Detecting cycle in graphs using Depth First Search (DFS)

Graph Type Algorithm Algorithm Gist Time Complexity
Directed graph Depth First Search (DFS) 1. Do a DFS traversal of the graph.
2. Keep track of the visited nodes in the current path (before back-tracking) along with all the visited nodes.
3. If an adjacent node is found visited in the list of nodes in the current path, a cycle is found.
4. Before back-tracking unmark the nodes in the current path.
O(E+V)
Undirected graph Depth First Search (DFS) 1. Do a DFS traversal of the graph.
2. Keep track of the visited node’s parent along with all the visited nodes.
3. If an adjacent node is found visited during the traversal that is not the parent of the source node, a cycle is found.
O(2E+V)

Copyright (c) 2019-2020, Algotree.org.
All rights reserved.