1.8k views

Consider the directed graph below given. Which one of the following is TRUE?

1. The graph does not have any topological ordering.
2. Both PQRS and SRQP are topological orderings.
3. Both PSRQ and SPRQ are topological orderings.
4. PSRQ is the only topological ordering.
edited | 1.8k views

The C option has been copied wrongly
C. Both PSRQ and SPRQ are topological orderings

1. Apply DFS by choosing P or S as starting vertices
2. As the vertex gets a finishing time assign it to the head of a linked list
edited by
+2

Hi,

I think, here  it (http://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/) should be used for getting all possible answer.

In general for getting one possible answer, approach (DFS method ) proposed by you looks good.

+3

Topological Sort

0

"The C option has been copied wrongly "

What is meaning of this line the above solution.

choose vertex in the graph which has 0 indegree . now see graph has such two vertices ie P,S so we can start topological sort either from vertex P or from S .

lets first start from vertex P now remove this vertex from graph ,we left with three vertices named asQ,S,R from these vertices see which vertex has INDEGREE 0,S vertex HAS indegree 0 therefore sequence is P,S,R,Q

repeat the above step from vertex S we get sequence as S,P,R,Q

edited
0
Typo:- in first paragraph

"we can start totpological sort either from vertex P or from Q . "

It sud be P or from S
0
Nice explanation, Thanks
The graph doesn't contain any cycle, so there exist topological ordering. P and S must appear before R and Q because there are edges from P to R and Q, and from S to R and Q.