그래프 데이터 구조 : DFS 대 BFS?

그래프 데이터 구조 : DFS 대 BFS?

---

그래프 문제가 주어지면 bfs 또는 dfs 알고리즘을 사용 해야하는지 어떻게 알 수 있습니까 ??? 또는 언제 dfs 알고리즘 또는 bfs 알고리즘을 사용합니까? 하나의 차이점과 장점은 무엇입니까?

---

BFS는 분기 요인에 따라 더 많은 메모리를 사용하지만 BFS는 완전한 알고리즘입니다. 즉, 가능한 가장 낮은 깊이에서 무언가를 검색하는 데 사용하는 경우 BFS가 최적의 솔루션을 제공합니다. BFS 공간 복잡성은 O(b^d)... 깊이까지 올라간 분기 요소입니다 (많은 메모리가 될 수 있음).

반면에 DFS는 공간에 대해 훨씬 더 좋지만 차선책을 찾을 수 있습니다. 즉, 한 정점에서 다른 정점으로의 경로를 검색하는 경우 실제 최단 경로를 찾기 전에 차선책을 찾을 수 있습니다 (그리고 거기서 멈출 수 있습니다). DFS 공간 복잡성은 O(|V|)... 즉, 차지할 수있는 가장 많은 메모리가 가능한 가장 긴 경로임을 의미합니다.

시간 복잡성이 동일합니다.

구현 측면에서 BFS는 일반적으로으로 구현되는 Queue반면 DFS는 Stack.

---

폭 먼저 형제를 먼저 검색합니다. 깊이 먼저 분명히 아이들을 먼저 검색합니다. 그래서 나는 당신이 어떤 종류의 검색을 하려는지에 달려 있다고 생각합니다. 필드 간 관계 유형 검색은 계층 적 (트리, 폴더, 순위 등)이 dfs로 더 적합 할 수있는 bfs에 적합 할 것입니다.

---

두 그래프 순회 모두 한 가지를 약속합니다. 그래프의 모든 정점을 방문하는 그래프의 완전한 순회입니다. 메모리 제약이 없다면 BFS가 많은 공간을 차지하므로 DFS가 좋은 선택입니다. 따라서이 두 가지 중에서 선택하는 것은 요구 사항에 따라 다릅니다.

그래프의 (강하게 /) 연결된 구성 요소를 찾고 싶습니까? 아니면 미로 나 스도쿠를 풀나요? DFS를 사용하십시오. 자세히 보면 Pre-Order, Post-Order 및 In-Order는 모두 DFS의 변형입니다. 예, 그것은 몇 가지 흥미로운 응용 프로그램입니다.

BFS 그래프가 2 분할인지 테스트하려면 이러한 작업이 필요한 두 노드 또는 응용 프로그램 간의 최단 경로를 찾으십시오.

---

bfs에서 큐는 dfs 스택에서 그래프 순회에 따라 정점을 저장하는 데 사용되는 동안 사용됩니다.
2- in bfs 프로세스는 수준별로 (방향성 또는 비 방향성 그래프에 따라) 수행되는 반면 dfs에서는 프로세스가 깊이까지 수행됩니다 (루트 노드를 처음 방문하는 프로세스와 다른 프로세스는 멀리 수행 한 다음 마지막 노드에서 역 추적을 적용하는 프로세스). 루트 노드).

---

BFS는 최단 경로에 매우 적합하지만 DFS는 그렇지 않습니다.

참조 URL : https://stackoverflow.com/questions/2626198/graphs-data-structure-dfs-vs-bfs