Ryan Mann Ryan Mann - 4 years ago 122
C++ Question

Finding connected components in graph (adjA) using DFS

I've been searching around the internet today trying to figure out how to run DFS on an adjacency list

vector<list<edge>> adjA
, but I just cannot figure out how to do this correctly. The best example I could find online was: Find connected components in a graph
but using his first method does not seem to work and I am not confident enough with unions / sets to try his other method. This is what I have so far: (disregard
test_vector
and
cc
, I'm focusing on getting the
cc_count
to work)

edge is a struct that contains:

struct edge{
int to; //copy of to_original (dont worry about this it's for a different functionality)
int w; //weight of edge
int from_original; //from vertex
int to_original; //to vertex
}


somewhere in int main:

cout << "conn: " << connected(adjA, test_vector) << endl;





int connected(vector<list<edge>> &adjA, vector<short int> &cc){
int v_size = adjA.size();
vector<bool> discovered(false,v_size);
int cc_count = 0;
for(unsigned int u = 0; u < adjA.size(); u++){
if(!discovered[u]){
cout << u << endl;
discovered[u] = true;
cc_count+=1;
dfs(adjA,discovered,cc,cc_count,u);
}
}
return cc_count;
}





void dfs(vector<list<edge>>&adjA, vector<bool> &discovered, vector<short int> &cc, int &cc_count,int u){
for(unsigned int v = 0; v < adjA[u].size();v++){
if(!discovered[v]){
cout << v << endl;
discovered[v] = true;
dfs(adjA, discovered,cc,cc_count,v);
}
}

}


from the line
cout << v << endl;
and
cout << u << endl
it will print showing that it was able to visit every node once. However, I am incrementing the
cc_count
incorrectly I think. In this adjacency list:

0->[1]->[3]->[5]
1->[0]->[2]->[3]->[4]
2->[1]->[4]
3->[0]->[1]->[4]->[5]
4->[1]->[2]->[3]->[5]->[6]
5->[0]->[3]->[4]->[6]
6->[4]->[5]


the program will output:

0
1
2
3
4
5
6
conn: 7


when conn should be 1, since the whole graph is a single component. I feel like I might be going about this the wrong way. Is there a change I should do? Is there a better way to do this using DFS or BFS?

I apologize for the poor formatting, I spent almost an hour just trying to get the stack overflow errors to go away.

graph that adjacency list represents

graph represented by adjacency list

Answer Source

Your dfs method is not looking at the edges at all. I don't know from the question what an edge is, but lets just assume it is pair-like (both endpoints).

Then

for(unsigned int v = 0; v < adjA[u].size();v++) {
    // do something with v
}

should actually be

for (auto const & e: adjA[u]) {
    // do something with the endpoint of e other than u
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download