C) Both can be used.
//pseudo code
void bfs(node u) {
mark u as visited;
queue.push(u);
while(!queue.empty()){
s = pop one element from queue;
for(node v adjacent to s) {
if (v is not visited) {
mark v as visited;
queue.push(v);
}
}
}
}
void dfs(node u) {
for(node v adjacent to u) {
mark v as visited;
dfs(v); // recursive
}
}
main () {
// using dfs
connected_component = 0;
for each node u:
if u is not visited :
mark u as visited;
connected_component += 1
dfs(u)
// using bfs
connected_component = 0;
for each node u:
if u is not visited :
connected_component += 1
bfs(u)
}
in both the cases, bfs()
or dfs()
returns only when one connected component is fully explored and all nodes belonging to that component have been marked. We are keeping these bfs() or dfs()
inside a for loop to make sure all such compoments are discovered in case the graph is disconnected.
connected_component
variable gets incremented whenever we return from dfs()
or bfs()
and still have unvisited nodes