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