0

I have got a set of nodes and few edges that represent which nodes are connected. 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

I have created its adjacency matrix that shows 1 for connected and 0 for disconnected vertices. Now I want to implement a Depth First Traversal for this graph using its Adjacency Matrix. I have seen the tutorials on DFS but I am confused How can I traverse it using my Adjacency matrix. I just need to print the nodes using Depth First Traversal. Any help will be appreciated.

// 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

You'll want to use a last-in first-out queue, otherwise known as a stack. You could also use recursion, but you risk having a stack overflow if you graph is too large.

For each node, loop through all the nodes that node is connected to, adding them to the stack.

Pop the first node off of the stack, do whatever operation you wanted to do, and then repeat the process.

This could look like

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);
  }
}

Note that if you have a cycle in your graph there will be problems.

于 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 回答