Graph Theory Cycle Detector using DFS

cycler_detector.py

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = {v: [] for v in vertices}

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)  # for undirected graph

def has_cycle(graph):
    visited = {v: False for v in graph.vertices}
    parent = {v: None for v in graph.vertices}

    def dfs_visit(node, parent_node):
        visited[node] = True
        parent[node] = parent_node

        for neighbor in graph.adj_list[node]:
            if not visited[neighbor]:
                if dfs_visit(neighbor, node):
                    return True
            elif parent_node != neighbor:
                return True

        return False

    for vertex in graph.vertices:
        if not visited[vertex]:
            if dfs_visit(vertex, None):
                return True

    return False

vertices = ['A', 'B', 'C', 'D', 'E']
edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A')]  # with a cycle
# edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E')]  # without a cycle

graph = Graph(vertices)
for u, v in edges:
    graph.add_edge(u, v)

if has_cycle(graph):
    print("The graph contains a cycle.")
else:
    print("The graph does not contain a cycle.")