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.

+18 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.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,010 questions

45,507 answers

131,664 comments

48,697 users