Topological sort : 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.
The graphs must be directed: otherwise for any edge (u,v)
there could be a path from u to v and also from v to u,
and hence they cant be ordered.
The graphs must be acyclic: otherwise for any two vertices u and v on a cycle
u could precede v and v could precede u.
V1, V2, V3, V4 and V1, V3, V2, V4 are legal orderings
Degree of a vertex U: the number of edges (U,V) – outgoing edges
Indegree of a vertex U: the number of edges (V,U) – incoming edges
The algorithm for topological sort uses “indegrees” of vertices.
- Compute the indegrees of all vertices
- 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.
- Remove U and all its edges (U,V) from the graph.
- Update the indegrees of the other vertices.
- Repeat steps 2 through 4 while there are vertices to be processed.
- Computing the indegrees:
- Find a vertex with indegree 0: V1
- Output V1 , removing V1 and updating the indegrees:
Remove edges: (V1,V2) , (V1, V3) and (V1,V4)
One possible sorting: V1, V2, V4, V3, V5
Another sorting: V1, V2, V4, V5, V3
Complexity of this algorithm: O(|V|2), |V| – the no of vertices.
To find a vertex of indegree 0 we scan all the vertices – |V| operations.
We do this for all vertices: |V|2
- Store all vertices with indegree 0 in a queue
- get a vertex U and place it in the sorted sequence (array or another queue).
- For all edges (U,V) update the indegree of V, and put V in the queue if the updated indegree is 0.
- Perform steps 2 and 3 while the queue is not empty.
The no. of operations is O(|E| + |V|), where |V| – no. of vertices, |E| – number of edges.
How many operations are needed to compute the indegrees?
Depends on the representation:
Adjacency lists: O(|E|)