Graphs

Overview

A graph is a set of vertices and a set of edges connecting them. That is nearly no structure at all, which is precisely why it models so much: road networks, social connections, package dependencies, web links, state machines, and the call graph of the program you are reading this in.

Trees and linked lists are special cases — a tree is a connected graph with no cycles, a linked list a tree where every node has one child.

An undirected graph on six vertices. Note vertex 6 hanging off a single edge — removing it disconnects the graph, which makes it a bridge. Wikimedia Commons, Public domain

Core Concepts

Term	Meaning
Vertex (node)	An entity
Edge	A relationship between two vertices
Directed / undirected	Whether edges have a direction (follower vs. friendship)
Weighted	Edges carry a cost — distance, latency, price
Degree	Number of edges at a vertex (in-degree/out-degree when directed)
Path	A sequence of vertices joined by edges
Cycle	A path returning to its start
Connected	Every vertex reachable from every other
DAG	Directed acyclic graph — directed, no cycles
Dense / sparse	E close to V² / E close to V

DAGs deserve their own line

A DAG. Because no path returns to where it started, the vertices can always be laid out so that every arrow points forward — that ordering is a topological sort. Wikimedia Commons, Public domain

Acyclicity is what makes dependency resolution, build systems, task scheduling and spreadsheet recalculation possible: it guarantees a valid order exists. A cycle in any of those is precisely the error condition ("circular dependency"). See Topological Sort.

Architecture / Mechanism

The two representations

Adjacency list — each vertex stores its neighbours:

graph = {
    1: [2, 5],
    2: [1, 3, 5],
    3: [2, 4],
    4: [3, 5, 6],
    5: [1, 2, 4],
    6: [4],
}
# Weighted: store (neighbour, weight) pairs
weighted = {1: [(2, 7), (5, 3)], ...}

Adjacency matrix — a V×V grid where m[i][j] marks an edge:

#      1  2  3  4  5  6
m = [[0, 1, 0, 0, 1, 0],   # 1
     [1, 0, 1, 0, 1, 0],   # 2
     [0, 1, 0, 1, 0, 0],   # 3
     [0, 0, 1, 0, 1, 1],   # 4
     [1, 1, 0, 1, 0, 0],   # 5
     [0, 0, 0, 1, 0, 0]]   # 6

	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
Is there an edge u→v?	O(degree(u))	O(1)
Iterate u's neighbours	O(degree(u))	O(V) — scans empty cells too
Add an edge	O(1)	O(1)
Best for	Sparse graphs — nearly all real ones	Dense graphs; matrix algorithms

Default to the adjacency list

Real graphs are overwhelmingly sparse. A social network with a million users and a hundred friends each has 10⁸ edges — an adjacency list holds that comfortably, while the matrix needs 10¹² cells, 99.99% of them zero. Reach for a matrix only when the graph is genuinely dense, or when an algorithm wants matrix form (Floyd–Warshall, spectral methods).

Practical Usage

from collections import defaultdict

# Building an undirected graph from an edge list
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)      # omit this line for a directed graph

# Degree of a vertex
len(graph[v])

Domain	Vertices	Edges	Question asked
Maps / navigation	Intersections	Roads, weighted by time	Shortest path
Social networks	People	Friendships / follows	Degrees of separation, communities
Package managers	Packages	"depends on"	Topological order, cycle detection
Compilers	Basic blocks	Control flow	Reachability, dominance, dead code
Networks	Routers	Links, weighted by cost	Routing
Web search	Pages	Hyperlinks	PageRank

Edge Cases & Pitfalls

• Forgetting the reverse edge builds a directed graph when you wanted an undirected one, and the bug surfaces much later as an unreachable vertex.
• Not tracking visited vertices turns any traversal of a cyclic graph into an infinite loop. This is the difference between graph traversal and tree traversal, and the most common graph bug there is.
• Disconnected graphs. A traversal from one vertex reaches only its component. Finding all components means looping over every vertex and starting a traversal from each unvisited one.
• Self-loops and parallel edges break assumptions in hand-written algorithms. Decide whether your representation permits them.
• Vertex identity. Using mutable objects as vertex keys in a dict has the same hazard described under hash tables; integer or string IDs are safer.

References

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, §22.1 — graph representations and their trade-offs.
• Sedgewick & Wayne, Algorithms, 4th ed., Ch. 4 — "Graphs", covering undirected, directed, weighted and shortest-path graphs in turn.

Books & Videos

• VisuAlgo — Graph Structures — build graphs and switch representations interactively.

Related Pages

• Traversal: BFS & DFS — the two ways to walk a graph.
• Shortest Paths — Dijkstra's and Bellman–Ford.
• Topological Sort — ordering a DAG.