+21 votes
1.5k 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.
asked
edited | 1.5k views

## 3 Answers

+21 votes
Best answer

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
3. The linked list is your required topological ordering
answered by (457 points)
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.

+2

Topological Sort

+21 votes

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

answered by Boss (20.7k points)
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
+5 votes
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.

answer is c
answered by Loyal (8.7k points)
Answer:

+17 votes
3 answers
1
+25 votes
6 answers
2
+6 votes
4 answers
3
+28 votes
2 answers
4
+21 votes
2 answers
5
+10 votes
2 answers
6
+13 votes
2 answers
7