Cycle Detection in Graphs

Cycle detection in graph in python

Introduction to Cycle Detection in Graphs 

Cycle Detection in Graphs are widely used to represent relationships between various entities. However, one critical challenge in working with graphs is detecting cycles within them.

This article let us go through into cycle detection in graphs using different algorithms and their Python implementations.

Understanding Cycle Detection in Graphs

A graph comprises vertices or nodes connected by edges, illustrating relationships between them. A cycle in a graph occurs when a sequence of edges leads back to the starting vertex.

Depth-First Search (DFS) Algorithm

Depth-First Search is an algorithm used for traversing or searching tree or graph data structures. It starts at a source node and explores as far as possible along each branch before backtracking.

DFS aids in cycle detection by tracking visited nodes and checking for back edges during traversal.

Breadth-First Search (BFS) Algorithm

In contrast to DFS, Breadth-First Search traverses a graph level by level. It explores all the neighbor nodes at the present level before moving to the next level.

BFS can also be used to detect cycles by maintaining a queue and identifying cycles when encountering a visited node.


Floyd's Tortoise and Hare Algorithm

Floyd’s Tortoise and Hare Algorithm, also known as the Floyd’s cycle-finding algorithm, is a pointer algorithm that detects cycles in a sequence efficiently.

By moving at different speeds through the sequence, this algorithm identifies a cycle’s existence.

Python Implementation for Cycle Detection

Let’s explore Python implementations for cycle detection in graphs using DFS, BFS, and Floyd’s Tortoise and Hare Algorithm:


Code :

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = {vertex: [] for vertex in range(vertices)}

    def add_edge(self, u, v):

    def is_cyclic_util(self, v, visited, parent):
        visited[v] = True

        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                if self.is_cyclic_util(neighbor, visited, v):
                    return True
            elif parent != neighbor:
                return True

        return False

    def is_cyclic(self):
        visited = [False] * self.vertices

        for vertex in range(self.vertices):
            if not visited[vertex]:
                if self.is_cyclic_util(vertex, visited, -1):
                    return True

        return False

# Example Usage:
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(1, 3)
g.add_edge(3, 4)

if g.is_cyclic():
    print("The graph contains a cycle.")
    print("The graph does not contain a cycle.")

In this implementation:

  • The Graph class represents an undirected graph using an adjacency list.
  • The add_edge method adds an edge between two vertices.
  • The is_cyclic method initializes a visited array and then calls the is_cyclic_util method for each unvisited vertex to perform DFS.
  • The is_cyclic_util method recursively explores the graph using DFS and checks for back edges (edges to already visited vertices that are not the parent of the current vertex).

This implementation prints whether the graph contains a cycle or not.

Breadth-First Search (BFS) Algorithm

Breadth-First Search is an algorithm for traversing or searching tree or graph data structures. It explores all the vertices at the current depth before moving on to vertices at the next depth level. BFS is often used for unweighted graphs.

Code : 

from collections import deque

def bfs(graph, start, end):
    queue = deque([start])
    visited = set([start])

    while queue:
        current_node = queue.popleft()

        if current_node == end:
            # Construct the path
            path = [current_node]
            while current_node != start:
                current_node = visited[current_node]
            return path[::-1]

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited[neighbor] = current_node

# Example usage:
graph_example = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']

result = bfs(graph_example, 'A', 'D')
print("Shortest path from A to D:", result)

Output :

Shortest path from A to D: ['A', 'B', 'D']

Explanation :

The output of the Breadth-First Search (BFS) algorithm is typically the shortest path from the start node to the goal node, represented as a sequence of nodes. This means that the shortest path from the start node ‘A’ to the goal node ‘D’ is through the sequence of nodes [‘A’, ‘B’, ‘D’]. This output represents the minimum number of edges or steps required to reach the goal node from the start node.

Practical Applications and Use Cases

  1. Social Networks:

    • Use Case: Modeling relationships in social media platforms.
    • Application: Analyzing connections between users, detecting communities, and recommending friends or connections.
  2. Transportation Networks:

    • Use Case: Modeling roads, flights, or public transportation systems.
    • Application: Finding optimal routes, analyzing traffic flow, and planning transportation logistics.
  3. Networks and Telecommunications:

    • Use Case: Representing communication networks.
    • Application: Designing and optimizing computer networks, identifying points of failure, and ensuring efficient data transmission.
  4. Recommendation Systems:

    • Use Case: Recommending products, movies, or content to users.
    • Application: Analyzing user preferences, identifying patterns in user behavior, and suggesting relevant items.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription