Design an algorithm to check if a given graph is connected?

Answer 1

As a rough outline, we start with some vertex x, and build a list of the vertices you can get to from x. Each time we find a new vertex to be added to this list, we check its neighbors to see if they should be added as well. Finally, we check whether the list covers the whole graph. In pseudocode: test-connected(G)

{

choose a vertex x

make a list L of vertices reachable from x,

and another list K of vertices to be explored.

initially, L = K = x.

while K is nonempty

find and remove some vertex y in K

for each edge (y,z)

if (z is not in L)

add z to both L and K

if L has fewer than n items

return disconnected

else return connected

}

To analyze the algorithm, first notice that the outer loop happens n times (once per vertex). The time for the inner loop (finding all unreached neighbors) is more complicated, and depends on the graph representation. One key step (testing whether z is in L) seems like it might be slow, but can be done quickly by keeping a bit on each vertex that says whether it's in L or not. * For the object oriented representation, each execution of the inner loop involves scanning through all m edges of the graph. So the total time for the algorithm is O(mn). * For the adjacency matrix representation, each execution of the inner loop involves looking at a single row of the matrix, in time O(n). So the total time for the algorithm is O(n^2). * In the adjacency list (or incidence list) representation, each element on each list is scanned through once. So the total time on all executions of the inner loop is the same as the total length of all adjacency lists, which is 2m. Note that we don't multiply this by n, even though this is a nested loop -- we just add up the number of times each statement is executed in the overall algorithm. The total time for the algorithm is O(m+n) At the end of the algorithm, the list L tells you one connected component of the graph (how much of the graph can be reached from x). With some more care, we can find all components of G rather than just one component. If graph is connected, we can modify the algorithm to find a tree in G covering all vertices (a spanning tree): For each z, let parent(z) be the vertex y corresponding to the time at which we added z to L. This gives a graph in which each vertex except x is connected to some previous vertex, and any such graph must be a tree

Answer 2

We'll need to keep track of two things:

1) The vertices we've already visited.

2) The vertices we need to visit.

Algorithm in pseudocode:

Stack toVisit

Set visited

add any vertex to toVisit

while toVisit is not empty

currentVertex = toVisit.pop()

visited.add(currentVertex)

for each vertex in neighbors of currentVertex

if vertex is not in visited

toVisit.push(vertex)

If visited contains all vertices in the graph, graph is connected; else, graph is not connected.

Answer 3

graphIsConnected = true

for (current = ) each vertex in graph

for (other = ) each other vertex in graph

if not (current isConnectedTo other)

graphIsConnected = false

end

if graphIsConnected

// yay!

If you want an implementation for isConnectedTo, I suggest using a version of a depth-first search algorithm modified to check for loops.