The Gateway to Computer Science Excellence
+1 vote
241 views

Which is the best data structure to implement topological sort on directed graph?

  1. Heap
  2. Stack
  3. queue
  4. Array

 

in Algorithms by
edited by | 241 views
0
Stack.

Using a stack toplogical sort can be done by doing dfs.
0

I have used Queue here still got the correct answer ?  If I use stack i am getting wrong answer

0

@Kunal Kadian please help me out on this

0

I think your algo will give wrong ans if you add an edge from E to B.

Refer this:- https://www.geeksforgeeks.org/topological-sorting/

0
I think the question is ambiguous because both stack and queue can be used to give correct answers efficiently.

Queue : We use an array of in-degrees for all the vertices and a Queue.

Stack : We use dfs and Stack (given in geeksforgeeks).
0
Queue will not give correct result in all the cases.

1 Answer

0 votes
topological sort application dfs

dfs used stack

answer is stack
by
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
52,345 questions
60,504 answers
201,905 comments
95,336 users