Test by Bikram | Algorithms | Test 2 | Question: 13

Question

Which one of the following is a topological sort for the above graph?

• A. $1, 6, 2, 5, 3, 4$
• B. $4, 5, 6, 3, 2, 1$
• C. $2, 4, 5, 6, 3, 1$
• D. $6, 4, 5, 2, 1, 3$

Answer 1

We can start either from vertex 4 or from vertex 6 because only these 2 have no incoming edge.

Therefore option B , D will be considered 

Starting from vertex 4, next vertex can be 5 or 6.(order: 4)

considering vertex 5, next vertex can be 2 or 6 (order: 4,5)             |    considering vertex 6, next vertex can be 5.(order:4,6)

considering vertex 6, next vertex can be 2(order: 4,5,6)                   |    considering vertex 5, next vertex will be 2.(order:4,6,5)

                               or                                                                                 |    considering vertex 2, next vertex can be 1,3(order:4,6,5,2)

considering vertex 2,next vertex can be 6(order:4,5,2)                     |  finally correct order can be (4,6,5,2,3,1) or (4,6,5,2,1,3)

considering order 4,5,6 next vertex 2: order(4,5,6,2)                        | no option

considering order 4,5,2, next vertex 6 : order (4,5,2,6)                     |

considering order(4,5,6,2)or(4,5,2,6) ,next vertex can be 1,3           |

finally correct order can be (4,5,6,2,1,3) or (4,5,6,2,3,1) or (4,5,2,6,1,3),(4,5,2,6,3,1)----------no option

therefore option B is wrong

---

Starting from vertex 6, next vertex will be 4.(order: 6)

considering vertex 4, next vertex will be 5.(order: 6,4)

considering vertex 5, next vertex will be 2.(order: 6,4,5)

considering vertex 2, next vertex can be 1,3.(order: 6,4,5,2)

finally correct order can be (6,4,5,2,1,3) or  (6,4,5,2,3,1)

The correct ans is option D. (6, 4, 5, 2, 1, 3)

Answer 2

the simple stack operation will be given by :

starting from the vertex 4

stack:(3,1,2,5,4,6) or  (1,2,3,5,4,6)

after popping from the stack : 6 4 5 2 1 3   or 6 4 5 3 2 1

option (D) is correct

Note: In topological sorting,a vertex having maximum incoming edges always at the last position