3

隣接行列を使用した深さ優先検索のアルゴリズムを説明できる人はいますか? 再帰を使用した深さ優先検索のアルゴリズムを知っており、隣接行列を使用して実装しようとしましたが、あまり成功しませんでした。

私がこれまでに持っているのは

 dfs(G,i){

  mark i as visited;

  for(traverse through the edges of i vertex){

     if(vertex of edge is unseen){

       DFS(G,newVerted)
     }
   }

}
4

4 に答える 4

7 
    void DFS(int i)
    {
        int j;
        printf("\n%d",i);
        visited[i]=1;
        for(j=0;j<n;j++)
            if(!visited[j]&&G[i][j]==1)
                DFS(j);
    }

は頂点nの数、Gはグラフで、頂点が頂点に接続されていることをG[i][j]示しますij

于 2015-06-22T13:24:00.787 に答える
0

迷宮のようにいつも左に行くのが一番簡単だと思います。nノードから来た場合は、サイクルの次のノードに昇順で進みます。

どうやってあなたがやって来たことを知っているのか分かりません：Dしかし、クールなのは、余分なスペースやマーキングが必要ないということです。

編集
例

    5
   / \
  7   3
 /\   /\
4  1 6  2

午前は

......1
..1....
.1..11.
1.....1
..1...1
..1....
1..11..

したがって、5からの注文は3 6 3 2 3 5 7 1 7 4 7 5 3＃であり、5->3から開始したためです。

私が言ったように、あなたがノードにいるなら、あなたはあなたが来たノードに基づいて次のノードに行きます。次にアクセスするノードは、前のノードの次の番号です（現在のノードではありません）。

于 2012-08-03T22:05:13.747 に答える
0

スタックと訪問済みリストを維持し、while ループを使用することでそれを行うことができると思います: Visited は bool[] であり、すべての位置で false を保持するように初期化されています。どういうわけかブール値を返し、ノードからネイバーへのエッジがあるかどうかを伝えます。(1 との暗黙の比較、または単純に隣接行列にブール値を保持させる)
スタックは、ノードのインデックスを保持します。

dfs(G,i){
    Initialize Stack
    Current = i
    PossibleEdge = 0
    Visited[Current] = true  //You have visited the starting node
    Do {
        While (PossibleEdge < count) {
            if (G[Current,PossibleEdge] && NOT Visited[PossibleEdge]){
                Stack.Push(Current)      //Save state
                Current = PossibleEdge   //Continue with the child node
                Visited[Current] = true 
                PossibleEdge = -1        //So that it will be incremented to 0
            }
            PossibleEdge++
        }
        PossibleEdge = Current           //Continue to next row of "parent node"
        Current = Stack.Pop()            //Get parent node back
    } While (Stack contains nodes)
}

最適化できると確信しています (そして、私が疲れ果てているのを見ると、いくつかの論理エラーがある可能性があります) が、基本的な手順が理にかなっている場合は、それが始まりです!
編集:このヒントを明確にして追加します:再帰はおそらく簡単です;)

于 2012-08-03T22:49:47.423 に答える