Connected Components in Graph

by codecrucks · Published 19/01/2022 · Updated 08/06/2022

Connected Components

Connected Components in laymen is something that is connected all along. For example, all the states in the country are connected somehow. We can reach from one state to any other state by road. Although different countries may not be connected. There may or may not be transportation possible between countries. Similarly, the graph is connected if all its vertices are reachable from any other vertice in the graph.

Strongly Connected Components

A strongly connected component (SCC) is a classical application of Depth First Search. Strongly connected component of graph G = (V, E) is the maximal subset of vertices C ∈ V, such that there exists a path from u to v and v to u for each pair of vertices (u, v) in C. Vertices u and v are said to be strongly connected to each other.
Finding SCC requires two DFS traversals. The algorithm uses a transpose of the graph G. Graph GT is the transpose of the original graph G = (V, E), if GT = (V, ET) and ET = {(u, v) | (v, u) ∈ E}. By inverting the direction of edges, we can produce a transposition of the graph.
G and GT have the same connected components. Vertices u and v are reachable in G if and only if they are reachable from GT.
Using the following algorithm, we can find the SCC of graph G.

Algorithm for Strongly connected components

Algorithm

  STRONGLY_CONNECTED_COMPONENTS
// Input to algorithm is directed graph G

Call

DFS on G

Compute

finish time of every vertex u  V

Compute

GT

Call

DFS on GT, but in main loop of DFS consider the vertices in decreasing order of f[u]

Display

set of vertices of each DFS forest as separate SCC

Weather DFS traversal of graph produces tree or graph, depends on order of chosen vertices for the traversal. Finish time of any vertex in SCC₁ will always be greater than finish time of any other vertices in SSC₂.
Graph is shown with their DFS traversal

G^T of the above graph would be :

Call DFS on G^T but consider vertices in decreasing order of their finish time.

We get four strongly connected components: {A, B, E}, {C, D}, {F, G} and {H}

Complexity Analysis of Strongly Connected Components

DFS is called twice to find SCC. Running time of algorithm would be
O(|V| + |E|).

Graph Components

Articulation Point:

The articulation point is the vertex v ∈ V in graph G = (V, E), whose removal disconnects graph G.

Consider the above graph, removal of vertex A or B divides the graph in two components, thus A and B are the articulation points of this graph.

Bridge : A bridge in a graph G = (V, E) is an edge e ∈ E, whose removal disconnects the graph G. In above graph, edge AB is the bridge. Removal of AB leaves graph disconnected
Bi-connected component : A bi-connected component of graph G = (V, E) is maximum subset of edges such that any two edges in set belong to common cycle.
Euler tour : Euler tour of strongly connected graph G = (V, E) is the cycle that traverse each edge of G exactly once. Vertex may be visited more than once.

Finding Articulation Point:

The articulation point is the vertex v ∈ V in graph G = (V, E), whose removal disconnects graph G. Articulation point is the single point of failure in the network. It is useful to identify articulation points in the network to make the network more reliable.

Consider the above graph, removal of vertex A or B divides the graph in two components, hence A and B are the articulation points of this graph.
In DFS tree, vertex u is parent of vertex v, if v is discovered by u. In DFS tree, vertex v is articulation point if it satisfies any of the following conditions :
- Vertex u is root of the DFS tree and has at least two children.
- Leaf in DFS tree cannot be an articulation point.
- If vertex u is not root of DFS tree, and it has child v such that no vertex in sub tree has back edge to one of the ancestor of u.
These three observation leads to mathematical formulation for finding an articulation point as follow :

Algorithm

Algorithm

 ARTICULATION_POINT

for

each v ∈ V

pred[v] == NULL

then

	// if v is root

 | Adj[v] | ≥ 2

then

	// if root has more than one child
      print “v is articulation point”

end

els

for

each w in Adj(v)

Low[w] ≥ dfn [v]

then


	print “v is articulation point”

end

Applications of Articulation Point:

Articulation point is used to determine single point failure in network.
It is used to identify bi-connected components of graph.
Articulation point analysis is useful in graph representing communication network, example traffic routers, network wires, reservation hubs, protein bonds etc.

