22.4.2. Using DFS for Cycle Detection

One of the interesting structural properties of a graph is whether or not it has cycles. An acyclic graph, as shown on the left, is a graph in which you cannot start at any node, follow a sequence of edges, and come back to the original node. In contrast, the graph on the right has cycles; for instance, edges (5, 9) and (9, 10) form a cycle.

Cycle detection is essential in graph theory since cycles can affect the properties and behavior of graphs. A cycle means that there is a way to traverse the graph that returns to the starting point. This chunk explains the concept of acyclic graphs (where cycles don't exist) and cyclic graphs (where cycles do exist). The left side shows a valid structure without cycles, whereas the right side highlights how loops can be formed in directed or undirected graphs leading to cycles.

Consider a roundabout in a traffic system. If you enter the roundabout, you can continuously loop around without getting out, which is similar to a graph with cycles. In contrast, a straight road with no exit points represents an acyclic graph; once you reach the end of the road, you can't circle back to where you started.

When we execute BFS, we keep track of edges which are used to mark vertices as visited. If the graph is acyclic, every node will be part of the BFS search. However, if the graph has cycles, some edges will not be used because the target vertex will already be marked as visited.

In this chunk, the focus is on how Breadth-First Search (BFS) can help determine if there are cycles in a graph. If during the BFS process an edge points to a vertex that is already visited, it indicates a cycle. This mechanism works because BFS explores nodes level by level; any edge that leads to a previously explored node implies circular connections or cycles.

Imagine a city with interconnected streets. If you are on a street that leads back to a point you have already visited, you create a loop or cycle in your travel. If you find that you can reach your past location without taking a new path, it’s similar to discovering cycles in a graph.

Now, let’s do the same thing, but with DFS. In this case, if we find non-tree edges, then the graph will have a cycle. Importantly, we also explore and differentiate three types of edges: forward edges, backward edges, and cross edges.

This chunk discusses the process of using Depth-First Search (DFS) to find cycles in graphs. As DFS progresses, it identifies and categorizes edges based on whether they are tree edges (part of the DFS tree) or non-tree edges. Non-tree edges can indicate cycles. It introduces terms like forward edges (going deeper in the tree), backward edges (going back to an ancestor), and cross edges (going to unrelated nodes) and explains how each relates to cycle detection.

Think of a family tree. If you look back at your ancestors (going backward) or trace connections between non-ancestral branches (cross edges), you can visualize the different types of relationships. A forward edge might be like finding a descendant when exploring deeper in your family history; if you discover someone marrying into another branch, that could signify a cycle.

A directed graph has a cycle if DFS reveals a back edge. This forms part of the cycle indirectly since the back edge closes the path between nodes that were previously traversed.

This section emphasizes the importance of back edges in identifying cycles in directed graphs using DFS. A back edge connects a node to its ancestors, confirming the existence of a cycle. The presence of these edges signifies that there's a route back to previously visited nodes and forms cycles uniquely in directed graphs.

Consider a board game where players can move forward to new spaces but can also jump back to earlier spots. If a player can jump back to an earlier position they've already been in, it represents a cycle. In directed graphs, this jumping back reflects how back edges create cycles.

--