Explain Topological Sorting with example
1 Answer
  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

enter image description here

        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:

enter image description here

    One possible sorting: V1, V2, V4, V3, V5
    Another sorting: V1, V2, V4, V5, V3
Please log in to add an answer.