GATE CSE 2014 | Set 1 | Question: 13

Question

Consider the directed graph below given. 

Which one of the following is TRUE?

• A. The graph does not have any topological ordering.
• B. Both PQRS and SRQP are topological orderings.
• C. Both PSRQ and SPRQ are topological orderings.
• D. PSRQ is the only topological ordering.

Comments

The answer is clearly option C. This is because S and P dont have any prerequisites i.e. no incoming edges so they can be visited in any order but before R and Q as these edges are dependent on P and S. Also Q should be visited after R only. Hence both PSRQ and SPRQ are the correct answers.

Answer 1

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

Comments

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. 

---

P and S does not have any indirect edges connecting through vertices. So, order of p and s does not matter.

C is the answer

Answer 2

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

Comments

Typo:- in first paragraph

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

It sud be P or from S

---

Nice explanation, Thanks

Answer 3

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

Answer 4

 

There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.

Answer 5

Think of edges as courses. If an edge is there between two courses as C1->C2, then C1 is prerequisite for C2.