그래서 나는 BFS와 DFS 알고리즘의 결과물과 혼동합니다.DFS 및 BFS 출력?
BFS가 입력으로 그래프를 취한 것으로 이해하면 G이고 정점은 x이라고 가정합니다.
출력 : G 모든 정점에 새 그래프는 그래프에서 다른 정점에서 정점 x 짧은 방법을 갖는 그래프를 반환한다.
맞습니까? 그렇지 않다면 무엇입니까?
및 DFS는 어떻습니까? DFS의 입력은 그래프 일뿐입니다. DFS는 어디에서 시작하든 상관하지 않습니다. DFS의 출력은 무엇입니까?
감사
나는 당신이 원하는 것이 무엇인지 전혀 모르겠지만, 한번해볼 께.
의 우리는 다음과 같은 그래프 있다고 가정 해 봅시다 :
이 그래프에서X - 1 - 2 - 3
| \
1 1
| \
2 2
| \
3 3
는, X는 우리가에서 통과 시작 노드를 표시하고 숫자는 특정 노드가 보유하는 값을 의미한다. 이 시간 X는 3 개의 즉각적인 이웃 노드를 가지며, 모두 값 1을 유지합니다.
모든 노드를 두 번 트래버스 할 수 없다고 가정합니다. 프로그램이 항상 서있는 노드의 값을 출력한다고 가정 해 봅시다. 정말 방법 BFS와 DFS 일 (전혀)와 깊이에 점점없이
는, 출력은 다음과 같이 될 것이다 :
BFS: X 1 1 1 2 2 2 3 3 3
DFS: X 1 2 3 1 2 3 1 2 3
희망이 귀하의 질문에 대답을 제공합니다.
안녕하세요. 입력을 주셔서 감사합니다, 예,이 예제가 마음에 듭니다. 정확히 출력이 될 것이라고 생각합니다. 그래서 나는 이제 자신의 의견을보고 자신의 결과를 나의 기대와 일치시켜 더 자신감을 얻었습니다. 감사합니다! – seman
@ShlomiMizrahi 기꺼이 도와 드릴 수 있습니다. 당신이 그것에 만족하는 경우 솔루션 (녹색 게시물이 게시물 옆에)로 답변을 표시겠습니까 :) –
DFS는 그래프와 시작점 (랜덤)을 입력으로 받아서 일련의 정점을 출력으로 제공하는 그래프 탐색 기법입니다. 시퀀스에는 시작 정점에서 도달 할 수있는 정점이 포함됩니다. 즉, 그래프의 다른 정점에서 모든 정점에 도달 할 수 있는지 여부를 확인하고 있습니까?
선형 데이터 구조 (BFS의 경우 큐, DFS의 경우 스택)를 사용하여 그래프를 트래버스하는 두 가지 방법이 있습니다. "산출물"에 대한 정의는 없습니다. – Ralor
BFS와 DFS가 모두 그래프를 통과하여 가장 짧은 길을 찾으면 데이터를 저장하는 알고리즘에 코드를 추가 할 수 있습니까? 나는 최단 경로를 기억하는 것을 의미합니까? – seman
나는 그것을 말하지 않았다. DFS는 무게가 측정되지 않은 그래프에서 최단 경로 (BFS)를 찾을 수 없습니다. BFS를 사용하여 최단 경로를 검색하는 코드가 필요하다면 google로 테스트하고 사용하십시오. – Ralor