Finding length of shortest cycle in undirected graph

Finding the Length of the Shortest Cycle in an Undirected Graph

Discover efficient algorithms to determine the shortest cycle in an undirected graph, a fundamental problem in graph theory with applications in network analysis and circuit design.

Finding the length of the shortest cycle in an undirected graph is a classic problem in computer science and graph theory. A cycle in a graph is a path that starts and ends at the same vertex, visiting other vertices along the way. The 'length' of a cycle typically refers to the number of edges it contains. This problem has various applications, from analyzing network robustness to identifying redundant connections in circuits. This article explores common algorithms to solve this problem, focusing on Breadth-First Search (BFS) based approaches.

Understanding Cycles and Shortest Paths

Before diving into algorithms, it's crucial to understand what constitutes a cycle and how it relates to shortest paths. In an undirected graph, a cycle exists if there's a path from a vertex u to a vertex v, and an edge directly connects u and v, forming a closed loop. The shortest cycle is the one with the minimum number of edges among all possible cycles in the graph. For unweighted graphs, BFS is an ideal algorithm for finding shortest paths because it explores the graph layer by layer, guaranteeing that the first time it reaches a node, it does so via the shortest possible path.

graph TD
    A[Start Node] --> B(BFS Traversal)
    B --> C{Node Visited?}
    C -->|No| D[Mark Visited & Enqueue Neighbors]
    C -->|Yes & Not Parent| E[Cycle Detected]
    E --> F[Calculate Cycle Length]
    D --> B
    F --> G[Compare & Update Shortest Cycle]
    G --> B

High-level flowchart of a BFS-based cycle detection algorithm.

Algorithm: BFS from Each Vertex

A straightforward approach to finding the shortest cycle is to run a Breadth-First Search (BFS) from each vertex in the graph. During each BFS traversal, we keep track of the distance from the source vertex and the parent of each visited vertex. If we encounter an already visited vertex v that is not the immediate parent of the current vertex u, we have found a cycle. The length of this cycle would be distance[u] + distance[v] + 1 (where 1 accounts for the edge (u, v)). We then take the minimum of all such cycle lengths found across all BFS traversals.

This method guarantees finding the shortest cycle because BFS inherently finds shortest paths in unweighted graphs. By running BFS from every possible starting point, we ensure that we cover all potential shortest cycles.

from collections import deque

def find_shortest_cycle(n, adj):
    min_cycle = float('inf')

    for start_node in range(n):
        q = deque([(start_node, 0, -1)]) # (node, distance, parent)
        dist = [-1] * n
        parent = [-1] * n
        dist[start_node] = 0

        while q:
            u, d, p = q.popleft()

            for v in adj[u]:
                if v == p: # Skip the edge to the parent to avoid trivial cycles
                    continue
                
                if dist[v] == -1: # Node v not visited yet
                    dist[v] = d + 1
                    parent[v] = u
                    q.append((v, d + 1, u))
                else: # Node v already visited, a cycle is found
                    # Cycle length = dist[u] + dist[v] + 1 (edge u-v)
                    min_cycle = min(min_cycle, d + dist[v] + 1)
    
    return min_cycle if min_cycle != float('inf') else -1 # Return -1 if no cycle found

# Example Usage:
# n = number of nodes, adj = adjacency list
# adj = [[1, 2], [0, 2], [0, 1]] for a triangle graph
# print(find_shortest_cycle(3, [[1, 2], [0, 2], [0, 1]])) # Output: 3

Python implementation of finding the shortest cycle using BFS from each vertex.

Optimization for Bipartite Graphs and Girth

While the BFS from each vertex approach is general, specific graph properties can sometimes lead to optimizations or provide additional insights. For instance, if a graph is bipartite, it contains no odd-length cycles. The shortest cycle in a bipartite graph will always have an even length. The length of the shortest cycle in a graph is also known as its 'girth'.

For graphs with a known small girth, or for very sparse graphs, more specialized algorithms might exist, but the BFS-based approach remains robust and widely applicable for general undirected graphs. It's important to note that if the graph is disconnected, this algorithm will correctly find the shortest cycle within any connected component, or return -1 if no cycles exist in any component.