Dfs Search Trees and Strongly Connected Components

Full graph K nis correct: C 2 n .(n  1)

The edge and degree of every vertex are n - 1.

K 3 K 4 K 5

Figure 62: Full graph

4.3.2. Graph closure:

With graph G = (V, E), people build graph G' = (V, E') which also includes the vertices of G and the edges are built as follows: (here the convention is that there is always a path between u and u)

Between vertices u and v of G' there is an edge  Between vertices u and v of G there is a path. The graph G' constructed like this is called the closure of the graph G.

From the definition of a complete graph, we can easily deduce that a complete graph is always connected, and from the definition of a connected graph, we can also easily deduce that:

A simple undirected graph is connected if and only if its closure is a complete graph.

A simple undirected graph has k connected components if and only if its closure has k completely connected components.

Figure 63: Undirected simple graph and its closure

Since it is quite easy to check whether a graph is complete or not (counting the number of edges, for example), the idea was to check the connectedness of the graph by checking the completeness of the closure. The problem is that there must be an algorithm to construct the closure of a given graph, and one of those algorithms is:

4.3.3. Warshall algorithm

Warshall algorithm - named after Stephen Warshall who described it in 1960, sometimes also called Roy-Warshall algorithm because Roy also described it in 1959. The algorithm can be described very briefly:

From the adjacency matrix A of a simple undirected graph G (a ij = True if (i, j) is an edge of G) we will modify A so that it becomes the adjacency matrix of the closure by: For every vertex k considered in order from 1 to n, we consider all pairs of vertices (u, v): if there is an edge connecting (u, k) (a uk = True) and there is an edge connecting (k, v) (a kv = True) then we add the edge (u, v) ourselves if it does not exist (let a uv := True) . This idea is based on a simple observation as follows: If from u there is a path to k and from k there is a path to v then of course from u there will be a path to v.

With n being the number of vertices in the graph, we can write the Warshall algorithm as follows:

for k := 1 to n do for u := 1 to n do

if a[u, k] then

for v := 1 to n do

if a[k, v] then a[u, v] := True ;

for k := 1 to n do for u := 1 to n do

for v := 1 to n do

a[u, v] := a[u, v] or a[u, k] and a[k, v];

Proving the correctness of the algorithm requires revisiting the theories of transitive closures and connected relations, which we will not present here. It is noted that although Warshall's algorithm is very easy to implement, its computational complexity is quite large (O(n 3 )).

Below, we will try to implement Warshall's algorithm to find the closure of a simple undirected graph and then count the number of connected components of the graph:

The algorithm installation will go through the following steps:

Enter the adjacency matrix A of the graph (Note here A[v, v] is always considered True for  v) Use Warshall algorithm to find the closure, then A is the adjacency matrix of the graph closure

Based on the adjacency matrix A, vertex 1 and its adjacent vertices will belong to the first connected component; for any vertex u that is not adjacent to vertex 1, then u and its adjacent vertices will belong to the second connected component; for any vertex v that is not adjacent to both vertex 1 and vertex u, then v and its adjacent vertices will belong to the third connected component, etc.

Input: text file GRAPH.INP

 Line 1: Contains the number of vertices n (  100) and the number of edges m of the graph separated by at least one space

 The next m lines, each containing a pair of numbers u and v separated by at least one space, represent an edge (u, v)

Output: text file CONNECT.OUT, listing the connected components

GRAPH.INP	CONNECT.OUT
12 9	Connected Component 1:
1 3	1, 2, 3, 4, 5,
1 4	Connected Component 2:
1 5	6, 7, 8,
2 4	Connected Component 3:
6 7	9, 10, 11, 12,
6 8
9 10
9 11
11 12

Maybe you are interested!

P_4_04_1.PAS * Warshall algorithm lists connected components

program Connectivity; const

InputFile ='GRAPH.INP'; OutputFile ='CONNECT.OUT'; max = 100;

var

a: array[1..max, 1..max] of Boolean; {Adjacency matrix of the graph}

Free: array[1..max] of Boolean; {Free[v] = True v is not listed in any interconnected components}

k, u, v, n: Integer;

Count: Integer;

fo: Text;

procedure Enter; {Enter graph}

var

i, u, v, m: Integer; fi: Text;

begin

FillChar(a, SizeOf(a), False); Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, m);

for v := 1 to n do a[v, v] := True; {Of course from v there is a path to v itself}

for i := 1 to m do begin

ReadLn(fi, u, v);

a[u, v] := True;

a[v, u] := True; end;

Close(fi); end;

begin

Enter;

{Warshall Algorithm}

for k := 1 to n do for u := 1 to n do

for v := 1 to n do

a[u, v] := a[u, v] or a[u, k] and a[k, v]; Assign(fo, OutputFile); Rewrite(fo);

Count := 0;

FillChar(Free, n, True); {No vertices are listed in any connected components}

for u := 1 to n do

if Free[u] then {For a vertex u not yet listed in any connected component}

begin

Inc(Count);

WriteLn(fo, 'Connected Component ', Count, ': '); for v := 1 to n do

if a[u, v] then {Consider the vertices adjacent to u (on the closure)}

begin

Write(fo, v, ', '); {List that vertex into the connected component containing u}

Free[v] := False; {List which vertex to mark}

end;

WriteLn(fo);

end;

Close(fo);

end

4.4. STRONGLY INTERCONNECTED COMPONENTS

For directed graphs, people are interested in the problem of testing for strong connectivity, or more generally: the problem of enumerating the strongly connected components of a directed graph. For that problem, we have a quite effective method based on the Depth First Search algorithm.

4.4.1. Analysis

Add a vertex x to the graph and connect x to all remaining vertices of the graph by directed arcs. Then the depth-first search process starting from x can be viewed as a process of building a depth-first search tree (DFS tree) with root x.

procedure Visit(u  V); begin. begin

<Add u to DFS search tree>; for (  v: (u, v)  E) do

if <v is not in DFS tree> then Visit(v);

end;

begin

<Add to the graph vertex x and directed arcs (x, v) for every v>;

<Initialize DFS search tree :=  >; Visit(x);

end

Notice the recursive vertex visiting procedure Visit(u). This procedure considers all vertices v connecting from u, if v has not been visited then follow that arc to visit v, that is, add the arc (u, v) to the DFS search tree. If v has been visited then there are three possibilities for the positions of u and v in the DFS search tree:

v is an ancestor of u, that is, v was visited before u and the procedure Visit(u) is chained.

recursively called from the procedure Visit(v). The arc (u, v) is then called a back edge.

v is a descendant of u, meaning u was visited before v, but the Visit(u) procedure, after recursing in another direction, has already called Visit(v). So when the recursive chain returns to the Visit(u) procedure, it will see that v has been visited and will not visit again. The arc (u, v) is then called a forward edge.

v belongs to a branch of a previously visited DFS tree, i.e. there will be a vertex w visited before both u and

v. The procedure Visit(w) called first will turn to a certain branch to visit v first, then when going back, turn to another branch to visit u. The arc (u, v) is then called a cross edge .

(Unfortunately, the English-Vietnamese computer terminology dictionary is so poor that it is impossible to find similar words.)

equivalent to the above terms. We can understand through examples).

3rd

1 st

2nd v

5 th

6 th

4 th

7 th

1 st

2nd

u 5 th

6 th

4 th

1 st

2nd

5 th

u 6 th

4 th

Case 1: v is the predecessor of u (u, v) is the inverse arc

Case 2: v is a descendant of u (u, v) is a straight arc

Case 3: v is on the DFS branch that has been visited before u (u, v are diagonal arcs)

Figure 64: Three types of arcs outside the DFS tree

We notice a characteristic of the depth-first search algorithm, the algorithm not only visits the vertices, it also visits all the arcs. In addition to the arcs in the search tree, the remaining arcs can be divided into three types: reverse arcs, forward arcs, and diagonal arcs.

