0

ノードのセットと、どのノードが接続されているかを表すいくつかのエッジがあります。V_nodes 1 7 22 97 48 11 V_arcs (1 22) (97 22) (7 1) (11 48) (48 7) (11 0) V_weight 1

接続された頂点の場合は 1、切断された頂点の場合は 0 を示す隣接行列を作成しました。次に、Adjacency Matrix を使用して、このグラフの深さ優先トラバーサルを実装したいと思います。DFS のチュートリアルを見たことがありますが、隣接行列を使用してそれをトラバースするにはどうすればよいか混乱しています。Depth First Traversal を使用してノードを出力するだけです。どんな助けでも大歓迎です。

// Prints the adjacency matrix

cout<<"Adjacency Matrix : \n";
for(int i=0;i<6;i++)
    cout<<"       "<<nodes[i].nodevalue;
cout<<endl<<endl;

for(int i=0;i<6;i++)
{
    for (int j=0;j<6;j++)
    {
        cout<<"       "<<edges[i][j];
    }
    cout<<endl<<nodes[i].nodevalue;
    cout<<endl<<endl;
}
4

2 に答える 2

1

stackとも呼ばれる後入れ先出しキューを使用することをお勧めします。再帰を使用することもできますが、グラフが大きすぎるとスタック オーバーフローが発生するリスクがあります。

ノードごとに、そのノードが接続されているすべてのノードをループして、それらをスタックに追加します。

スタックから最初のノードを取り出し、必要な操作を行ってから、プロセスを繰り返します。

これは次のようになります

void dfs(int node){
  std::stack<int> expand;
  expand.push(node);
  while(!expand.empty()){
    int tnode=expand.top();expand.pop();
    do_operation_on(tnode);
    for(int i=0;i<ADJACENCY_MATRIX_DIMENSION;i++)
      if(adj_matrix[tnode][i])
        expand.push(i);
  }
}

グラフにサイクルがある場合、問題が発生することに注意してください。

于 2012-12-30T12:25:58.220 に答える
0 
    #include<cstdio>
    #include<iostream>
    #include<stack>
    #include<cstring>
    using namespace std;
    int G[10][10],n;
    void dfs(int strt)
    {
        int vis[n];
        memset(vis,0,sizeof vis);
        stack<int>st;
        st.push(strt);
        while(!st.empty())
        {
            int pre=st.top();st.pop();

            if(!vis[pre])
            {
                cout<<pre<<" ";
                vis[pre]=1;
                for(int i=n-1;i>=0;i--)
                {

                    if(G[pre][i]==1 and !vis[i])
                    {
                        st.push(i);
                    }
                }
            }
        }
        cout<<endl;
    }
    int main()
    {
        cin>>n;
        for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
            cin>>G[i][j];
        dfs(2);
    }

ここでは、ノードに接続されているノードを逆の順序で追加しています。https://ideone.com/AGm2xe

于 2015-06-22T14:18:53.790 に答える