Understanding cycle detection in a directed graph

A directed graph is one where all edges can only be traversed in one direction. Similar to an undirected graph, a cycle in a directed graph is a path that starts and ends at the same node, has no repeated edges, and has at least two nodes. Unlike undirected graphs, revisiting an already visited node is not sufficient to confirm the existence of a cycle. In this lesson, we will look at cycles in directed graphs and learn the algorithm that can be used to detect such cycles.

Algorithm

Detecting a cycle in a directed graph is very similar to that in an undirected graph, but there are some notable differences. In an undirected graph, revisiting a previously visited node while traversing the graph is sufficient to confirm the existence of a cycle. However, in a directed graph, the revisited node must be part of the currently traced path from the source node. If the revisited node is not in the currently traced path, we can ignore it and continue with the traversal. We will learn more about the proof of correctness later in the course.

Unlike cycle detection in an undirected graph, where any traversal algorithm can be used, for a directed graph, we can only use depth-first traversal, which keeps track of all nodes in the currently traced path in the function call stack.

We begin by creating two sets visited and nodesInPath to keep track of the nodes that have been visited and the nodes in the currently traced path from the source, respectively. We then iterate through the list of nodes and for each node, check if it is already visited. If it is visited, we ignore it and proceed to the next node; otherwise, we perform a depth-first search from the node to detect if it is part of any cycle using a cycle detection function.