retagged by
510 views
0 votes
0 votes

Can Bfs be applied for topological sort?

retagged by

1 Answer

0 votes
0 votes
Yes, It can be applied.

Because the fundamental property of topological sort states that no node can be traversed until its requisite node(s) has been traversed.

In BFS we can see that every next node is only traversed after all the nodes on its previous level are visited. Which essentially is the same thing as topological ordering. Although you do need to update some baselines in the program, but the essence of BFS is maintained.

Related questions

0 votes
0 votes
1 answer
1
VS asked Nov 26, 2017
991 views
1 votes
1 votes
1 answer
2
thor asked Jan 15, 2017
312 views
1 votes
1 votes
0 answers
4
admin asked Dec 15, 2022
338 views
Consider the following graph.How many nodes (apart from $s$) does the Breadth First Search algorithm discover before discovering $t$ when starting from $s$.