## Topological sort

**Topological sort **: an ordering of the vertices in a directed acyclic graph, such that:

If there is a path from ** u** to

**, then**

*v***appears after**

*v***in the ordering.**

*u*The graphs must be

**directed:**otherwise for any edge (u,v)

there could be a path from

**to**

*u***and also from**

*v***to**

*v***,**

*u*and hence they cant be ordered.

The graphs must be

**acyclic**: otherwise for any two vertices

**and**

*u***on a cycle**

*v***could precede**

*u***and**

*v***could precede**

*v*

*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.

**Algorithm**

- 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.

An Example

- Computing the indegrees:

V2: 1

V3: 2

V4: 2

V5: 2

- Find a vertex with indegree 0: V1
- Output V1 , removing V1 and updating the indegrees:

Remove edges: (V1,V2) , (V1, V3) and (V1,V4)

Updated indegrees:

V3: 1

V4: 1

V5: 2

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|^{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
}

**Improved algorithm**

- 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.

**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|^{2})

^{2})