Question

Find a topological sort for the graph in file hw9_dag_junctions.png.

Answer 1

Solution:-

The topological sort of the graph can be done by finding the indegree of every node, indegree of JCT A = 0 , indegree of JCT B = 1 , indegree of JCT C = 1 , indegree of JCT D = 2 , indegree of JCT E = 1 , indegree of JCT F = 2 , indegree of JCT G = 2. Now choosing the node having indegree as 0 (which is JCT A) and removing it due to which indegree of every node would be affected and now again choosing the node having indegree 0 (which is now JCT B) and removing it. Now after removing JCT B you have 2 nodes having indegree 0 that are JCT C , JCT D so anyone can be chosen and the process will be repeated until all the nodes have been removed. So the possible topological ordering can be
Ordering 1: JCT A, JCT B, JCT C, JCT D, JCT E, JCT F, JCT G

Ordering 2: JCT A, JCT B, JCT D, JCT C, JCT E, JCT F, JCT G

Ordering 3: JCT A, JCT B, JCT C, JCT E, JCT D, JCT F, JCT G