Implementing Depth First Traversal for a Graph using Adjacency Matrix C++

0
votes

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;
}
2
c++graphtraversaldepth-first-searchadjacency-matrix

2 Answers

1
votes

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.

0
votes
    #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);
    }

Here i am adding the nodes that are connected to node in reverse order,its working. https://ideone.com/AGm2xe