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

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

---

주로 DFS는 BFS가 아닌 그래프에서주기를 찾는 데 사용됩니다. 이유가 있습니까? 둘 다 트리 / 그래프를 횡단하는 동안 노드가 이미 방문되었는지 확인할 수 있습니다.

---

깊이 우선 검색은 더 빨리 역 추적 할 수 있으므로 폭 우선 검색보다 메모리 효율적입니다. 또한 호출 스택을 사용하는 경우 구현하기가 더 쉽지만 스택을 오버플로하지 않는 가장 긴 경로에 의존합니다.

또한 그래프가 방향 이 지정되면 노드를 방문했는지 여부뿐만 아니라 거기에 어떻게 도달했는지 기억해야합니다. 그렇지 않으면주기를 찾았다 고 생각할 수 있지만 실제로는 두 개의 개별 경로 A-> B 만 있지만 이것이 경로 B-> A가 있다는 것을 의미하지는 않습니다. 예를 들면

에서 시작하는 BFS를 수행하면 0주기가있는 것으로 감지하지만 실제로는주기가 없습니다.

깊이 우선 검색을 사용하면 하강 할 때 방문한 노드를 표시하고 역 추적 할 때 표시를 해제 할 수 있습니다. 이 알고리즘의 성능 향상에 대한 설명을 참조하십시오.

유 방향 그래프에서주기를 감지 하는 가장 좋은 알고리즘 은 Tarjan의 알고리즘을 참조 할 수 있습니다.

---

1. DFS는 구현하기가 더 쉽습니다.
2. DFS가주기를 찾으면 스택에는주기를 형성하는 노드가 포함됩니다. BFS의 경우도 마찬가지이므로 발견 된 주기도 인쇄하려면 추가 작업을 수행해야합니다. 이것은 DFS를 훨씬 더 편리하게 만듭니다.

---

그래프가 방향이 지정되지 않은 경우 BFS가 합리적 일 수 있습니다 (방향성 그래프로주기를보고하는 BFS를 사용하여 효율적인 알고리즘을 보여줄 수 있습니다!). 여기서 각 "교차 에지"는주기를 정의합니다. 교차 에지가 {v1, v2}이고 해당 노드를 포함하는 루트 (BFS 트리에서)가 r이면주기는 r ~ v1 - v2 ~ r( ~경로, -단일 에지)이며 DFS 에서처럼 거의 쉽게보고 될 수 있습니다.

BFS를 사용하는 유일한 이유는 (무 방향) 그래프가 긴 경로와 작은 경로 커버 (즉, 깊고 좁은)를 가질 것이라는 것을 알고있는 경우입니다. 이 경우 BFS는 DFS 스택보다 대기열에 대해 비례 적으로 적은 메모리를 필요로합니다 (물론 여전히 선형).

다른 모든 경우에는 DFS가 분명히 승자입니다. 방향성 및 무 방향성 그래프 모두에서 작동하며주기를보고하는 것은 사소한 일입니다. 조상에서 후손까지의 경로에 뒤쪽 가장자리를 연결하면주기를 얻을 수 있습니다. 대체로이 문제에 대해 BFS보다 훨씬 낫고 실용적입니다.

---

