Loading learning content...
If connectivity tells us whether destinations are reachable, paths and cycles tell us how we get there and whether we can return to where we started. These concepts are so fundamental that they appear in nearly every graph algorithm and application.
Consider these scenarios:
npm install) must detect cycles to avoid infinite loopsPaths and cycles are the verbs of graph theory—they describe movement, flow, and structure within a graph.
By the end of this page, you will master the formal definitions of paths, walks, trails, and cycles. You'll understand the crucial distinctions between these concepts, learn multiple algorithms for cycle detection in both directed and undirected graphs, and see how these concepts apply to real-world problems from deadlock detection to Eulerian circuits.
Graph theory is precise about different types of movement through a graph. These distinctions matter because algorithms behave differently depending on what repetitions are allowed.
Walk: A sequence of vertices v₀, v₁, ..., vₖ where each consecutive pair (vᵢ, vᵢ₊₁) has an edge connecting them. Vertices and edges may repeat.
Trail: A walk where no edge repeats (but vertices may repeat).
Path: A walk where no vertex repeats (and therefore no edge repeats either).
Think of it as increasing restrictions:
| Type | Vertex Repetition | Edge Repetition | Example Use |
|---|---|---|---|
| Walk | Allowed | Allowed | Random walks, probability analysis |
| Trail | Allowed | NOT Allowed | Eulerian paths (visiting every edge once) |
| Path | NOT Allowed | NOT Allowed | Shortest path problems |
A path from vertex u to vertex v in graph G = (V, E) is a sequence of distinct vertices:
P = (v₀, v₁, v₂, ..., vₖ) where v₀ = u, vₖ = v, and (vᵢ, vᵢ₊₁) ∈ E for all 0 ≤ i < k
Path Properties:
Some texts use 'simple path' to emphasize no vertex repetition, and 'path' to mean what we call 'walk.' In this course, we follow the convention where 'path' always means no repetition. When repetition is allowed, we say 'walk.' Always clarify terminology when reading other sources.
A cycle is a path that returns to its starting point. More formally:
A cycle is a path v₀, v₁, ..., vₖ where v₀ = vₖ (start equals end), k ≥ 1, and all other vertices are distinct.
For undirected graphs, we typically require k ≥ 3 (at least 3 edges) because going back and forth on a single edge (A-B-A) is not considered a meaningful cycle.
For directed graphs, even k = 1 can form a cycle if there's a self-loop (edge from a vertex to itself), though k ≥ 2 is more common.
The length of a cycle is the number of edges (or equivalently, vertices) it contains.
Girth: The length of the shortest cycle in a graph. If a graph has no cycles (is acyclic), the girth is defined as infinity (∞).
| Graph Type | Minimum Cycle Length | Girth |
|---|---|---|
| Forest/Tree | None possible | ∞ |
| Triangle | 3 | 3 |
| Square/Rectangle | 4 | 4 |
| Bipartite graph | 4+ (no odd cycles) | ≥ 4 |
A graph with no cycles is called acyclic. Acyclic graphs have special properties that make many algorithms simpler and more efficient.
An undirected acyclic graph is called a forest. If it's also connected, it's a tree.
Properties of trees:
A directed graph with no cycles is called a DAG (Directed Acyclic Graph). DAGs are perhaps the most important graph class in computer science.
A directed graph is a DAG if and only if it has a topological ordering. If you can arrange all vertices in a line such that all edges go from left to right, there are no cycles. This provides both a test for acyclicity and a useful ordering when it exists.
Detecting cycles in undirected graphs is a fundamental operation. There are two main approaches:
During DFS traversal, a cycle exists if we encounter a vertex that has already been visited and is not the parent of the current vertex.
The key insight is that in an undirected graph, every edge connects to either:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
def has_cycle_undirected(graph: dict[int, list[int]]) -> bool: """ Detect if an undirected graph contains a cycle using DFS. Args: graph: Adjacency list representation Returns: True if the graph contains at least one cycle Time Complexity: O(V + E) Space Complexity: O(V) for visited set and recursion stack """ visited = set() def dfs(vertex: int, parent: int) -> bool: """ DFS that tracks parent to avoid false positives. Returns True if a cycle is found. """ visited.add(vertex) for neighbor in graph.get(vertex, []): if neighbor not in visited: # Unvisited neighbor: explore recursively if dfs(neighbor, vertex): return True elif neighbor != parent: # Visited neighbor that's NOT our parent = back edge = CYCLE return True return False # Check all components (graph may be disconnected) for vertex in graph: if vertex not in visited: if dfs(vertex, -1): # -1 = no parent (root of DFS tree) return True return False def find_cycle_undirected(graph: dict[int, list[int]]) -> list[int] | None: """ Find and return an actual cycle in an undirected graph. Returns: List of vertices forming a cycle, or None if no cycle exists """ visited = set() parent_map = {} # To reconstruct the cycle path def dfs(vertex: int, parent: int) -> int | None: """Returns the vertex where cycle was detected, or None.""" visited.add(vertex) parent_map[vertex] = parent for neighbor in graph.get(vertex, []): if neighbor not in visited: result = dfs(neighbor, vertex) if result is not None: return result elif neighbor != parent: # Cycle found! Return where it closes parent_map[neighbor] = vertex # Close the cycle return neighbor return None for start in graph: if start not in visited: cycle_vertex = dfs(start, -1) if cycle_vertex is not None: # Reconstruct cycle by following parents back cycle = [] current = cycle_vertex while True: cycle.append(current) current = parent_map.get(current, -1) if current == cycle_vertex or current == -1: break cycle.append(cycle_vertex) # Complete the cycle return cycle[::-1] # Reverse to get correct order return None # Example usagegraph_with_cycle = { 0: [1, 2], 1: [0, 2], # Creates triangle 0-1-2-0 2: [0, 1, 3], 3: [2]} graph_without_cycle = { 0: [1, 2], 1: [0], 2: [0, 3], 3: [2]} print(f"Has cycle: {has_cycle_undirected(graph_with_cycle)}") # Trueprint(f"Has cycle: {has_cycle_undirected(graph_without_cycle)}") # Falseprint(f"Cycle: {find_cycle_undirected(graph_with_cycle)}") # [0, 1, 2, 0]For undirected graphs being built incrementally, Union-Find provides an elegant cycle detection method:
When adding edge (u, v), if u and v are already in the same component (same root), adding the edge creates a cycle.
This is because there's already a path between them; adding another creates a second path, forming a cycle.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
class UnionFind: def __init__(self, n: int): self.parent = list(range(n)) self.rank = [0] * n def find(self, x: int) -> int: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x: int, y: int) -> bool: """Returns False if x and y were already connected (cycle would form).""" root_x, root_y = self.find(x), self.find(y) if root_x == root_y: return False # Already connected - adding edge creates cycle! # Union by rank if self.rank[root_x] < self.rank[root_y]: self.parent[root_x] = root_y elif self.rank[root_x] > self.rank[root_y]: self.parent[root_y] = root_x else: self.parent[root_y] = root_x self.rank[root_x] += 1 return True def has_cycle_edges(n: int, edges: list[tuple[int, int]]) -> bool: """ Detect cycle given edge list using Union-Find. Time Complexity: O(E × α(V)) ≈ O(E) Space Complexity: O(V) """ uf = UnionFind(n) for u, v in edges: if not uf.union(u, v): return True # This edge would create a cycle return False # Example: Building a graph edge by edgeedges = [(0, 1), (1, 2), (2, 0)] # Triangle - last edge creates cycleprint(f"Has cycle: {has_cycle_edges(3, edges)}") # True edges_tree = [(0, 1), (1, 2), (2, 3)] # Path - no cycleprint(f"Has cycle: {has_cycle_edges(4, edges_tree)}") # FalseCycle detection in directed graphs requires a different approach because edge direction matters. The parent-tracking trick from undirected graphs doesn't work—we need to track the state of each vertex during DFS.
We assign each vertex one of three colors:
Key Insight: A cycle exists if we encounter a gray vertex during DFS. Gray vertices are ancestors in the current DFS path, so reaching one means we've found a back edge that forms a cycle.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
from enum import IntEnum class Color(IntEnum): WHITE = 0 # Unvisited GRAY = 1 # In current DFS path (exploring) BLACK = 2 # Completely processed def has_cycle_directed(graph: dict[int, list[int]]) -> bool: """ Detect if a directed graph contains a cycle using three-color DFS. Time Complexity: O(V + E) Space Complexity: O(V) """ color = {v: Color.WHITE for v in graph} def dfs(vertex: int) -> bool: """Returns True if a cycle is found starting from vertex.""" color[vertex] = Color.GRAY # Start processing for neighbor in graph.get(vertex, []): if color.get(neighbor, Color.WHITE) == Color.GRAY: # Found back edge to ancestor = CYCLE return True if color.get(neighbor, Color.WHITE) == Color.WHITE: # Unvisited vertex - explore recursively if dfs(neighbor): return True color[vertex] = Color.BLACK # Finished processing return False # Check all vertices (graph may have multiple components) for vertex in graph: if color[vertex] == Color.WHITE: if dfs(vertex): return True return False def find_cycle_directed(graph: dict[int, list[int]]) -> list[int] | None: """ Find and return an actual cycle in a directed graph. """ color = {v: Color.WHITE for v in graph} parent = {} cycle_start = None cycle_end = None def dfs(vertex: int) -> bool: nonlocal cycle_start, cycle_end color[vertex] = Color.GRAY for neighbor in graph.get(vertex, []): if color.get(neighbor, Color.WHITE) == Color.GRAY: # Back edge found - record cycle endpoints cycle_start = neighbor cycle_end = vertex return True if color.get(neighbor, Color.WHITE) == Color.WHITE: parent[neighbor] = vertex if dfs(neighbor): return True color[vertex] = Color.BLACK return False for vertex in graph: if color[vertex] == Color.WHITE: if dfs(vertex): # Reconstruct cycle by following parents from end to start cycle = [] current = cycle_end while current != cycle_start: cycle.append(current) current = parent[current] cycle.append(cycle_start) cycle.append(cycle_end) # Close the cycle return cycle[::-1] return None # Example: Directed graph with cyclegraph_cycle = { 0: [1], 1: [2], 2: [3], 3: [1], # Creates cycle 1 -> 2 -> 3 -> 1 4: []} # Example: DAG (no cycle)dag = { 0: [1, 2], 1: [3], 2: [3], 3: [], 4: [0]} print(f"Has cycle: {has_cycle_directed(graph_cycle)}") # Trueprint(f"Has cycle: {has_cycle_directed(dag)}") # Falseprint(f"Cycle found: {find_cycle_directed(graph_cycle)}") # [1, 2, 3, 1]Union-Find merges vertices into equivalence classes but ignores edge direction. In a directed graph, edges A→B and B→C don't mean A can reach C via B and return—the direction matters. A cycle requires following edges in their specified direction, which Union-Find doesn't track.
Cycle detection and topological sorting are deeply connected:
A directed graph has a valid topological ordering if and only if it has no cycles (is a DAG).
This relationship provides an alternative cycle detection method: attempt topological sort, and if it fails (not all vertices processed), the graph has a cycle.
Kahn's algorithm simultaneously produces a topological order and detects cycles:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
from collections import deque def topological_sort_with_cycle_detection( graph: dict[int, list[int]]) -> tuple[bool, list[int]]: """ Perform topological sort using Kahn's algorithm. Returns: (has_cycle, topological_order) - has_cycle: True if graph contains a cycle - topological_order: Valid ordering if no cycle, partial otherwise Time Complexity: O(V + E) Space Complexity: O(V) """ # Calculate in-degrees in_degree = {v: 0 for v in graph} for vertex in graph: for neighbor in graph[vertex]: in_degree[neighbor] = in_degree.get(neighbor, 0) + 1 # Start with vertices having no dependencies queue = deque([v for v in in_degree if in_degree[v] == 0]) topological_order = [] while queue: vertex = queue.popleft() topological_order.append(vertex) # "Remove" this vertex by decrementing neighbor in-degrees for neighbor in graph.get(vertex, []): in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # If we couldn't process all vertices, there's a cycle has_cycle = len(topological_order) < len(graph) return has_cycle, topological_order # Example: Course schedulingcourses = { "calc1": ["calc2"], "calc2": ["calc3", "linear_algebra"], "calc3": ["diff_eq"], "linear_algebra": ["diff_eq"], "diff_eq": [], "intro_cs": ["data_structures"], "data_structures": ["algorithms"], "algorithms": []} has_cycle, order = topological_sort_with_cycle_detection(courses)print(f"Has cycle: {has_cycle}") # Falseprint(f"Order: {order}") # Valid course sequence # Add a cyclic dependencycourses["diff_eq"] = ["calc1"] # Creates cycle!has_cycle, order = topological_sort_with_cycle_detection(courses)print(f"Has cycle: {has_cycle}") # True| Algorithm | Graph Type | Time | Finds Cycle? | Best For |
|---|---|---|---|---|
| DFS + parent tracking | Undirected | O(V+E) | Yes | Any undirected graph |
| Union-Find | Undirected | O(E·α(V)) | Yes | Incremental edge addition |
| Three-color DFS | Directed | O(V+E) | Yes | Any directed graph |
| Kahn's (topological) | Directed | O(V+E) | No (just detects) | When also need ordering |
Beyond simple cycles, graph theory identifies several special cycle types with important applications:
An Eulerian path visits every edge exactly once. An Eulerian cycle does this and returns to the start.
Existence conditions:
Applications: DNA fragment assembly, drawing figures without lifting pen, optimizing garbage truck routes.
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle does this and returns to the start.
Complexity: No efficient (polynomial-time) algorithm is known. This is an NP-complete problem—one of the most famous in computer science.
Applications: Traveling Salesman Problem, circuit board drilling optimization.
In weighted graphs, a negative cycle is a cycle where the sum of edge weights is negative. Negative cycles are important because:
# Negative cycle in currency exchange:
# USD -> EUR: 0.9 (log: -0.105)
# EUR -> GBP: 0.8 (log: -0.223)
# GBP -> USD: 1.5 (log: 0.405)
# Total: 0.9 × 0.8 × 1.5 = 1.08 USD (profit!)
# Sum of logs: 0.077 > 0, but detecting -cycle in -log graph
Paths and cycles appear throughout computer science and beyond:
When you see 'detect deadlock,' 'find if valid ordering exists,' or 'check for circular dependency,' think cycle detection. The problem is almost always: model as a graph, then use DFS with proper state tracking.
Paths and cycles are fundamental to understanding how information flows through graphs and whether structures contain circular dependencies. Let's consolidate the key concepts:
What's Next:
With paths and cycles understood, we now turn to vertex degree—the count of edges connected to each vertex. Degree analysis reveals graph structure, predicts algorithm behavior, and determines properties like whether Eulerian cycles exist.
You now understand paths and cycles deeply—from precise definitions through detection algorithms to real-world applications. You can detect cycles in both undirected and directed graphs, understand the connection to topological sorting, and recognize when cycle detection applies to problems. Next, we'll explore vertex degrees.