Graph — Things and Their Connections

What is it? #

A graph is a set of nodes and the connections between them. Unlike a tree, there is no root, a node can have many parents, and cycles are allowed.

Connections are called edges. They can be undirected, like a mutual friendship, or directed, like "A depends on B". They can also carry a weight — distance, cost, time.

The usual way to store a graph in code is an adjacency list: a dictionary mapping each node to its neighbours. It uses memory proportional to the actual connections, which is what most real graphs need.

Once you have that structure, the standard algorithms — BFS, DFS, shortest paths, cycle detection — all become short functions.

Think of it like this #

A city map. Junctions are nodes, roads are edges. Some roads are one-way, which makes those edges directed. Each road has a length, which is a weight.

Asking "can I get from here to there", "what is the shortest route", and "is there a road that, if closed, cuts the city in half" are all graph questions.

Simple example #

A social network where friendship is mutual, a task list where some tasks must finish before others, and a road network with distances. All three are graphs, differing only in direction and weights.

Code #

from collections import defaultdict

# Undirected graph — friendships
friends = defaultdict(set)

def add_friendship(a, b):
    friends[a].add(b)
    friends[b].add(a)            # both directions

for a, b in [("ravi", "anita"), ("anita", "sam"), ("sam", "priya")]:
    add_friendship(a, b)

print(friends["anita"])          # {'ravi', 'sam'}


# Directed graph — task dependencies ("build" must run before "test")
depends_on = {
    "deploy": ["test"],
    "test": ["build"],
    "build": ["install"],
    "install": [],
}


# Weighted graph — road distances in km
roads = {
    "A": {"B": 5, "C": 2},
    "B": {"A": 5, "D": 4},
    "C": {"A": 2, "D": 8},
    "D": {"B": 4, "C": 8},
}


# Is there any path from one node to another?
def reachable(graph, start, goal):
    seen, stack = {start}, [start]
    while stack:
        node = stack.pop()
        if node == goal:
            return True
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                stack.append(neighbour)
    return False

print(reachable(friends, "ravi", "priya"))     # True


# Cycle detection in a directed graph — a circular dependency
def has_cycle(graph):
    visiting, done = set(), set()

    def visit(node):
        if node in done:
            return False
        if node in visiting:          # we came back to a node still in progress
            return True
        visiting.add(node)
        for neighbour in graph.get(node, []):
            if visit(neighbour):
                return True
        visiting.discard(node)
        done.add(node)
        return False

    return any(visit(node) for node in graph)

print(has_cycle(depends_on))                   # False
print(has_cycle({"a": ["b"], "b": ["a"]}))     # True

Two ways to store a graph with V nodes and E edges

adjacency list    memory O(V + E)   neighbour lookup fast   good for sparse graphs
adjacency matrix  memory O(V^2)     edge check O(1)         good for dense graphs

How it works #

defaultdict(set) gives an empty set for any unseen key, which removes the "does this key exist yet" boilerplate when building a graph.

For an undirected graph, adding an edge means adding it in both directions. Forgetting one side is the most common bug in graph-building code.

The directed graph stores only the outgoing edges from each node. Direction carries meaning: deploy depends on test, not the other way around.

The weighted graph nests a dictionary of neighbour to weight. That shape is exactly what Dijkstra's algorithm consumes.

reachable uses a stack and a seen set. The seen set is not optional — without it, any cycle sends the traversal into an infinite loop. That is the biggest practical difference between walking a graph and walking a tree.

has_cycle tracks two states. A node in visiting is on the current path; reaching it again means a cycle. A node in done is fully explored and safe to skip. This three-colour idea is the standard way to detect cycles in directed graphs, and the basis of topological sorting.

The representation table matters for large graphs. An adjacency matrix for a million nodes would need a trillion cells; an adjacency list only stores the edges that exist.

Real-world use #

Graphs model social networks, road and flight networks, package dependencies, build pipelines, permission hierarchies, recommendation systems and network topology.

Cycle detection is why package managers can tell you "circular dependency detected", and why build tools can order tasks correctly. That ordering is a topological sort, which is a direct application of DFS.

Shortest-path algorithms power navigation, network routing and delivery planning. Dijkstra's algorithm, built on the heap from the previous lesson, is the standard for non-negative weights.

At large scale, graphs live in specialised databases such as Neo4j, or in adjacency tables in a relational database. "Friends of friends" as a SQL query is a self-join; as a graph traversal it is two hops.

Common mistakes #

• Forgetting to add both directions for an undirected edge.
• Traversing without a visited set, which loops forever on a cycle.
• Using an adjacency matrix for a large sparse graph and wasting huge amounts of memory.
• Assuming a graph is connected. Real graphs often have isolated components.
• Using recursion for traversal on a graph deep enough to exhaust the stack.

Practice #

Build a graph of six cities with distances. Write functions to list all cities reachable from a start point, count the connected components, and detect whether a directed version of the graph contains a cycle.