The Gateway to Computer Science Excellence
+20 votes

Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.

Which of the following is not a topological ordering?

  1. $1$ $2$ $3$ $4$ $5$ $6$
  2. $1$ $3$ $2$ $4$ $5$ $6$
  3. $1$ $3$ $2$ $4$ $6$ $5$
  4. $3$ $2$ $4$ $1$ $6$ $5$
in Algorithms by Boss (21.5k points)
edited by | 2k views
pls explain again
Only 4 topological orders exist for this graph:





4 Answers

+24 votes
Best answer

Go with vertex with indegree 0. Remove the vertex with all edges going from it. Repeat the procedure.

We see that $3$ cannot come at first because indegree is not $0$. So, D is the answer here.

ALL other options are in Topological order.

Only $1$ and $4$ order matter for this question.

by Veteran (63k points)
edited by
+5 votes

choose vertex in the graph which has 0 indegree. now see graph has vertex 1 with 0 indegree so remove this along with its edges.

after that there are two possibilities remove one by one either vertex 2 or 3. after that there is one possibility remove vertex 4 .after that two possibilities remove either vertex 5 or 6 one by one. the order of vertex we get is called  topological ordering.

here a,b,c are correct but d is wrong. so d is ans

by Active (4.5k points)
+5 votes
The arrow represents which comes after or which comes before i.e a-->b means that a must come before b or b must come after a

Now jump to the given diagram, as it is clear that

i) 2 and 3 must come after 1

ii) 4 must come after 2 and 3 so obvious comes after 1 also

iii) 5 and 6 must come after 4 so obvious must comes after 1,2 and 3 also.

Now follow this step and check with the given options

Hence option D is not correct as 3 does not comes before 1 (point no. i)

NOTE: (2,3) and (5,6) are at same level, therefore their positions can be interchange as in option (A and B) position of 2 and 3 interchanged.
by Loyal (7.3k points)
+3 votes
choose vertex in the graph which has 0 indegree. now see graph has vertex 1 with 0 indegree so remove this along with its edges.    See option D) it is starting with vertex 3 which is not having indegree as zero so it can not be answer ..

Therefore option D)
by Active (4.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,397 answers
105,456 users