트리의 임의의 지점에 사이클을 배치하면 DFS는 트리의 약 절반을 덮었을 때 사이클에 충돌하는 경향이 있으며, 절반은 사이클이가는 곳을 이미 횡단하고 절반은 그렇지 않습니다 ( 평균적으로 나머지 트리의 절반에서 찾을 수 있으므로 평균적으로 트리의 약 0.5 * 0.5 + 0.5 * 0.75 = 0.625로 평가됩니다.

나무의 임의의 지점에 사이클을 배치하면 BFS는 해당 깊이에서 나무의 레이어를 평가할 때만 사이클에 충돌하는 경향이 있습니다. 따라서 일반적으로 균형 이진 트리의 잎을 평가해야하므로 일반적으로 더 많은 트리를 평가하게됩니다. 특히, 3/4의 경우 두 개의 링크 중 적어도 하나가 나무의 잎에 나타나며,이 경우 평균적으로 나무의 3/4 (하나의 링크가있는 경우) 또는 7 / 나무의 8 개 (두 개가있는 경우)이므로 이미 검색 기대치에 도달했습니다. 1 / 2 * 3 / 4 + 1 / 4 * 7 / 8 = (7 + 12) / 32 = 21/32 = 잎 노드에서 떨어져서주기를 추가 한 트리 검색 비용을 추가하지 않고도 트리의 0.656 ...

또한 DFS는 BFS보다 구현하기 쉽습니다. 그래서 당신이 당신의주기에 대해 알지 못한다면 그것은 사용하는 것입니다 (예를 들어,주기는 당신이 검색하는 루트 근처에있을 가능성이 있고 BFS가 당신에게 이점을 제공합니다).

---

BFS는주기를 찾는 방향 그래프에 대해 작동하지 않습니다. A-> B 및 A-> C-> B를 그래프에서 A에서 B 로의 경로로 고려하십시오. BFS는 B가 방문한 경로 중 하나를 따라 가면 말합니다. 다음 경로를 계속 이동하면 표시된 노드 B가 다시 발견되었으므로 사이클이 있습니다. 분명히 여기에는주기가 없습니다.

---

그래프가 순환적임을 증명하려면 하나의 순환 (직접 또는 간접적으로 자신을 향하는 에지)이 있음을 증명해야합니다.

DFS에서는 한 번에 하나의 정점을 가져 와서주기가 있는지 확인합니다. 주기가 발견되는 즉시 다른 정점 검사를 생략 할 수 있습니다.

BFS에서 우리는 많은 정점 가장자리를 동시에 추적해야하며 마지막에주기가 있는지 확인하는 경우보다 더 자주 추적해야합니다. 그래프의 크기가 커짐에 따라 BFS는 DFS에 비해 더 많은 공간, 계산 및 시간이 필요합니다.

---

재귀 또는 반복 구현에 대해 이야기하고 있는지 여부에 따라 다릅니다.

재귀 DFS는 모든 노드를 두 번 방문합니다. Iterative-BFS는 모든 노드를 한 번 방문합니다.

주기를 감지하려면 노드에서 "시작"할 때와 노드에서 "완료"할 때 모두 인접성을 추가하기 전과 후에 노드를 조사해야합니다.

이를 위해서는 Iterative-BFS에서 더 많은 작업이 필요하므로 대부분의 사람들은 Recursive-DFS를 선택합니다.

예를 들어 std :: stack을 사용한 Iterative-DFS의 간단한 구현에는 Iterative-BFS와 동일한 문제가 있습니다. 이 경우 더미 요소를 스택에 배치하여 노드 작업을 "완료"할 때 추적해야합니다.

Iterative-DFS에서 노드로 "완료"할 때를 결정하기 위해 추가 작업이 필요한 방법에 대한 자세한 내용은이 답변을 참조하십시오 (TopoSort 컨텍스트에서 답변 됨).

재귀없이 DFS를 사용하는 토폴로지 정렬

이것이 사람들이 노드 처리를 "완료"할 때 결정해야하는 문제에 대해 Recursive-DFS를 선호하는 이유를 설명합니다.

---

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

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

In a DFS, every vertex is "visited", where visiting a vertex means:

1. The vertex is started

2. The subgraph reachable from that vertex is visited. This includes tracing all untraced edges that are reachable from that vertex, and visiting all reachable unvisited vertexes.

3. The vertex is finished.

The critical feature is that all edges reachable from a vertex are traced before the vertex is finished. This is a feature of DFS, but not BFS. In fact this is the definition of DFS.

Because of this feature, we know that when the first vertex in a cycle is started:

1. None of the edges in the cycle have been traced. We know this, because you can only get to them from another vertex in the cycle, and we're talking about the first vertex to be started.
2. All untraced edges reachable from that vertex will be traced before it is finished, and that includes all the edges in the cycle, because none of them has been traced yet. Therefore, if there is a cycle, we will find an edge back to the first vertex after it is started, but before it is finished; and
3. Since all edges that are traced are reachable from every started-but-unfinished vertex, finding an edge to such a vertex always indicates a cycle.

So, if there is a cycle, then we are guaranteed to find an edge to a started-but-unfinished vertex (2), and if we find such an edge, then we are guaranteed that there is a cycle (3).

That's why DFS is used to find cycles in directed graphs.

BFS provides no such guarantees, so it just doesn't work. (notwithstanding perfectly good cycle-finding algorithms that include BFS or similar as a sub-procedure)

An undirected graph, on the other hand, has a cycle whenever there are two paths between any pair of vertexes, i.e., when it's not a tree. This is easy to detect during either BFS or DFS -- The edges traced to new vertexes form a tree, and any other edge indicates a cycle.

참고URL : https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs