Graph Algorithms

Página 1

Cycle detection in a directed and undirected graph differs. In a directed graph, we use DFS and store the currently visited nodes in a stack and find a back edge. whereas in a undirected graph, we just mark every node that we have visited as visited and when we visit an already visited node and this visited node is not the parent of the current node, then there is a cycle in the graph.

Detect Cycle in a Directed Graph : http://www.geeksforgeeks.org/detect-cycle-in-a-graph/

Time Complexity : O(E + V);

Detect Cycle in a Undirected Graph: http://www.geeksforgeeks.org/detect-cycle-undirected-graph/

Time Complexity : O(E + V);

Página 2