넓은 검색 우선 순위 또는 심도 우선 검색?

Question

나는 100,000 개 이상의 노드로 구성된 거대한 유향 그래프를 구현 중이다. 나는이 두 가지 검색 알고리즘에 대해서만 알고 있기 때문에 파이썬을 시작할 것이다. 두 노드 사이의 최단 거리를 찾고 싶다면 어느 것이 더 효율적입니까? 내가 잘 모르는 다른 방법이 있습니까?

감사합니다.

Answer 1

실제로 BFS와 DFS에는 여러 가지 대안이 있습니다. Dijsktra의 알고리즘은 기본적으로 BFS 알고리즘의 적응이다 http://en.wikipedia.org/wiki/Dijkstra 's_algorithm

및 그래프가 가중되는 경우가 훨씬 더 효율적 그래프 전체를 검색하는 것보다입니다 : 최단 경로를 계산에 매우 적합하다

하나입니다.

@ThomasH와 마찬가지로, Djikstra는 가중치 그래프가있는 경우에만 관련이 있습니다. 모든 에지의 가중치가 동일하면 기본적으로 BFS로 다시 설정됩니다.

선택 사항이 BFS와 DFS 사이에 있으면 BFS가 가장 짧은 경로를 찾는 데 더 적합합니다. 먼 거리에있는 노드로 이동하기 전에 노드의 바로 근처를 완전히 탐색 할 수 있기 때문입니다.

즉, 크기가 3 인 경로는 알고리즘이 거리 4의 노드를 탐색하기 전에 탐색됩니다.

DFS를 사용하면 노드를 깊이 탐구하기 때문에 이전에 탐색 한 경로가 더 길어 지므로 전체 그래프를 탐색해야합니다. 그것이 최단 경로입니다.

downvotes를 얻는 이유에 관해서는 대부분의 SO 질문에는 약간의 노력이 해결책을 찾는데 도움이 될 것입니다. 예를 들어, DFS 대 BFS의 장단점에 대한 몇 가지 관련 질문이 있습니다.

다음 번에 조금만 찾은 다음 특정 의심에 대해 질문하십시오.

Answer 2

다음과 같은 두 가지 알고리즘에서보세요 :

1. Dijkstra's algorithm - 단일 소스 최단 경로
2. Floyd-Warshall algorithm - 모든 쌍 최단 경로

Answer 3

을의 가장자리에 대한 가중치가없는 경우 그래프에서 반복적으로 그래프의 노드에 액세스하고 새 노드 중 하나가 대상 노드와 동일한 지 확인하는 간단한 우선 탐색을 수행 할 수 있습니다. 가장자리에 가중치가 있다면 DJikstra의 알고리즘과 Bellman-Ford 알고리즘은 예상 한 시간과 공간 복잡성에 따라 사용자가 살펴야 할 것입니다.

Answer 4

가장 짧은 경로를 찾으려면 BFS가 가장 가까운 노드를 먼저 탐색하므로 목표를 달성 할 때 가장 짧은 경로를 사용했는지 확인하고 검색을 중지 할 수 있습니다. DFS는 한 번에 하나의 지점을 탐색하지만 목표에 도달하면 다른 지점을 통해 다른 경로가 더 짧다고 확신 할 수 없습니다.

따라서 BFS를 사용해야합니다.

그래프의 가장자리에 다른 무게가있는 경우 가중치 그래프에 BFS를 적용한 Dijkstra 알고리즘을 사용해야하지만 가중치가없는 경우에는 사용하지 마십시오.

어떤 사람들은 Floyd-Warshall 알고리즘을 사용하도록 권장 할 수도 있지만이 큰 그래프에 대해서는 매우 나쁜 생각입니다.