Page 273 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes In Figure 13.4, 5 1,2 is a directed path; 1, 3, 5, 7, 6 is a directed path 1, 4, 5 is not a directed path.
There is no directed cycle in the above graph. You may verify the above statement. A digraph is
called strongly connected if there is a directed path from any vertex to any other vertex.
Consider the digraph given in Figure 13.6.

Figure 13.6: A Weakly Connected Graph

1

2

3

4 5

There does not exist a directed path from vertex 1 to vertex 4; also from vertex 5 to other vertices;
and so on. Therefore, it is a weakly connected graph. Let us make is strongly connected.

Figure 13.7: A Strongly Connected Graph

1

2

3

4 5

The, graph in Figure 13.7 a strongly connected graph. You may notice that we have added just
one arc from vertex 5 to vertex 3.

268 LOVELY PROFESSIONAL UNIVERSITY