Adjacency lists and matrices

What is a graph?

A graph is a collection of vertices and edges. A vertex, also called a node, represents an item. An edge represents a connection between two items. Edges can have a direction or a weight. Graph traversal visits connected vertices while remembering which have already been visited.

Example: Let A, B, and C be vertices, with edges A–B and B–C. A can reach C through B. A directed edge A → B permits movement from A to B but does not automatically permit movement back.

Helpful before this chapter

If these ideas are new, begin with:

Hash maps and sets Queues and deques Recursion

Understand the idea

Adjacency lists store neighbors per vertex and suit sparse graphs. Matrices store a V×V edge relation and give direct edge tests but scan many absent connections.

Work through an example

The lab stores A:[B,C]. A matrix for five vertices needs 25 cells even though many pairs are disconnected.

Time and space complexity

Lists O(V+E) storage/traversal; matrices O(V²) storage and typical full-neighbor scans.

Why it works

Every stored adjacency entry corresponds to a real edge; undirected edges appear in both endpoint lists.

Common mistakes

Forgetful reverse insertion makes an undirected graph one-way.
Include isolated vertices in the vertex inventory.

Chapter lab · Python implementation

A graph models entities and connections; edges can be directed or undirected, weighted or unweighted. Our lab uses adjacency lists and marks BFS vertices when enqueuing. The diagram has a cycle A-B-D-C-A, so visited state is essential. Distances count edges because every edge has equal cost.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def bfs(graph,start):
    distances={start:0}
    parent={start:None}
    queue=deque([start])
    while queue:
        node=queue.popleft()
        for neighbor in graph.get(node,[]):
            if neighbor not in distances:
                distances[neighbor]=distances[node]+1
                parent[neighbor]=node
                queue.append(neighbor)
    return distances,parent

def components(graph):
    seen=set(); count=0
    for start in graph:
        if start in seen: continue
        count+=1; seen.add(start); stack=[start]
        while stack:
            node=stack.pop()
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor); stack.append(neighbor)
    return count

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C'],'E':[]}
d,p=bfs(g,'A'); assert d=={'A':0,'B':1,'C':1,'D':2}
assert p['D'] in ['B','C']
assert components(g)==2
assert bfs({'X':[]},'X')[0]=={'X':0}

CHECK YOUR UNDERSTANDING