Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
It's not clear to me why this is indicative of a cycle in the graph: if (sort...

Mike Palarz

Mar 3, 2022

It's not clear to me why this is indicative of a cycle in the graph:

if (sortedOrder.size() != vertices) // topological sort is not possible as the graph has a cycle return new ArrayList();

If there's a cycle, then wouldn't the algorithm have just ran endlessly?

0

0

Comments
Comments
Design Gurus
Design Gurus4 years ago

No the algorithm will not run endlessly. Try it; give an input with a cycle. This should also answer your first question too.

Let us know if you were able to find the answer.

M
Mike Palarz4 years ago

Thanks for the clarification. I see that if I have 2 nodes that have cyclical edges, they will be missed in the algorithm. It's almost as if they're skipped in a way. It's because they can never be source vertices because they will always refer to each other since they ...

On this page