Topological sort

Topological sort

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.

Types of graphs:
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.

The ordering may not be unique:

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.

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.

1. Remove U and all its edges (U,V) from the graph.
2. Update the indegrees of the other vertices.
3. Repeat steps 2 through 4 while there are vertices to be processed.
   
   An Example

 

1. Computing the indegrees:

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

1. Find a vertex with indegree 0: V1
2. Output V1 , removing V1 and updating the indegrees:

Sorted: V1
Remove edges: (V1,V2) , (V1, V3) and (V1,V4)
Updated indegrees:V2: 0
V3: 1
V4: 1
V5: 2The process is represented in the following table:

	Indegree
Sorted à		V1	V1,V2	V1,V2,V4	V1,V2,V4,V3	V1,V2,V4,V3,V5
V1	0
V2	1	0
V3	2	1	1	0
V4	2	1	0
V5	2	2	1	0	0

 

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

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

Complexity of this algorithm: O(|V|²), |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|²

Improved algorithm

After the initial scanning to find a vertex of degree 0, we need to scan only those vertices whose updated indegrees have become equal to zero.

1. Store all vertices with indegree 0 in a queue
2. get a vertex U and place it in the sorted sequence (array or another queue).
3. For all edges (U,V) update the indegree of V, and put V in the queue if the updated indegree is 0.
4. Perform steps 2 and 3 while the queue is not empty.

Complexity

 

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|)
Matrix: O(|V|²)

Note that if the graph is complete |E| = O(|V|²)