Example

Example: Find out articulation points for the following graph. Consider vertex A as the starting point.

Solution:

Figure (a), shows the order of vertices visited in DFS order. The back edges are labeled as B. Figure (b) shows the DFS tree with the dfn (depth-first visit number) number beside it.

DFN numbers — (a). Graph with dfn numbers and back edges

Low[u] = min{dfn[u], min{Low[w] / w is child of u}, min{dfn[w] / (u, w) is back edge}}

Low[A] = min{dfn[A], min{Low[B]}, – } // A does not have back edge

= min{1, Low[B], -}

= 1 // Low[u] cannot be less than one

Low[B] = min{dfn[B], min{Low[C]}, – }

= min{2, Low[C], -} …(1)

Low[C] = min{dfn[C], min{Low[G], Low[D]}, – }

= min{3, min{Low[G], Low[D]}, – } …(2)

Low[D] = min{dfn[D], min{Low[E]}, min{dfn[A]}}

= min{4, min{Low[E], 1 }

= 1 // Low[u] cannot be less than one

Put this value back in Equation (2)

Low[C] = min{3, min{Low[G], 1}, – }

= min{3, 1, -}

= 1 // C does not have back edge

Put value of Low[C] in Equation (1)

Low[B] = min{2, 1, -}

= 1

Low[E] = min{dfn[E], min{Low[F]}, – }

= min{5, min{Low[F]}, – } …(3)

Low[F] = min{dfn[F], – , min{dfn[D]}}

= min{6, -, 4 }

= 4 // F does not have any child

Put this value in Equation (3),

Low[E] = min{5, 4, – }

= 4 // E does not have back edge

Low[G] = min{dfn[G], – , – } // G does not have back edge or child

= min{7, -, – }

= 7

The following table describes dfn and Low values for each vertex.

Vertex u	A	B	C	D	E	F	G
dfn[u]	1	2	3	4	5	6	7
Low[u]	1	1	1	1	4	4	7

The root is articulation point it has more than one child.

Any other vertex u is an articulation point if and only if u has some child w such that Low[w] ≥ dfn[u].

Let’s check these conditions for all vertices.

A is root but it has only one child so it cannot be an articulation point
For B being an articulation point, it should satisfy the condition Low[C] ≥ dfn[B]. Here, Low[C] = 1 and dfn[B] = 2, so B is not an articulation point.
For C being an articulation point, it should satisfy the condition Low[G] ≥ dfn[C] or Low[D] ≥ dfn[C]. Here, Low[G] = 7 and dfn[C] = 3. It satisfies the condition. So C is an articulation point.
For D being an articulation point, it should satisfy the condition Low[E] ≥ dfn[D]. Here, Low[E] = 4 and dfn[D] = 4. It satisfies the condition. So D is an articulation point.
For E being an articulation point, it should satisfy the condition Low[F] ≥ dfn[E]. Here, Low[F] = 4 and dfn[E] = 5, so E is not an articulation point.
F and G are leaf of the tree, so they cannot be an articulation point.
For given graph, there are two articulation points, i.e. {C, D}.

Bi-Connected Component

Graph G is called bi-connected graph if it does not have any articulation point.
Consider following two graphs. Graph G₁ has two articulation points, i.e. A and B. So G₁ is not bi-connected component. Graph G₂ has no articulation point, so removal of any vertex does not factor graph in two parts. And hence, G₂ is bi-connected graph.

To disconnect a bi-connected graph, we must remove at least two vertices. If we remove vertex B and E from graph G2, it becomes disconnected.
Bi-connected component of graph G is the maximal biconnected sub graph.
Few observations :
- In graph, two different bi-connected components can share common vertex, but they cannot share common edge.
- Common vertex connecting biconnected components must be an articulation point of graph
- Articulation connects the biconnected components of graph. If graph has no articulation point, graph itself is biconnected component.

Consider the below graph :

This graph has two articulation points (shaded vertices), C and D. Removal of any vertex disconnects the graph in multiple components. This graph is having following biconnected components

Additional Reading: Articulation Point

Connected Components in Graph