[algorithm] 그래프에서주기를 찾는 데 BFS가 아닌 DFS가 필요한 이유

왜 그런 오래된 질문이 내 피드에 나타 났는지 모르겠지만 이전 답변이 모두 나쁘기 때문에 …

DFS는 작동 하기 때문에 방향성 그래프에서주기를 찾는 데 사용됩니다. .

DFS에서 모든 정점은 “방문”되며, 정점 방문은 다음을 의미합니다.

1. 정점이 시작됩니다.

2. 해당 정점에서 도달 할 수있는 하위 그래프를 방문합니다. 여기에는 해당 정점에서 도달 할 수있는 추적되지 않은 모든 가장자리를 추적하고 도달 할 수있는 모든 방문하지 않은 정점을 방문하는 것이 포함됩니다.

3. 정점이 완성되었습니다.

중요한 기능은 정점이 완료되기 전에 정점에서 도달 할 수있는 모든 가장자리가 추적된다는 것입니다. 이것은 DFS의 기능이지만 BFS는 아닙니다. 사실 이것이 DFS의 정의입니다.

이 기능으로 인해 주기 의 첫 번째 정점이 시작 되는시기를 알고 있습니다 .

1. 주기의 가장자리가 추적되지 않았습니다. 우리는 이것을 알고 있습니다. 왜냐하면 여러분은 사이클의 다른 정점에서만 얻을 수 있기 때문입니다. 그리고 우리는 시작할 첫 번째 정점에 대해 이야기 하고 있습니다.
2. 해당 정점에서 도달 할 수있는 모든 추적되지 않은 가장자리 는 완료되기 전에 추적 되며 여기에는 아직 추적 된 가장자리가 없기 때문에주기의 모든 가장자리 가 포함됩니다 . 따라서주기가있는 경우 시작된 후 완료되기 전에 첫 번째 정점으로 돌아가는 가장자리를 찾을 수 있습니다. 과
3. 추적되는 모든 가장자리는 시작되었지만 완료되지 않은 모든 정점에서 도달 할 수 있으므로 이러한 정점에 대한 가장자리를 찾는 것은 항상 주기를 나타냅니다.

따라서주기가있는 경우 시작되었지만 완료되지 않은 정점 (2)에 대한 가장자리를 찾을 수 있으며 그러한 가장자리를 찾으면주기 (3)가 있음을 보장합니다.

이것이 DFS가 방향성 그래프에서주기를 찾는 데 사용되는 이유입니다.

BFS는 그러한 보장을 제공하지 않으므로 작동하지 않습니다. (BFS 또는 유사한 하위 절차를 포함하는 완벽하게 좋은주기 찾기 알고리즘에도 불구하고)

반면에 무 방향 그래프는 한 쌍의 꼭지점 사이에 두 개의 경로가있을 때마다, 즉 나무가 아닐 때마다주기가 있습니다. 이것은 BFS 또는 DFS 중에 쉽게 감지 할 수 있습니다. 새 꼭지점으로 추적 된 가장자리는 트리를 형성하고 다른 가장자리는주기를 나타냅니다.