Find a topological ordering for the following graph Solution

Find a topological ordering for the following graph.

Solution

As the topological Ordering is not unique , there can be more than one Topological Ordering of the given Graph : -

Calculate Indegrees of All Node : Our algorithm will be we will pick Nodes having less Indegree and if there is a tie , tie will be broken by picking any one of them, hence the ordering is not unique .

Indegree (s) = 0
Indegree (A) = 2
Indegree (G) = 1
Indegree (D) = 2
Indegree (B) = 1
Indegree (H) = 1
Indegree (E) = 4
Indegree (I) = 2  
Indegree (F) = 2
Indegree (C) = 3
Indegree (t) = 3


Steps :
1. Start with Sink Node (Having Indegree as 0) , As there is no incoming edge in s so first Node is s.

2. Remove all edges associated with S like (s,A) (s,G) (s,D) , Now
Indegree (A) = 1 , Indegree (G) = 0 , Indegree (D) = 1 , Indegree (B) = 1, Indegree (H) = 1
Indegree (E) = 4 , Indegree (I) = 2 , Indegree (F) = 2 ,Indegree (C) = 3 ,Indegree (t) = 3 . So Pick G

3. Remove all outgoing edges of G , (G,H) (G,D) (G,E)..
Indegree (A) = 1 , Indegree (D) = 0 , Indegree (B) = 1, Indegree (H) = 0
Indegree (E) = 3 , Indegree (I) = 2 , Indegree (F) = 2 ,Indegree (C) = 3 ,Indegree (t) = 3 . We can pick D or H we will pick any one . Lets say H

4.Remove all outgoing edges of H , (H,E) (H,I) ..
Indegree (A) = 1 , Indegree (D) = 0 , Indegree (B) = 1
Indegree (E) = 2 , Indegree (I) = 1 , Indegree (F) = 2 ,Indegree (C) = 3 ,Indegree (t) = 3 . We can pick D Now

5.Remove all outgoing edges of D , (D,E) (D,A) ..
Indegree (A) = 0 , Indegree (B) = 1
Indegree (E) = 1 , Indegree (I) = 1 , Indegree (F) = 2 ,Indegree (C) = 3 ,Indegree (t) = 3 . We can pick A

6. Remove all outgoing edges of A , (A,B) (A,E) ..
Indegree (B) = 0 Indegree (E) = 0 , Indegree (I) = 1 , Indegree (F) = 2 ,Indegree (C) = 3 ,Indegree (t) = 3 . We can pick E Now

7. Remove all outgoing edges of E , (E,C) (E,F) (E,I)..
Indegree (B) = 0 Indegree (I) = 0 , Indegree (F) = 1 ,Indegree (C) = 2 ,Indegree (t) = 3 . We can pick I

8. Remove all outgoing edges of I , (I,F) (I,t)..
Indegree (B) = 0 , Indegree (F) = 0 ,Indegree (C) = 2 ,Indegree (t) = 2 . We can pick F

9. Remove all outgoing edges of F , (F,t) (F,C)
Indegree (B) = 0 Indegree (C) = 1 ,Indegree (t) = 1 . We can pick B

10. Remove all outgoing edges of B ,(B,C)
Indegree (C) = 0 ,Indegree (t) = 1 . We can pick C

11. Remove all outgoing edges of C ,(C,t)
Indegree (t) = 0 . We can pick t

So the sequence is s,G,H,D,A,E,I,F,B,C,t

Thanks, I hope it clarifies