c++ - 加权有向图

Question

我正在尝试在加权有向图(上实现递归深度优先遍历(，但似乎我的输出总是关闭的。就像这样，我对节点进行了额外的访问。这就是我目前正在使用的:

void Dfs( int u, vector<bool> visited, vector < char > label, vector < vector < int > > adj)
{
visited[u] = true;
cout << label[u];

for ( int i = 0; i < (signed)visited.size(); i++)
    {
    if (visited[i] != true && adj[u][i] != 0)
            {
            cout << "->";
            Dfs( i, visited, label, adj);
            }
    }

}

其中 label 是分配给顶点的字母(A = 0，等等...)，visited 是一个 vector ，表示某个索引处的顶点是否已被访问，adj 是邻接矩阵。

假设我有一个图，正确的深度优先搜索是 A->D->B->C->E，我最终得到的是 A->D->B->C->E-> C->B->E。如果有帮助，对于此示例，邻接矩阵如下所示:

  |  A  B  C  D  E
--|---------------
A |  -  -  -  6  -
B |  -  -  8  3  2
C |  -  8  -  7  -
D |  6  3  7  -  -
E |  -  2  -  -  -

Answer 1

函数的参数是按值传递的；所以你的 visited vector 没有得到更新。此外，对其他 vector 使用按引用传递，以便每个递归调用都不会复制 vector 。