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.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+21 votes

Consider the directed graph below given.

Which one of the following is **TRUE**?

- The graph does not have any topological ordering.
- Both PQRS and SRQP are topological orderings.
- Both PSRQ and SPRQ are topological orderings.
- PSRQ is the only topological ordering.

+21 votes

Best answer

+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.

+19 votes

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,559 answers

146,291 comments

62,306 users