0
8.4kviews
Explain Topological Sorting with example
2
493views
1. Topological sort: It id defined as an ordering of the vertices in a directed acyclic graph, such that if there is a path from u to v, then v appears after u in the ordering.

2. Types of graphs:

a. The graphs should be directed: otherwise for any edge (u,v) there would be a path from u to v and also from v to u, and hence they cannot be ordered.

b. The graphs should be acyclic: otherwise for any two vertices u and v on a cycle u would precede v and v would precede u.

3. The algorithm for topological sort uses "indegrees" of vertices.

4. Complexity of this algorithm: O(|V|2), |V| - the number of vertices.

5. Algorithm

1. Compute the indegrees of all vertices
2. Find a vertex U with indegree 0 and print it (store it in the ordering) If there is no such vertex then there is a cycle and the vertices cannot be ordered. Stop.

3. Remove U and all its edges (U,V) from the graph.

4. Update the indegrees of the remaining vertices.
5. Repeat steps 2 through 4 while there are vertices to be processed.
6. Example

        Compute the indegrees:

V1: 0
V2: 1
V3: 2
V4: 2
V5: 2
Find a vertex with indegree 0: V1
Output V1 , remove V1 and update the indegrees:

Sorted: V1
Remove edges: (V1,V2) , (V1, V3) and (V1,V4)
Updated indegrees:

V2: 0
V3: 1
V4: 1
V5: 2

The process is depicted in the following table:


    One possible sorting: V1, V2, V4, V3, V5
Another sorting: V1, V2, V4, V5, V3