Reputation: 5
I am trying to implement a recursive depth first traversal on a weighted digraph(, but it seems as if my output is always off. As in, I am getting extra visits to nodes. This is what I am currently working with:
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);
}
}
}
Where label is the letter assigned to the verticies (A = 0, etc...), visited is a vector holding whether or not the vertex at a certain index has been visited, and adj is the adjacency matrix.
Say I have a graph and the correct depth first search is A->D->B->C->E, what I end up getting is A->D->B->C->E->C->B->E. If it helps, for this example the adjacency matrix looks like:
| A B C D E
--|---------------
A | - - - 6 -
B | - - 8 3 2
C | - 8 - 7 -
D | 6 3 7 - -
E | - 2 - - -
Upvotes: 0
Views: 1747
Reputation: 1747
The parameters to your function are pass by value; so your visited vector
is not getting updated. Also, use pass by reference for your other vectors so that each recursive call is not copying the vectors.
Upvotes: 3