0

Data Structures and Algorithms in C++ 4e (By Adam Drozdek) のグラフに関連する資料を読んでいます。彼の Graph Breadth First Search の実装では、疑似コードは次のようになります。

BFS():
    for all vertices u
        num(u) = 0
    edges = null
    i = 1
    while there is a vertex v such that num(v) is 0
        num(v)++
        enqueue(v)
        while queue is not empty
            v = dequeue()
            if num(u) is 0
                num(u) = i++
                enqueue(u)
                attach edge(v,u) to edges
    output edges

基本的に、グラフの実装では、すべての頂点のセットとすべてのエッジのセットを既に保持しています。BFS では、アルゴリズムは最初に、このセットでアクセスされていないすべての頂点を列挙して、完全なグラフをトラバースします。

私の質問は、すべての頂点を既にセットに格納しているため、BFS アルゴリズムを使用せずにセットをループして特定の頂点を操作できるということです。グラフ走査アルゴリズムが必要な理由と主な用途は何ですか?

4

2 に答える 2

2

BFS と DFS には多くの用途があります...
BFS のアイデアを提供するには:

  1. ソーシャル ネットワークを表すグラフがあり、特定のユーザーに友達を提案したいと考えています。次に、BFS を実行します。頂点 (人) が近いほど、フレンド候補リストのランクが高くなります。(ユーザー数が多い場合は、距離 3 で停止し、グラフ全体で BFS を実行しないのが理にかなっています)。

  2. 解空間探索。解空間が無限である場合に非常に便利です。(ゲームツリーを参照)

  3. 最短パス (エッジの重みが同じで、ループがない場合)。Dijkstra は、変数の重みで機能するようにそれを適応させました ( Dijkstra のアルゴリズムを参照してください)。

于 2014-03-27T14:45:16.897 に答える
1

たとえば、通常、DFS は、ツリーが再帰的にトラバースされるときに暗黙的に使用されます。

于 2014-03-27T14:49:47.497 に答える