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

}
``````

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.

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