Sccd and topological sorting

PPT on "SCCD and topological sorting"

1. Strongly Connected Component
Decomposition (SCCD)


Dr. AMIT KUMAR @JUET

2. Strongly Connected Component Decomposition
(SCCD)

•The third useful application of DFS is to perform a strongly
connected component decomposition
•Given a directed graph G(V,E), the strongly connected
component decomposition determi nes sets of
vertices C
i ∈ V such that
For every pair u,v ∈ C
i ⇒ u ↝ v and v ↝ u.
•In otherwords, it separates the graph into subsets of vertices
that are mutually reachable from each other.
Dr. AMIT KUMAR @JUET

3. Strongly Connected Component Decomposition
(SCCD)

•Define the transpose of a graph



•i.e. it is the original graph with all edges reversed. The
transpose graph can be created in O(V+E) time if the graph is
represented as an adjacency list.
•It can then be shown that u and v are mutually reachable
from each other in G if and only if u and v are mutually
reachable from each other in G
T
.


Dr. AMIT KUMAR @JUET

4. Strongly Connected Component Decomposition
(SCCD)

Thus the procedure for finding strongly connected
components is as follows:

1.Run DFS on G to find u.f's ⇒ O(V+E)
2.Compute G
T
⇒ O(V+E)
3.Run DFS on G
T
considering the vertices in decreasing
order of u.f's from step 1 ⇒ O(V+E)

The resulting depth-first trees from step 3 are the strongly
connected components of G. Furthermore, the running time
of SCCD is Θ(V+E).


Dr. AMIT KUMAR @JUET

5. Strongly Connected Component Decomposition
(SCCD)

Example
Consider the following directed graph

Dr. AMIT KUMAR @JUET

6. Strongly Connected Component Decomposition
(SCCD)

Example
Step 1 - Run DFS on G
Running DFS on G (starting at vertex 1 and taking the vertices in numerical
order) gives
Thus the vertices in decreasing order of u.f is {1,4,2,5,3}.
Dr. AMIT KUMAR @JUET

7. Strongly Connected Component Decomposition
(SCCD)

Example
Step 2 - Compute G
T

Dr. AMIT KUMAR @JUET

8. Strongly Connected Component Decomposition
(SCCD)

Example
Step 3 - Run DFS on G
T
Running DFS on G
T
taking the vertices in the order {1,4,2,5,3}
Dr. AMIT KUMAR @JUET

9. Strongly Connected Component Decomposition
(SCCD)

Example
The depth-first trees from step 3 are
Hence the strongly connected components are {1,2,3,4} and {5}.
Dr. AMIT KUMAR @JUET

10. Topological Sorting

•A second application of DFS is to create a directed ordering of
nodes, e.g. task dependencies. This can be done based on an
important theorem that can be shown using DFS

•A directed graph is acyclic (i.e. a DAG) if and only if a DFS
produces no back edges. Thus DFS can be used to test
whether or not a graph has cycles on O(V+E) time.

Dr. AMIT KUMAR @JUET

11. Topological Sorting


•Given a directed acyclic graph G (i.e. DAG, which can be
determined via DFS), running DFS on G and sorting the
vertices by decreasing finishing times produces a sequential
ordering of the vertices.

•This can be seen since for any edge (u,v) in the depth-first
tree, u must appear before v in the sorted list (since G is a
DAG we know there are no back edges).

Dr. AMIT KUMAR @JUET

12. Topological Sorting

•For example,
If the vertices represent a set of tasks with edges representing
dependencies between tasks, a topological sort can be used
to find a critical path.
Since DFS runs in Θ(V + E), topological sort runs in the same
time
Dr. AMIT KUMAR @JUET