Given a directed graph, find whether it contains cycle or not.
Which is the best algorithm for this problem in terms of memory and time complexity? Assuming the graph can contain approx 1 millions nodes.
4 Likes
<O(N+M),O(N+M)> a simple DFS will do the job.
1 Like
Read this -
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
11 Likes
I think depth first search (stack based) is better to detect a cycle and memory friendly
Is not what I just said?