Register

GO Classes DPP | GATE CS, DA | Algorithms | Topological Ordering

121 views
2 2 votes

Is the reverse postorder the only valid topological order for this graph?

  1. No
     
  2. Yes

1 Answer

0 0 votes

DFS gives the reverse postorder:

$3,6,0,5,2,1,4$

This is a valid topological ordering.

However, a DAG can have more than one valid topological ordering whenever some vertices do not have a precedence constraint between them.

In this graph, vertices $1$ and $2$ do not have an edge forcing one to occur before the other.

Therefore, another valid ordering is:

$3,6,0,5,1,2,4$

Check the relevant constraints:

$0$ still appears before $1$ and $2$.

$5$ still appears before $2$.

$1$ still appears before $4$.

All other directed-edge constraints also remain satisfied.

Thus, reverse DFS postorder gives a valid topological ordering, but it need not be the only one. 


Answer: A

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
105
105 views
GO Classes asked Aug 19
105 views
GO Classes DPP | GATE CS, DA | Algorithms | Topological Ordering
Which of the following is a valid topological ordering of the vertices in the given graph?$0 \rightarrow 6 \rightarrow 1 \rightarrow 7 \rightarrow 3 \rightarrow 5 \righta...
1 1 vote
1 1 answer
175
175 views
GO Classes asked Aug 19
175 views
GO Classes DPP | GATE CS, DA | Algorithms | Topological Sort
Can the above graph be topologically sorted?Yes No
1 1 vote
1 1 answer
108
108 views
GO Classes asked Aug 19
108 views
GO Classes DPP | GATE CS, DA | Algorithms | Distance vs Topological Order
Let $G=(V,E)$ be a dag, where each edge is annotated with some positive length. Let $s$ be a source vertex in $G$.Suppose we run Dijkstra's algorithm to compute the dista...
2 2 votes
1 1 answer
128
128 views
GO Classes asked Aug 19
128 views
GO Classes DPP | GATE CS, DA | Algorithms | DFS Tree in DAG
Suppose DFS is called on a DAG $G$, and the resulting DFS forest has a single tree. Then $G$ has exactly one source vertex.True False