The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+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 in Algorithms by Veteran (112k points)
edited by | 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 by
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:

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

44,254 questions
49,750 answers
164,111 comments
65,848 users