Today we shall use some of the algorithms described in the previous post and explore connectivity in graphs. Lets start with finding connected components in an undirected graph. In an undirected graph connected components are subgraphs in which any two vertices have a path between them. Lets take a look at the graph represented by the adjacency list shown below:

A: F B

B: G A F H

C: D I

D: C I

E: J

F: A B G

G: B H F

H: G B

I: D C

J: E

This will look the figure below:

In this case the vertices A,F,B,H,G is a connected component and so is C,D,I and E,J. Finding connected components in an undirected graph is relatively simple. You start with a vertex and do a depth or breadth first search to mark all the vertices that can be reached from that vertex with an index. Every vertex that can be reached is in that connected component. You increment the index and repeat the procedure with another unmarked vertex till there are no more vertices left to be marked. For the depth first search we shall use the class developed in the last post. The scala code that finds the connected components is shown below. Here is the link of the github repo where the code is stored.

package com.salil.graphs.connectivity import com.salil.graphs.search.GraphTraversal import com.salil.graphs.util.GraphUtil import com.salil.graphs.{Graph, Vertex} /** * Created by sasurendran on 12/25/2014. */ object ConnectedComponents extends App { if (args.isEmpty) print("Please pass a filename containing the graph details to the program") else new ConnectedComponents().work(args(0)) } class ConnectedComponents { val graphTraversal = new GraphTraversal() def work(fileName: String)={ val g = GraphUtil.getGraphFromAdjacencyList(fileName) println(connectedComponents(g,g.vertices.toList).map(x => x._1 + " -> " + x._2.mkString(",")).mkString("\n")) } def connectedComponents(g: Graph, unmarkedList: List[Vertex], i: Int = 0): List[(Int, List[Vertex])] = unmarkedList match { case Nil => Nil case head :: tail => val cc: List[Vertex] = graphTraversal.preOrderDFS(g, g.vertices, List(head)) (i, cc) :: connectedComponents(g, unmarkedList diff cc, i + 1) } }

In the code above we are once again using Scala’s pattern matching. If the unmarkedList is empty we return back a null list else we pick up the first element of the list and do a depth first traversal. We then add this list to a tuple along with the index and prepend it to the result of next method call. But this time we remove all the vertices found by the previous depth first traversal since they are already accounted for. We use the ‘diff’ operator which returns the difference between the two lists. The output of the above code is:

0 -> E,J 1 -> A,F,B,G,H 2 -> D,C,I

## Leave a Reply