Quinn’s Mind Palace

How to detect cycles in a graph?

In this post, I’ve gathered the most commonly used algorithms to detect cycles.

But first, we have to decide what kind of cycles we are trying to detect.


Definitions.

Cycle: a path in a graph that starts and ends at the same vertex, visiting at least one edge.

Negative-weight cycle: a cycle in a weighted graph where the sum of the edge weights around the cycle is negative.

The concept of a “negative-weight cycle” is generally not applicable to undirected graphs, as the direction of traversal can be chosen to always yield the lower weight, effectively eliminating the concept of a “negative-weight cycle.”


Well, there are also Hamiltonian and Eulerian cycles (tours), but those are out of the scope of this post. We’ll just focus on the normal nonnegative-weight cycles and the negative-weight cycles.

Nonnegative-weight cycle detection

General idea: While exploring, keep track of visited nodes. If during the traversal, we encounter a node that has already been visited and is not the parent of the current node in the DFS tree, then a cycle exists. This method is efficient for detecting cycles in both directed and undirected graphs.


For the implementation, there are two ways—one is using a recursion stack and a visited tag, and the other is incorporating both together into one 3-color tag. The former is easier to understand in my opinion, but the latter is more popular on LeetCode.

Pseudo code (visited tag + recursion stack):

def has_cycle(graph):
    visited = set()
    rec_stack = set()

    def dfs(node):
        visited.add(node)
        rec_stack.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True

        rec_stack.remove(node)
        return False

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True

    return False

Pseudo code (3-color tags):

def has_cycle(graph):
    color = {node: 0 for node in graph}
    
    def dfs(node):
        color[node] = 1  # Node is being processed
        
        for neighbor in graph[node]:
            if color[neighbor] == 0:  # Unvisited node
                if dfs(neighbor):
                    return True
            elif color[neighbor] == 1:  # Cycle detected
                return True
        
        color[node] = 2  # Node and all its descendants processed
        return False

    for node in graph:
        if color[node] == 0:
            if dfs(node):
                return True
    
    return False

Asymptotic analysis: O(|V|+|E|).

General idea: Traverse the graph level by level, keeping track of visited nodes. If during the traversal, we encounter a node that has already been visited and is not the parent of the current node, then a cycle exists. This method is particularly useful for detecting cycles in undirected graphs.


Pseudo code:

def has_cycle(graph):
    visited = set()
    
    for start_node in graph:
        if start_node not in visited:
            queue = [(start_node, None)]  # (node, parent)
            visited.add(start_node)
            
            while queue:
                node, parent = queue.pop(0)
                
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, node))
                    elif neighbor != parent:
                        return True  # Cycle detected
    
    return False  # No cycle found

Asymptotic analysis: O(|V|+|E|).

Topological sort (for directed graphs only)

General idea: It works by ordering the vertices of a graph such that for every directed edge (u,v), vertex u comes before v in the ordering. If a valid topological sort exists, then the graph is acyclic. If no valid ordering can be found, it indicates the presence of a cycle.


Pseudo code:

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(node):
        if node in visited:
            return False
        visited.add(node)
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        stack.append(node)
        return True

    for node in graph:
        if node not in visited:
            if not dfs(node):
                return None  # Cycle detected

    return stack[::-1]  # Reverse the stack to get topological order

def has_cycle(graph):
    return topological_sort(graph) is None

Asymptotic analysis: O(|V|+|E|).

Negative-weight cycle detection

There is only one way of finding negative-weight cycles. You may encounter other algorithms (or rather, “other names”) on the internet, but they are actually just reskinned Bellman-Ford.

Bellman-Ford algorithm

General idea: The algorithm works by relaxing all edges |V|−1 times, and then checking for negative cycles by attempting one more relaxation. If any distance can still be reduced after |V|−1 iterations, it indicates the presence of a negative cycle.


Steps:

  1. Initialize distances from the source to all vertices as infinite and distance to the source itself as 0.
  2. Relax all edges |V|−1 times. For each edge (u,v) with weight w, if dist[v]>dist[u]+w, then update dist[v]=dist[u]+w.
  3. After step 2, if we can still relax an edge, then there is a negative weight cycle in the graph.

Pseudo code:

def bellman_ford(graph, source):
    # Initialize distances
    distances = {node: float('inf') for node in graph}
    distances[source] = 0

    # Relax edges |V| - 1 times
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    # Check for negative-weight cycles
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                return True  # Negative cycle detected

    return False  # No negative cycle found

Asymptotic analysis: O(|V|⋅|E|).

#Algorithms