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 , the depth first search will be .
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 , for each vertex , let denote the number of vertices in the connected component containing , and for the edges.
Let 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 time if we’ve already encountered the vertex’s component, meaning that the final time will be .
Let’s see the python 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).plot() get_connected_components(GunionH).plot()