Doubt in code of Topological sort using DFS Graphs

#1

In the below code for Topological sort using DFS Graphs:

1184×1280 158 KB

Sir, is getting following output:

1280×1111 123 KB

But I think that in the output, Data Set should be printed first then all the other vertices.

#2

hello @sahilkhan2312000131

there can be multiple topological sort possible for a single graph.

yeah that is also correct.

#3

But as per the above code,
Map is made like:
Python: Data preprocessing,Pytorch,ML
Data Pre:ML
Data Set: Face recogn
DL: Face recogn
ML:DL
Pytorch: DL
and as per code First python is sent to dfs_helper() and all its neighbours and their neighbours are marked as visited and added to ordering. Then only only Data Set is left and that is added to front of ordering. This means data set should be printed first.
Why is sir’s output different??

#4

we have used map , it will order the elements(key) in ascending order…
so python will not be sent first. elements that is smallest will be sent first

#5

Map is made like:
Data Pre:ML
Data Set: Face recogn
DL: Face recogn
ML:DL
Python: Data preprocessing,Pytorch,ML
Pytorch: DL
and sir’s output is correct, I get it.
Then how are multiple outputs possible??

#6

leave the implementation(with unique implementation u will get unique ordering).

my point is there can be multiple topological ordering possible.
for ex->
a
/ \
b c
\ /
d
here
u can have
a b c d
or
a c b d
both are valid ordering of same graph.

#7

That’s what I want to know that for a complex DAG, how will we be able to write Topological ordering??

#8

…

the algorithm that u have learnt is finding the topological ordering(any one valid ordering among all possible) only.
whatevr ordering the algorithm will give will be valid.
the algorithm will work for any kind of dag.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.