다음 그래프 G를 고려하고 G에서의 알고리즘 DFS 실행시, 그래프의 에지는 트리 에지 (t), 백 에지 (b), 포워드 에지 (f) 및 크로스 에지 (c) 다음 그래프와 같습니다. 그래프의 각 노드에 대해 노드의 발견 시간과 완료 시간을 찾으십시오. 즉, 그래프의 각 노드 v에 대해이 노드와 알고리즘 DFS를 연결하는 값 d [v]와 f [v]를 찾습니다.알고리즘을 적용하기 위해 초기 노드를 어떻게 찾을 수 있습니까?
D를 값의 하나의 가능한 할당이있다 통지는 [V]와 F [V].
깊이 우선 검색 알고리즘을 적용하기 위해 초기 노드를 찾는 방법을 알려주시겠습니까?
노드를 살펴보십시오 a - 노드 a에서 DFS는 무엇을 할 수 있습니까? b 또는 e으로 갈 수 있습니다. a->b은 트리 에지이고 a->e은 앞쪽 가장자리이므로 (트리/앞쪽 가장자리의 정의를 확인하십시오) b을 선택했습니다. b에서 유일한 선택은 f입니다. f에서 DFS는 a, e 또는 g 중 하나가 될 수 있습니다. (f->a은 뒤쪽 가장자리로 표시되어 있으므로 지금까지는 모든 것이 정확함)을 방문하려고 시도한 것으로 가정하고 e을 방문한 것보다 b을 방문하려고 시도한 것보다 좋습니다. 그러나 가장자리가 f->g 인 문제가 생겼습니다. 교차 모서리로 표시되어 DFS가 이미 g을 방문했음을 의미합니다. 그렇지 않으면이 가장자리가 트리 가장자리로 표시됩니다. 따라서 a은 초기 노드가 아닙니다. 우리는 다른 옵션을 시도해야합니다. c는 어떨까요? 다시 말하자면, c에서 나오는 모든 모서리는 나무가 아닌 십자가로 표시되므로 c은 초기 노드가 아닙니다.
약 d? DFS가 d에서 시작된 경우 d에서 g으로 갈 수 있으며 d->g은 트리 가장자리로 표시되어 있기 때문에 그럴 수 있습니다. g에서 갈 노드가 없었으므로 d으로 역 추적하고 h을 방문했습니다. h에서 g을 방문하려고했지만 이전에 이미 방문 했으므로 h->g은 교차 수정으로 표시되어 있습니다. 그렇기 때문에 d이이 DFS 실행의 초기 노드였습니다. d, g 및 h이 포함 된 연결된 구성 요소를 방문한 후 DFS는 a 또는 c에서 다시 시작될 수 있지만 교차 경계로 인해 c에서 시작되지 않았 음을 이미 알고 있습니다. 따라서 a에서 시작하여 b, f 및 e을 방문한 후 c에서 시작되었습니다.
우리는 a에서 시작하지 않습니다. 왜냐하면 f에 도달 한 후에 g로 가야 할 것이기 때문에 (f, g)는 교차 모서리입니까? 또한 h-> g의 경로가 없어도 d-> g-> h가 연결된 구성 요소입니까? 또한 x가 y 인 가장자리가 교차 가장자리 인 경우 y가 이미 방문되었음을 알 수 있습니다. 가장자리가 나무 가장자리 인 경우 y는 아직 방문하지 않았 음을 알 수 있습니다. 뒷 모서리 나 앞 모서리가 있다면 무엇을 결론 지을 수 있습니까? –
"그래서, 우리는 [...] 오른쪽부터하기 때문에 시작하지 않습니다." - 권리. "또한 왜 d-> g-> h는 연결된 구성 요소입니까 [...]?" - 죄송 합니다만, 정확하지 않았습니다. 연결된 구성 요소가 정의되지 않은 무 방향 그래프에 있습니다. 나는 DFS가 d, g, h (d에서 시작)를 방문한 후에 아무데도 갈 수 없다는 것을 의미했다. 왜냐하면 그 노드에서 나오는 다른 가장자리가 없으므로 그래프의 다른 노드를 선택하고 그 노드에서 시작해야하기 때문이다. 마디. –
여러 종류의 모서리에 관해서 - 그림을 붙이고이 질문에서 설명하려고했습니다. http : //stackoverflow.com/questions/27484803/edges-of-the-graph ... 주어진 그래프에 DFS를 적용했지만 DFS의 결과를 얻고 어떻게 작동하는지 재구성하려면 다른 노드에서 시작하여 DFS를 시뮬레이트하고 동일한 결과를 얻는 지 확인해야합니다. 트리 가장자리는 DFS가 따르고 방문하지 않은 노드에 도달하는 가장자리입니다. 뒤쪽 가장자리는 트리의 현재 노드의 조상 인 방문한 노드의 가장자리입니다. –
트리 가장자리는 포리스트를 형성해야합니다. DFS가 시작할 수있는 노드는 들어오는 트리 가장자리가없는 노드입니다.
DFS가 시작된 노드가 들어오는 트리 가장자리가없는 노드 인 이유를 설명해 주시겠습니까? –
"트리 가장자리가 트리를 형성해야합니다." - 틀렸어, 숲을 형성 할 수도 있고 여기가 그럴거야. –
@ MD-11은 그래프가 연결되어 있다고 잘못 가정합니다. 결정된. – saadtaame
귀하의 질문은 "알고리즘 소개"에 있습니다. – qqibrow
@qqibrow 깊이 검색의 장에서 찾지 못했습니까? 어디서 봤니? :/ –
이 장의 마지막 부분에 있습니다. 나는 초판을 사용하고있다. – qqibrow