4.4.2. DFS search tree and strongly connected components

Theorem 1:

If a, b are two vertices in a strongly connected component C, then for every path from a to b as well as from b to a. All intermediate vertices on that path must belong to C.

Prove

If a and b are two vertices in C, then there is a path from a to b and another path from b to a. It follows that for a vertex v on the path from a to b, a can reach v , v can reach b, and b has a path to a, so v can also reach a . So v is in the strongly connected component containing a, that is, v  C. Similarly, for a vertex on the path from b to a.

Theorem 2:

For any strongly connected component C, there will exist a vertex r  C such that every vertex of C belongs to the original DFS branch r.

Prove:

First, recall that a strongly connected component is a strongly connected subgraph of the original graph that satisfies the maximality property, i.e. adding another set of vertices to the component will destroy the strong connectivity.

Among the vertices of C, choose r as the first vertex visited by the depth-first search algorithm. We will prove that C lies in the original DFS branch r. Indeed: for any vertex v of C, since C is strongly connected, there must exist a path from r to v:

(r = x 0 , x 1 , …, x k = v)

From Theorem 1, all vertices x 1 , x 2 , …, x k belong to C so they will have to be visited after vertex r. When the Visit(r) procedure is called, all vertices x 1 , x 2 …, x k =v are not visited; because the Visit(r) procedure will list all vertices

all unvisited vertices from r by constructing the root branch r of the DFS tree, so the vertices x 1 , x 2 , …, x k = v will belong to the root branch r of the DFS tree. Since we choose v to be any vertex in C, we have what to prove.

The vertex r in the theorem proof - the vertex visited before all other vertices in C - is called the key of the component C. Each strongly connected component has only one key. In terms of position in the DFS search tree, the key of a connected component is the vertex that is highest relative to other vertices in that component , or in other words: the predecessor of all vertices in that component .

Theorem 3:

Always find a key vertex a satisfying: The depth-first search process starting from a cannot visit any other key . (That is, the original DFS branch a does not contain any key other than a) for example, we choose a to be the last key visited in a recursive chain or choose a to be the key visited after all other keys. With such a key a, the vertices belonging to the original DFS branch a are the strongly connected components containing a.

Prove:

For every vertex v in the original DFS branch a, let b be the key of the strongly connected component containing v. We will prove that a  b. Indeed, by Theorem 2, v must be in the original DFS branch b. So v is in both the original DFS branch a and the original DFS branch b. Suppose by contradiction that a  b, then there are two possibilities:

Possibility 1: The root DFS branch a contains the root DFS branch b, which means that Visit(b) will be called by Visit(a), which contradicts the assumption that a is a node whose depth-first search starting from a does not visit any other nodes.

Possibility 2: The original DFS branch a is inside the original DFS branch b, which means that a is on a path from b to v. Since b and v belong to the same strongly connected component, by Theorem 1, a must also belong to that strongly connected component. So this strongly connected component has two keys a and b. This is absurd.

According to Theorem 2, we have a strongly connected component containing a in the original DFS branch a . According to the above proof, we have: Every vertex in the original DFS branch a is in the strongly connected component containing a . Combining them, we get: The original DFS branch a is the strongly connected component containing a.

4.4.3. Tarjan's algorithm (RETarjan - 1972)

Choose u as the node from which the depth-first search does not visit any other nodes, choose the first strongly connected component as the root DFS branch u. Then remove the root DFS branch u from the DFS tree, find another node v whose root DFS branch v does not contain any other nodes, and choose the second strongly connected component as the root DFS branch v. Similarly for

The third, fourth, etc. strongly connected components can be visualized as Tarjan's algorithm "breaking" the DFS tree at the nodes to obtain discrete branches, each of which is a strongly connected component.

Figure 65: Tarjan's algorithm "breaks" the DFS tree

Such a long presentation, but the most important thing now comes down to: How to check if a certain vertex v is a key or not?

