**1 Answer**

written 5.7 years ago by | modified 5.7 years ago by |

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.

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.

The algorithm for topological sort uses "indegrees" of vertices.

Complexity of this algorithm: O(|V|2), |V| - the number 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 remaining vertices.
- Repeat steps 2 through 4 while there are vertices to be processed.
- 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
```