python - 幅優先探索か深さ優先探索か?

Question

100,000 以上のノードからなる巨大な有向グラフを実装しています。私はPythonを始めたばかりなので、これら2つの検索アルゴリズムしか知りません。任意の 2 つのノード間の最短距離を見つけたい場合、どちらがより効率的でしょうか? 私が気付いていない他の方法はありますか？

お時間をいただきありがとうございます

Answer 1

実際、BFS と DFS の代替手段は他にもいくつかあります。

最短経路を計算するのに非常に適切なものは次のとおりです: http://en.wikipedia.org/wiki/Dijkstra 's_algorithm

Dijsktra のアルゴリズムは基本的に BFS アルゴリズムの適応であり、グラフが重み付けされている場合、グラフ全体を検索するよりもはるかに効率的です。

@ThomasHが言ったように、Djikstraは加重グラフがある場合にのみ関連し、すべてのエッジの加重が同じ場合、基本的にデフォルトでBFSに戻ります。

選択肢が BFS と DFS のどちらかである場合、最短経路を見つけるには BFS の方が適切です。これは、距離が離れているノードに移動する前に、ノードのすぐ近くを完全に探索するためです。

これは、サイズ 3 のパスがある場合、アルゴリズムが距離 4 のノードの探索に移る前に探索されることを意味します。

DFS では、そのような保証はありません。ノードを詳細に調査するため、たまたま以前に調査された長いパスを見つけることができ、グラフ全体を調査して、それが正しいことを確認する必要があります。最短経路。

反対票を獲得している理由については、ほとんどの SO の質問は、解決策を見つけるために少し努力したことを示しているはずです。たとえば、DFS と BFS の長所と短所に関するいくつかの関連する質問があります。

次回は、少し検索したことを確認してから、具体的な疑問について質問してください。

Answer 2

最短パスを見つけたい場合は、DFS ではなく BFS を使用する必要があります。これは、BFS が最も近いノードを最初に探索するためです。目標に到達すると、最短パスを使用したことが確実になり、検索を停止できます。DFS は一度に 1 つのブランチを探索するのに対し、目標に到達したときに、別のブランチを経由する別のパスが短いかどうかを確認することはできません。

したがって、BFS を使用する必要があります。

グラフのエッジに異なる重みがある場合は、重み付きグラフに BFS を適応させた Dijkstra のアルゴリズムを使用する必要がありますが、重みがない場合は使用しないでください。

Floyd-Warshall アルゴリズムを使用することを推奨する人もいますが、これほど大きなグラフを作成するのは非常に悪い考えです。

Answer 3

グラフにエッジの重みがない場合は、グラフ内のノードに繰り返しアクセスし、新しいノードのいずれかが宛先ノードと等しいかどうかを確認する単純な幅優先検索を実行できます。エッジに重みがある場合、予想される時間と空間の複雑さに応じて、DJikstra のアルゴリズムと Bellman-Ford アルゴリズムを確認する必要があります。