Home » maths » graph theory » Finding Connected Components With Depth First Search

# Finding Connected Components With Depth First Search

In this post we will discuss depth first searches and their complexity, and as an application create an algorithm to return the connected components of a graph.

Depth First Search

Let me show you some pseudocode first taken from Edelbrunner and Harer’s Computational Topology, p. 35:

void Visit(vertex):
if vertex unmarked then mark vertex; P1;
forall neighbors new_vertex of vertex do<
Visit(new_vertex)
endfor; P2
else P3


Where P1 is to be executed the first time a node is visited, P2 after all children have been processed and P3 each time a node is revisited.

Notice that each edge is used twice, forwards and backwards, and each vertex is visited once for each of its incident edges (and once more for the vertex we start with). Thus, assuming that P1, P2, P3 are say $O(1)$, the depth first search will be $O(n+m)$.

Connected Components

Recall that a connected component of a vertex is the subgraph containing all paths in the graph that visit the vertex. In order to find the connected component of a particular vertex, we can perform a depth first search starting with that vertex. Since we are also interested in the edges of the component we will be marking these as seen/unseen also. This will be implemented for a simple graph, but it is trivial to alter it for directed graphs.

Since the complexity of a search is $O(n+m)$, for each vertex $v$, let $n_v$ denote the number of vertices in the connected component containing $v$, and $m_v$ for the edges.
Let $T$ be a transversal of the vertex sets, one from each component.

Then to return all the connected components, we run the search starting with each vertex, stopping in $O(1)$ time if we’ve already encountered the vertex’s component, meaning that the final time will be $\sum \limits _{v \in T}O(n_v+m_v) = O(n+m)$.

Let’s see the python code.

The Code

import tigraphs as tig

def get_connected_components(graph):
vertices = graph.vertices
edges=graph.edges
#First we mark all the edges and vertices as unseen
for vertex in vertices:
vertex.seen_before=False
for edge in edges:
edge.seen_before=False
#A list of all the components
components=[]
for vertex in vertices:
component=get_component(graph, vertex)
if component: #checks to see if we've seen this component already
components.append(component)
return components


Straightforward enough, but now we actually need to write our get_component function.

#First we setup a wrapper to the recursive part to keep track of the graph we will build
def get_component(graph, vertex): #assumes vertices .seen_before initiated
component=tig.UnDirGraph() #This graph can be modified by all the calls of the recursive function.
check=True #Checks to see if we've already seen this component before.
def get_component_recursive(graph, vertex, first=False):
if vertex.seen_before:
if first: #Confirms that we've seen this component already.
return False
return
else:
vertex.seen_before=True
for incident_edge in graph.get_incident_edges(vertex): #Now we get neighbors and incident edges.
if not incident_edge.seen_before:
incident_edge.seen_before=True
for target in incident_edge.ends:
if target != vertex:
component.create_edge([vertex, target])
get_component_recursive(graph, target)
check=get_component_recursive(graph, vertex, first=True)
if check==False: #In case the component has been seen before.
return check
else:
return component


And that’s that. Now let’s test it by taking the disjoint union of a linear graph and a complete graph.

G=tig.Complete(5)
H=tig.create_linear(number_vertices=5)
GunionH=tig.UnDirGraph(vertices=G.vertices+H.vertices, edges=G.edges.union(H.edges))
GunionH.plot()
get_connected_components(GunionH)[0].plot()
get_connected_components(GunionH)[1].plot()


Which produced the following in this order:

then and finally as expected! The code for this post is here, but to run it remember you will need tigraphs.