ProAnswers.org

What is the algorithm to find if a graph is connected or not?

What is the algorithm to find if a graph is connected or not?

Take an arbitrary vertex V from the graph G(which has n vertices) and make a list of vertices(Say L) that can be reached through V via one or more edges(i.e there is a path).After you have completed the process, if the set L contains all the vertices present in the graph G, then it is connected. If some vertices are missing then it is disconnected.

if_Connected(Graph G)
pick a vertex v
initially L={v}
repeat
add vertex v1 to the list L if there is a path between v and v1
end
if(number of vertices in set L=n) return true
else return false