0

重み付き有向グラフに再帰的な深さ優先探索を実装しようとしています（しかし、出力が常にオフになっているようです。のように、ノードへの追加の訪問があります。これが現在作業しているものです。 

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は特定のインデックスの頂点が訪問されたかどうかを保持するベクトルであり、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  -  -  -
4

1 に答える 1

3

関数へのパラメーターは値渡しされます。だからあなたvisited vectorは更新されていません。また、他のベクトルには参照渡しを使用して、各再帰呼び出しがベクトルをコピーしないようにします。

于 2012-05-01T02:50:00.373 に答える