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:
            component.add_vertex(vertex)
            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:GunionH

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: