The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Graph Representation

Next ►
►

We know what a graph is; now we must decide how to store it in memory. There are two classic representations — the adjacency matrix and the adjacency list — and choosing well between them is an engineering decision with direct consequences for space and time, exactly the kind of Big O analysis we've been practicing since module 1. In this lesson we'll compare the two, see why for TaskFlow's sparse graphs the adjacency list wins (built with module 5's dict and set), and implement the Graph class we'll use throughout the entire rest of the module.

Contents

  1. Adjacency matrix
  2. Adjacency list
  3. Cost comparison: space and time
  4. When is each one the right choice? Dense versus sparse
  5. The course's Graph class
  6. TaskFlow's dependency graph with the class
  7. Honorable mention: the edge list

Adjacency matrix

The idea: number the n vertices from 0 to n-1 and build an n × n table where cell [i][j] says whether the edge i → j exists (with 1/0, or with the weight if the graph is weighted).

# Vertices, in a fixed order:
vertices = ["migrate_db", "configure_server", "deploy_api"]
# index: migrate_db=0, configure_server=1, deploy_api=2

# 3x3 matrix as a list of lists (like the arrays in module 1):
matrix = [
    [0, 0, 1],   # migrate_db -> deploy_api
    [0, 0, 1],   # configure_server -> deploy_api
    [0, 0, 0],   # deploy_api doesn't unblock anything (yet)
]

# Does the edge migrate_db -> deploy_api exist?
print(matrix[0][2] == 1)   # True, in O(1): direct index access

Walking through the snippet:

  • Row i describes the edges that leave vertex i; column j, the ones that enter j. That's why matrix[0][2] = 1 encodes migrate_db → deploy_api under our convention (the arrow points at what gets unblocked).
  • Checking an edge is a double index access: O(1), the matrix's great virtue.
  • In an undirected graph the matrix is symmetric (matrix[i][j] == matrix[j][i]); in a weighted one, we'd store the weight instead of 1 (and a special value like None or float("inf") for "no edge").

The problem jumps right out: with just 3 vertices and 2 edges we're already storing 9 cells, almost all zero. With the 200 tasks of a large TaskFlow project that would be 40,000 cells for maybe 300 dependencies: over 99% zeros. The matrix takes O(n²) no matter how many edges there are.

Adjacency list

The alternative: for each vertex, store only its neighbors (the targets of its outgoing edges). In Python, the natural pairing is a dict whose value is a set — the two structures from module 5, with their average O(1) membership test:

adjacency = {
    "migrate_db": {"deploy_api"},
    "configure_server": {"deploy_api"},
    "deploy_api": set(),
}

# Does the edge exist? Two O(1) hash-table lookups:
print("deploy_api" in adjacency["migrate_db"])   # True

# A vertex's neighbors: direct, nothing to scan
print(adjacency["configure_server"])             # {'deploy_api'}

Explanation:

  • The key is the source vertex; the value, the set of targets. A vertex with no outgoing edges stores an empty set() — but it still has its entry in the dict, which is what makes it exist as a vertex.
  • Total space is O(n + a) (vertices plus edges): we pay for what is there, not for what could be there. For sparse graphs, the gap with O(n²) is enormous.
  • Using a set instead of a list for the neighbors gives us edge_exists in average O(1) instead of O(degree); with a list we'd keep insertion order, but the lookup would be linear. For weighted graphs, the natural step up is an inner dict mapping target → weight, which keeps the O(1) lookup and adds the weight. That's what our class will do.

Cost comparison: space and time

With n vertices and a edges:

Operation Adjacency matrix Adjacency list (dict of set/dict)
Space O(n²) O(n + a)
Does edge u → v exist? O(1) Average O(1) (hash)
Iterate neighbors of u O(n) (whole row, zeros included) O(degree(u))
Add edge O(1) Average O(1)
Add vertex O(n) or worse (new row and column) O(1)
Out-degree of u O(n) (count the row) O(1) (len)
In-degree of u O(n) (count the column) O(n + a) (or keep a separate counter)

Two important readings of the table:

  • The operation the algorithms in the coming lessons run millions of times is "give me u's neighbors". In the adjacency list it costs exactly the vertex's degree; in the matrix, always n. That's why BFS/DFS will cost O(n + a) with a list but O(n²) with a matrix.
  • In-degree is awkward in both; when we need it often (topological order, 07-03), we'll precompute it once and maintain it in a separate dict.

When is each one the right choice? Dense versus sparse

Situation Recommended representation
Sparse graph (a ≈ n): dependencies, social networks, maps Adjacency list
Dense graph (a ≈ n²): everyone-to-everyone, distance matrices Adjacency matrix
Massive "does this edge exist?" querying on a small, stable graph Adjacency matrix
Vertices appearing and disappearing dynamically Adjacency list

TaskFlow's dependency graph is the textbook sparse case (each task depends on a handful), so our class will use an adjacency list. The matrix will make a natural comeback in Floyd-Warshall (07-04), which works precisely with the all-pairs distance table.

The course's Graph class

This is the class we'll use for the whole module. Design decisions, before the code:

  • Adjacency list with an outer dict (vertex → neighbors) and an inner dict (target → weight). For unweighted graphs the weight is simply 1, so the same code serves 07-03 (no weights) and 07-04/07-05 (with weights).
  • Optional directed: True by default (dependencies); with False (for the MST in 07-05), every edge is recorded in both directions.
  • Vertices are task ids; each task's full dict lives in a separate index, as in module 5.
class Graph:
    """Graph with an adjacency list: dict vertex -> dict target -> weight."""

    def __init__(self, directed=True):
        self.directed = directed
        self.adjacency = {}

    def add_vertex(self, v):
        # setdefault: creates the entry only if it doesn't exist (idempotent)
        self.adjacency.setdefault(v, {})

    def add_edge(self, source, target, weight=1):
        self.add_vertex(source)          # endpoints register themselves
        self.add_vertex(target)
        self.adjacency[source][target] = weight
        if not self.directed:            # undirected: the edge goes both ways
            self.adjacency[target][source] = weight

    def neighbors(self, v):
        """Dict target -> weight of the edges leaving v."""
        return self.adjacency.get(v, {})

    def edge_exists(self, source, target):
        return target in self.adjacency.get(source, {})

    def vertices(self):
        return list(self.adjacency)

    def out_degree(self, v):
        return len(self.adjacency.get(v, {}))

    def in_degree(self, v):
        # O(n + a): scans every neighbor list
        return sum(1 for targets in self.adjacency.values() if v in targets)

    def in_degrees(self):
        """All in-degrees in one pass: O(n + a) total."""
        degrees = {v: 0 for v in self.adjacency}
        for targets in self.adjacency.values():
            for target in targets:
                degrees[target] += 1
        return degrees

Points worth understanding line by line:

  • add_edge first calls add_vertex for both endpoints: that way there are never edges "dangling" from nonexistent vertices, and adding the edge A → B in one go creates A and B if needed.
  • neighbors returns the inner dict mapping target → weight. Iterating it with for target in g.neighbors(v) yields the targets; with for target, weight in g.neighbors(v).items(), the weights too. Both forms will appear constantly.
  • in_degree for a single vertex is expensive (O(n + a)); that's why we offer in_degrees(), which computes all of them at once for the same price. Kahn's algorithm (07-03) will use the latter.
  • Repeating add_edge(source, target) duplicates nothing: the inner dict overwrites the previous weight. With a list of neighbors we would have had to police duplicates by hand.

TaskFlow's dependency graph with the class

Let's build the DAG from the previous lesson. Reminder of the convention: add_edge(A, B) means "B depends on A" (finishing A brings B closer to being unblocked).

tasks = {
    "design_schema":     {"id": "design_schema", "title": "Design DB schema",
                          "priority": 2, "status": "pending", "hours": 3},
    "migrate_db":        {"id": "migrate_db", "title": "Migrate database",
                          "priority": 1, "status": "pending", "hours": 2},
    "configure_server":  {"id": "configure_server", "title": "Configure server",
                          "priority": 2, "status": "pending", "hours": 1},
    "deploy_api":        {"id": "deploy_api", "title": "Deploy API",
                          "priority": 1, "status": "pending", "hours": 2},
    "design_ui":         {"id": "design_ui", "title": "Design interface",
                          "priority": 3, "status": "pending", "hours": 5},
    "implement_ui":      {"id": "implement_ui", "title": "Implement interface",
                          "priority": 2, "status": "pending", "hours": 8},
    "integration_tests": {"id": "integration_tests", "title": "Integration tests",
                          "priority": 1, "status": "pending", "hours": 3},
    "launch":            {"id": "launch", "title": "Launch",
                          "priority": 1, "status": "pending", "hours": 1},
}

dependencies = Graph(directed=True)
for task_id in tasks:
    dependencies.add_vertex(task_id)   # tasks with no edges included

dependencies.add_edge("design_schema", "migrate_db")
dependencies.add_edge("migrate_db", "deploy_api")
dependencies.add_edge("configure_server", "deploy_api")
dependencies.add_edge("deploy_api", "integration_tests")
dependencies.add_edge("design_ui", "implement_ui")
dependencies.add_edge("implement_ui", "integration_tests")
dependencies.add_edge("integration_tests", "launch")

print(dependencies.neighbors("migrate_db"))              # {'deploy_api': 1}
print(dependencies.edge_exists("design_ui", "launch"))   # False (no DIRECT edge)
print(dependencies.in_degree("deploy_api"))              # 2: it waits for two tasks
print(dependencies.in_degrees())
# {'design_schema': 0, 'migrate_db': 1, 'configure_server': 0, 'deploy_api': 2,
#  'design_ui': 0, 'implement_ui': 1, 'integration_tests': 2, 'launch': 1}

The graph we just built:

graph LR
    A[design_schema] --> B[migrate_db]
    B --> C[deploy_api]
    S[configure_server] --> C
    C --> D[integration_tests]
    U[design_ui] --> I[implement_ui]
    I --> D
    D --> L[launch]

Look at the output of in_degrees(): the zeros (design_schema, configure_server, design_ui) are exactly the tasks that can start today. That dictionary is, quite literally, the starting point of Kahn's algorithm in the next lesson.

Honorable mention: the edge list

There is a third representation, the edge list: simply a list of tuples [(source, target, weight), ...]. It's terrible for querying neighbors (O(a) per query), but perfect when an algorithm needs all edges sorted by weight — which is exactly what Kruskal will do in lesson 07-05. We note it here and will pick it back up then.

Common Mistakes and Tips

  • Forgetting vertices with no edges. If you build the graph only with add_edge, a task with no dependencies and no dependents will never exist in adjacency and the algorithms will silently ignore it. That's why the example registers all vertices first.
  • Recording the edge in only one direction in undirected graphs. If you forget the symmetric write, "Anna knows Bruno" but Bruno doesn't know Anna, and BFS will produce nonsense. Our class handles it inside add_edge; if you write your own, don't skip it.
  • Mutating the dict returned by neighbors(). It returns the real internal dictionary; modify it from outside and you corrupt the graph. Treat it as read-only (or return dict(...), a copy, if you'd rather armor it and pay the cost).
  • Calling in_degree(v) inside a loop over all vertices. That's O(n · (n + a)). For all of them at once, in_degrees() does it in a single pass.
  • Tip: vertices must be hashable values (strings, numbers, tuples). We use the task's id, never the full dict — dicts can't be keys of another dict, as we saw in module 5.

Exercises

Exercise 1: the same graph as a matrix

Write (by hand or with code) the adjacency matrix of this lesson's TaskFlow graph, with the vertex order [design_schema, migrate_db, configure_server, deploy_api, design_ui, implement_ui, integration_tests, launch]. How many cells does it have and how many are 1? What percentage of the matrix is useful?

Exercise 2: remove_edge and remove_vertex

Add the methods remove_edge(source, target) and remove_vertex(v) to the Graph class (in TaskFlow: removing a dependency and deleting a task). Careful: when removing a vertex, the edges that arrive at it must disappear too. State the cost of each method.

Exercise 3: runnable tasks

Write a function runnable_tasks(graph, tasks) that returns the ids with in-degree 0 whose status is "pending", sorted by priority (1 first). Test it with the lesson's graph.

Solutions

Solution 1:

#                 d_s  mig  c_s  api  ui   imp  tst  lau
matrix = [
    [0,   1,   0,   0,   0,   0,   0,   0],   # design_schema
    [0,   0,   0,   1,   0,   0,   0,   0],   # migrate_db
    [0,   0,   0,   1,   0,   0,   0,   0],   # configure_server
    [0,   0,   0,   0,   0,   0,   1,   0],   # deploy_api
    [0,   0,   0,   0,   0,   1,   0,   0],   # design_ui
    [0,   0,   0,   0,   0,   0,   1,   0],   # implement_ui
    [0,   0,   0,   0,   0,   0,   0,   1],   # integration_tests
    [0,   0,   0,   0,   0,   0,   0,   0],   # launch
]

64 cells, 7 set to one: 10.9% is information and 89% is zeros. And that's with only 8 tasks; with 200, the useful part would be around 0.7%. It's the exact picture of why we chose the adjacency list.

Solution 2:

def remove_edge(self, source, target):
    # pop with a default value: doesn't fail if the edge didn't exist
    self.adjacency.get(source, {}).pop(target, None)
    if not self.directed:
        self.adjacency.get(target, {}).pop(source, None)

def remove_vertex(self, v):
    self.adjacency.pop(v, None)           # its outgoing edges: O(1)
    for targets in self.adjacency.values():
        targets.pop(v, None)              # the ones arriving at v: O(n + a)

remove_edge is average O(1). remove_vertex is O(n + a): there's no way to locate the incoming edges without checking every neighbor list — the same reason in_degree was expensive.

Solution 3:

def runnable_tasks(graph, tasks):
    degrees = graph.in_degrees()                         # a single pass
    ready = [t for t, d in degrees.items()
             if d == 0 and tasks[t]["status"] == "pending"]
    return sorted(ready, key=lambda t: tasks[t]["priority"])

print(runnable_tasks(dependencies, tasks))
# ['design_schema', 'configure_server', 'design_ui']
# (priorities 2, 2, and 3: the first two tie and keep their stable order)

sorted is stable (module 1), so priority ties respect the previous order. This function is a miniature preview of the full topological order in the next lesson.

Conclusion

We now have both classic representations measured and compared: the matrix (O(n²), edge lookup in O(1), ideal for dense graphs) and the adjacency list (O(n + a), neighbors at the fair price, the choice for sparse graphs like TaskFlow's). And, above all, we have the Graph class — an adjacency list built as a dict of dicts, optionally directed, weights built in — and the real dependency graph constructed with it. The structure is in memory; now we have to traverse it. In the next lesson, BFS and DFS on graphs finally arrive: module 6's level-order traversal generalized, module 3's stack resurfacing in DFS, and the visited set promised in module 5 becoming, once cycles enter the picture, not merely useful but indispensable.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved