c++ - 使用邻接矩阵 C++ 实现图的深度优先遍历

Question

我有一组节点和一些表示连接的节点的边。V_nodes 1 7 22 97 48 11V_arcs (1 22) (97 22) (7 1) (11 48) (48 7) (11 0)V_weight 1

我创建了它的邻接矩阵，显示 1 表示连接的顶点，0 表示断开的顶点。现在我想使用它的邻接矩阵为这个图实现深度优先遍历。我看过有关 DFS 的教程，但我很困惑如何使用我的邻接矩阵遍历它。我只需要使用深度优先遍历打印节点。任何帮助将不胜感激。

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

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

请注意，如果您的图中有一个循环，就会出现问题。