Notice the DFS branch rooted at some vertex r.

Comment 1 :

If from the vertices of the original branch r there are no reverse or diagonal arcs going out of that branch, then r is a key . This is easy to understand because it means that from r, following the arcs of the graph will only reach the vertices of that branch. So:

The strongly connected component contains r  The set of vertices that can be reached from r = Original DFS branch r so r is a key.

Comment 2 :

If from a vertex v of the original DFS branch r there is a reverse arc to a vertex w that is a predecessor of r, then r is not a key . Indeed: because of the cycle (w  r  v  w), w, r, v belong to the same strongly connected component. But w is visited before r, which contradicts the way to determine the key (See Theorem 2 again)

Comment 3 :

The tricky problem here is that if from a vertex v of the root DFS branch r, there is a diagonal arc leading to another branch. We will set up the strongly connected component enumeration algorithm right in the Visit(u) procedure, when vertex u has been visited , that is, when the other vertices of the root DFS branch u have been visited and the recursive visit process returns to Visit(u). If u is a key, we announce that the root DFS branch u is a strongly connected component containing u and immediately remove the vertices belonging to that component from the graph as well as from the DFS tree. The correctness of this method can be proven, because if the branch

If the original DFS u contains another key u', then u' must have finished scanning before u and the original DFS branch u' has been eliminated. Furthermore, it can be proven that, when the algorithm proceeds as above, if from a vertex v of an original DFS branch r there is a diagonal arc leading to another branch, then r is not a key .

To prove this, we rely on the property of the DFS tree: a diagonal arc will connect from a branch to a previously visited branch, but there will never be a diagonal arc going to a later visited branch. Suppose there is a diagonal arc (v, v') going from v  root DFS branch r to v'  root DFS branch r, let r' be the key of the connected component containing v'. According to the above property, v' must be visited before r, so r' must also be visited before r . There are two possibilities: If r' belongs to the DFS branch that was visited before r, then r' will be finished visiting before visiting r, that is, when visiting r and also later when visiting v, the original DFS branch r' will be canceled, the diagonal arc (v, v') will not be considered anymore.

If r' is a predecessor of r, then we have r' reaching r , v is in the original DFS branch of r so r can reach v , v can reach v' because (v, v') is an arc, v' can reach r' because r' is a key of the strongly connected component containing v'. We can establish a cycle (r'  r  v  v'  r'), which implies that r' and r belong to the same strongly connected component, r' is already a key so r cannot be a key anymore.

From the three observations and the program implementation as in observation 3, we have: Vertex r is a key if and only if there does not exist a reverse arc or a diagonal arc connecting a vertex in the original DFS branch r with a vertex outside that branch, or in other words: r is a key if and only if there does not exist an arc connecting a vertex in the original DFS branch r to a previously visited vertex r .

Here is a very clever implementation, just modify the Visit procedure above a little bit and we have this method. Its content is to number the vertices from the first visited vertex to the last visited vertex. Define Numbering[u] as the order number of vertex u according to that numbering method. We also calculate Low[u] as the smallest Numbering value among the vertices that can be reached from a vertex v of the original DFS branch u by an arc (assuming that u has a pseudo-arc connected to u itself).

Specifically, the way to minimize Low[u] is as follows:

In the Visit(u) procedure, we first number the vertex u and initialize the assignment.

Low[u] := Numbering[u] (u has an edge to u itself) Consider all vertices v connecting from u:

If v has been visited, we minimize Low[u] according to the formula:

New Low[u] := min( Old Low[u] , Numbering[v]).

If v is not visited, we recursively visit v, then minimize Low[u] according to the formula:

New Low[u] := min( Old Low[u] , Low[v]) It is easy to prove the correctness of the calculation formula.

When we finish browsing a vertex u (preparing to exit the Visit(u) procedure), we compare Low[u] and Numbering[u]. If Low[u] = Numbering[u], then u is a key, because there is no edge connecting from a vertex