Topological Ordering works on the concept of in-degree and out-degree.
In-degree means how many edges are coming into the vertex.
Out-degree means how many edges are going out of the vertex.
Also, note that only DIRECTED ACYCLIC GRAPHS (DAG) have topological orderings. Now, let us look at our graph.
We start by writing in-degree of all the vertices.
VERTEX | INDEGREE |
a | 0 |
b | 1 |
c | 1 |
d | 1 |
e | 2 |
We always add nodes with in-degree 0 to our graph. So, in our topological ordering, we place a first.
TOPOLOGICAL ORDERING: a
Next, we remove a completely from the graph.
Now, we will write the indegree of the remaining vertices.
VERTEX | INDEGREE |
b | 0 |
c | 0 |
d | 1 |
e | 2 |
Now, we can add b as well as c to our graph. This results in two different topological orderings.
TOPOLOGICAL ORDERING 1: a→b
TOPOLOGICAL ORDERING 2: a→c
Now, we will consider two cases. In the first case, let us remove b.
Now, we get the following in degrees.
VERTEX | INDEGREE |
c | 0 |
d | 1 |
e | 1 |
So, topological ordering 1 is a→b→c→d→e
If we remove c, however, we get,
VERTEX | INDEGREE |
b | 0 |
d | 0 |
e | 2 |
Hence, we can say that topological ordering in case 2 can be one of the following:
a→c→b→d→e
a→c→d→b→e
Hence, three topological orderings are possible.
a→b→c→d→e
a→c→d→b→e
a→c→b→d→e