Consider the following directed graph G as shown in Figure 2.
Question
Consider the following directed graph G as shown in Figure 2.
Answer the following.
a) Is the graph strongly connected? Justify your answer.
b) Apply Depth-First Search (DFS) algorithm over this graph and find each vertex’s discovery and finishing time. Explore/visit the nodes in alphabetic order in cases where you have multiple options.
c) Mark all the edges of this graph accordingly.
d) How many strongly connected is the component the graph has? Justify your answer.
Explanation
a) A directed graph is considered to be strongly linked if each pair of vertices has a path in each direction. We can see that there are paths in all of the directions of each vertex in the presented graph. As a result, we can conclude that the graph in question is highly linked.
b) The DFS traversal for the above graph is as follows: We start at point A.
| Traversal | Stack |
| A | |
| A | B,D |
| A,D | B,C,F |
| A,D,F | B,C,G,H |
| A,D,F,H | B,C,G |
| A,D,F,H,G | B,C |
| A,D,F,H,G,C | B |
| A,D,F,H,G,C,B | E |
| A,D,F,H,G,C,B,E | I,J |
| A,D,F,H,G,C,B,E,J | I |
| A,D,F,H,G,C,B,E,J,I |
The traversal on DFS was A,D,F,H,G,C,B,E,J,I.
Starting and ending times are calculated as follows:
A (1,14)
B (12,13)
C (9,10)
D (2,11)
E (15,20)
F (3,8)
G (5,6)
H (4,7)
I (17,18)
J (16,19)
c) All the vertex marked with their starting and finishing time is: I (17,18) J (16,19)
d) Kosaraju’s Algorithm is used to obtain the strongly connected components. We start with the stack of the finishing time. In terms of completion time, the stack will be as follows:
| G | H | F | C | D | B | A | I | J | E |
Now, we reverse the arrows of the graph:
Then, until the stack is empty, we pop elements from it and perform DFS on them.
The components have popped, and their DFS is as follows:
Pop: E no DFS applicable
Pop: J no DFS applicable
Pop: I I-J-E
Pop: A no DFS applicable
Pop: B no DFS applicable
Pop: D D-B-A
Pop: C C-D-B-A
Pop: F no DFS applicable
Pop: H H-F
Pop: G G-H-F
As a result, the following graph has highly related components:
1) I-J-E
2) G-H-F
3) C-D-B-A
Also read, Make a flowchart of MICE (Meeting Incentive Convention Exhibition).
