9.6 Undirected Graphs

Problem

You need to model relationships that are naturally symmetric.

Many connections do not have a meaningful direction. If two cities are connected by a road, travel is often possible in both directions. If two computers share a network cable, both endpoints can communicate. If two users are friends in a social network, the relationship is mutual.

Representing these relationships as directed edges introduces unnecessary complexity and can obscure the actual structure of the problem.

You need a graph model that captures mutual connectivity directly.

Solution

Represent each connection as an undirected edge.

Instead of writing:

A → B

write:

A — B

This single edge represents connectivity in both directions.

An adjacency list implementation stores the relationship twice:

graph = {
    "A": ["B"],
    "B": ["A"]
}

Traversal algorithms can move freely between connected vertices.

For example:

A — B
|   |
C — D

can be represented as:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}

Any traversal starting from one vertex can move along any incident edge regardless of direction.

Discussion

Undirected graphs focus on connectivity rather than flow.

The most common question becomes:

What is connected to what?

rather than:

What can reach what?

This distinction changes both the interpretation of the graph and the algorithms that operate on it.

Common examples include:

Domain	Vertex	Edge
Road networks	City	Road
Social networks	User	Friendship
Computer networks	Device	Physical connection
Electrical systems	Component	Wire
Molecules	Atom	Bond
File sharing	Computer	Shared connection

In each case, the relationship is fundamentally mutual.

Building an Undirected Graph

Given edge pairs:

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

Insert both directions:

def build_graph(edges):
    graph = {}

    for u, v in edges:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)

    return graph

Result:

{
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"]
}

The graph now reflects mutual connectivity.

Failure to add the reverse edge is one of the most common implementation mistakes in graph programming.

Connectivity

Connectivity is the central concept in undirected graphs.

Consider:

A — B — C

D — E

There are two disconnected regions.

A traversal beginning at A can reach:

A
B
C

but not:

D
E

The graph therefore contains two connected components.

Many graph problems reduce to determining whether vertices belong to the same component.

Examples include:

• Network reachability
• Social clusters
• Infrastructure analysis
• Geographic regions
• Resource sharing

A simple DFS can identify all vertices in a component.

def dfs(graph, vertex, visited):
    visited.add(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Starting from one vertex, DFS discovers every vertex connected to it.

Connected Components

A connected component is a maximal set of vertices connected by paths.

Consider:

A — B — C

D — E

F

The graph contains three connected components:

{A, B, C}
{D, E}
{F}

A standard algorithm repeatedly launches DFS from unvisited vertices.

def connected_components(graph):
    visited = set()
    result = []

    for vertex in graph:
        if vertex in visited:
            continue

        component = set()

        def dfs(v):
            visited.add(v)
            component.add(v)

            for neighbor in graph[v]:
                if neighbor not in visited:
                    dfs(neighbor)

        dfs(vertex)
        result.append(component)

    return result

Result:

[
    {"A", "B", "C"},
    {"D", "E"},
    {"F"}
]

This pattern appears throughout graph theory.

Many more advanced algorithms build upon the concept of components.

Paths in Undirected Graphs

A path is a sequence of vertices connected by edges.

Example:

A — B — D — F

This path connects:

A

to:

F

Unlike directed graphs, path traversal does not need to consider edge orientation.

This simplification makes many algorithms easier.

Breadth-first search, for example, computes shortest paths in unweighted undirected graphs directly.

from collections import deque

def bfs(graph, start):
    distance = {
        start: 0
    }

    queue = deque([start])

    while queue:
        vertex = queue.popleft()

        for neighbor in graph[vertex]:
            if neighbor not in distance:
                distance[neighbor] = (
                    distance[vertex] + 1
                )
                queue.append(neighbor)

    return distance

The first time a vertex is discovered, the shortest path has already been found.

Trees as Undirected Graphs

Many important graph structures are special kinds of undirected graphs.

A tree is a connected undirected graph with no cycles.

Example:

    A
   / \\n  B   C
 / \\nD   E

Properties:

• Connected
• No cycles
• Exactly V - 1 edges

Trees appear throughout algorithms:

• File systems
• Syntax trees
• Search trees
• Network routing
• Hierarchical data

Although trees receive their own treatment later, it is useful to recognize that every tree is also an undirected graph.

Cycle Detection

Cycle detection is simpler in undirected graphs than in directed graphs.

Consider:

A — B
|   |
C — D

A cycle exists.

When traversing an undirected graph, every edge appears twice.

This creates a subtle issue.

Suppose DFS visits:

A → B

When processing B, it immediately sees:

B → A

That edge does not indicate a cycle.

It is simply the edge used to arrive at B.

The solution is to track the parent vertex.

def has_cycle(graph):
    visited = set()

    def dfs(vertex, parent):
        visited.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor == parent:
                continue

            if neighbor in visited:
                return True

            if dfs(neighbor, vertex):
                return True

        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, None):
                return True

    return False

The parent check prevents false positives.

Sparse Network Modeling

Many practical networks are sparse.

Suppose a network contains:

1,000,000 devices

and each device connects to only a handful of others.

The number of edges remains relatively small compared to the number of possible connections.

Adjacency lists work particularly well in this environment.

For sparse undirected graphs:

Memory = O(V + E)

Traversal remains:

O(V + E)

This scalability is one reason adjacency lists dominate graph implementations.

Complexity Characteristics

For an undirected graph stored as an adjacency list:

Operation	Complexity
Add edge	O(1) amortized
Remove edge	O(degree)
DFS	O(V + E)
BFS	O(V + E)
Connected components	O(V + E)
Cycle detection	O(V + E)
Memory usage	O(V + E)

Notice that every major traversal algorithm scales linearly with graph size.

This efficiency makes undirected graph algorithms practical even for large datasets.

Common Pitfalls

Do not forget to insert both directions of every edge.

Do not accidentally mix directed and undirected semantics within the same graph.

Do not ignore isolated vertices.

F

is still a connected component.

Do not use directed graph cycle-detection logic on undirected graphs.

The parent relationship must be handled explicitly.

Do not assume the graph is connected.

Many datasets contain multiple disconnected regions.

Always verify this assumption before launching a traversal from a single starting vertex.

Recipe: Verify Graph Connectivity

A useful utility function checks whether the graph forms a single connected component.

def is_connected(graph):
    if not graph:
        return True

    start = next(iter(graph))

    visited = set()

    def dfs(vertex):
        visited.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)

    return len(visited) == len(graph)

Example:

graph = {
    "A": ["B"],
    "B": ["A"],
    "C": []
}

print(is_connected(graph))

Output:

False

Vertex C forms a separate component.

This check is frequently used before algorithms that require connectivity.

Takeaway

Undirected graphs model mutual relationships in which connectivity matters more than direction. Their primary concerns are paths, connected components, cycles, and structural properties of networks. Because traversal algorithms can move freely across edges, many problems become simpler than their directed counterparts. Understanding connected components, cycle detection, and connectivity analysis provides the foundation for spanning trees, minimum spanning trees, articulation points, bridges, and other advanced graph algorithms that follow.