Introduction

In Python, graphs and trees are usually represented with adjacency lists, edge lists, or node objects, depending on the operations you care about most. Cycle detection then depends on the structure type: for a directed graph you usually track a recursion stack, while for an undirected graph you usually track the parent node during traversal.

Adjacency Lists Are the Usual Default

For most graph algorithms, an adjacency list is the most practical representation. In Python, that usually means a dictionary mapping each node to its neighbors.

1graph = {
2    "A": ["B", "C"],
3    "B": ["D"],
4    "C": ["D"],
5    "D": [],
6}
7
8print(graph["A"])

This representation is good because it is:

• easy to read
• memory-efficient for sparse graphs
• convenient for traversal algorithms such as DFS and BFS

If your nodes are integers, you can also use a list of lists instead of a dictionary.

Edge Lists and Matrices Have Specific Uses

Sometimes a different representation is more appropriate.

An edge list is simple when you mostly care about the set of connections:

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]

An adjacency matrix is useful for dense graphs or for constant-time edge existence checks:

1matrix = [
2    [0, 1, 1, 0],
3    [0, 0, 0, 1],
4    [0, 0, 0, 1],
5    [0, 0, 0, 0],
6]

The tradeoff is space. Matrices use much more memory for sparse graphs, so adjacency lists remain the normal default in Python.

Trees Are Usually Simpler Than General Graphs

A tree is just a special kind of graph:

• connected
• acyclic
• usually hierarchical

In Python, a tree is often represented as a node object with a list of children.

1from dataclasses import dataclass, field
2
3@dataclass
4class Node:
5    value: str
6    children: list["Node"] = field(default_factory=list)
7
8root = Node("A", [
9    Node("B"),
10    Node("C", [Node("D")]),
11])
12
13print(root.children[1].children[0].value)  # D

This is natural for recursive traversal and for structures such as file trees, parse trees, and UI hierarchies.

Detect Cycles in a Directed Graph

For a directed graph, a standard technique is depth-first search with two sets:

• 'visited for nodes seen at all'
• 'in_stack for the current recursion path'

If DFS re-enters a node that is already in the current path, a cycle exists.

1def has_cycle_directed(graph):
2    visited = set()
3    in_stack = set()
4
5    def dfs(node):
6        if node in in_stack:
7            return True
8        if node in visited:
9            return False
10
11        visited.add(node)
12        in_stack.add(node)
13
14        for neighbor in graph.get(node, []):
15            if dfs(neighbor):
16                return True
17
18        in_stack.remove(node)
19        return False
20
21    return any(dfs(node) for node in graph)
22
23
24graph = {
25    "A": ["B"],
26    "B": ["C"],
27    "C": ["A"],
28}
29
30print(has_cycle_directed(graph))  # True

This is the classic answer for cycle detection in directed graphs.

Detect Cycles in an Undirected Graph

For undirected graphs, you need a slightly different rule. Seeing a previously visited node is not automatically a cycle, because you naturally revisit the node you just came from. So you track the parent.

1def has_cycle_undirected(graph):
2    visited = set()
3
4    def dfs(node, parent):
5        visited.add(node)
6
7        for neighbor in graph.get(node, []):
8            if neighbor not in visited:
9                if dfs(neighbor, node):
10                    return True
11            elif neighbor != parent:
12                return True
13
14        return False
15
16    for node in graph:
17        if node not in visited and dfs(node, None):
18            return True
19
20    return False
21
22
23graph = {
24    1: [2],
25    2: [1, 3],
26    3: [2, 4],
27    4: [3],
28}
29
30print(has_cycle_undirected(graph))  # False

This version matches the structure of undirected edges more accurately.

Trees Should Not Have Cycles

If a structure is supposed to be a tree and your traversal finds a cycle, the structure is invalid as a tree. That often means:

• a parent was linked as a child
• the input data is actually a general graph
• the construction logic introduced a back-reference

So cycle detection is not just an algorithm exercise. It is often a data-validation step.

Choose the Representation Based on the Problem

A useful rule is:

• adjacency list for most graph algorithms
• node objects for recursive tree logic
• edge list for simple storage or import/export
• matrix only when dense connectivity or constant-time edge checks really matter

Python is flexible enough to support all of them, but adjacency lists and node objects cover most real use cases.

Common Pitfalls

• Using an adjacency matrix for a sparse graph and wasting a lot of memory.
• Applying directed-graph cycle logic to an undirected graph and getting false positives.
• Assuming a tree representation cannot contain cycles just because it is called a tree.
• Forgetting to initialize nodes with no outgoing edges in the adjacency list when traversal code expects them.
• Choosing a representation that makes the target algorithm harder instead of easier.

Summary

• In Python, adjacency lists are the most common representation for general graphs.
• Trees are often represented with node objects and child lists.
• Use DFS with a recursion-stack check to detect cycles in directed graphs.
• Use DFS with parent tracking to detect cycles in undirected graphs.
• Pick the representation that matches the operations you need, not just the one that is easiest to type.