Graphs: dots joined by lines
Before you start
You need nothing else first. This unit starts from scratch.
The idea in one paragraph
A graph records which things are linked to which. The things are called nodes, drawn as dots, and the links are called edges, drawn as lines between pairs of dots. Friends in a class, cities joined by roads and points that sit close to each other are all graphs. Only the links matter, not where the dots are drawn. A program usually stores a graph as a list of each node's neighbors.
A graph is a set of nodes and the edges between some pairs of them
Five students, A to E, list who is friends with whom: A and B, A and C, B and C, and C and D. E is new and has no friends in the class yet. Draw each student as a dot and each friendship as a line, and you have a graph. Each dot is a node and each line an edge.
Two nodes joined by an edge are neighbors. The number of neighbors a node has is its degree. A node with no edges, like E, still belongs to the graph; it just has degree 0.
A program stores each node's list of neighbors
A program cannot look at a drawing. It stores the graph in one of two common ways. An edge list is just the pairs: (A, B), (A, C), (B, C), (C, D). A neighbor list, also called an adjacency list, gives each node the list of its neighbors. The neighbor list answers "who is next to C?" at once, which most graph methods need again and again.
Build the neighbor list from the edge list (A, B), (A, C), (B, C), (C, D), with nodes A to E.
- Start every node with an empty list: A: [], B: [], C: [], D: [], E: [].
- For each edge, add each end to the other's list. (A, B) gives A: [B] and B: [A].
- After all four edges: A: [B, C], B: [A, C], C: [A, B, D], D: [C], E: [].
- The degrees are the list lengths: 2, 2, 3, 1 and 0. They add to 8, twice the 4 edges, because every edge has two ends.
Your turn. Add the edge (D, E). What are the new degrees, and what do they add to?
Answer
A 2, B 2, C 3, D 2, E 1. They add to 10, twice the 5 edges.
Graphs also describe shapes. Take a set of points in space and join each point to the others that lie within some small distance. The result is a graph, and questions about the shape, such as "is it in one piece?", become questions about the graph. The connected-components unit answers that one.
The word "graph" here does not mean a chart of a function. Also, this page shows the simplest kind: each edge joins two different nodes and works both ways. Other graphs give each edge a direction, like a one-way street (a directed graph), or a number, like a road's length (a weighted graph).
graphs.py: a neighbor list in plain Python
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]
nodes = ["A", "B", "C", "D", "E"]
# This builds a dictionary in one line, as a list comprehension builds a list.
# Each node starts with an empty list.
neighbors = {n: [] for n in nodes}
for u, v in edges:
neighbors[u].append(v) # append puts v at the end of u's list
neighbors[v].append(u)
print(neighbors)
print({n: len(neighbors[n]) for n in nodes}) # each node's degree
{'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C'], 'E': []}
{'A': 2, 'B': 2, 'C': 3, 'D': 1, 'E': 0}
Check yourself
-
A graph has six nodes, and their degrees are 3, 3, 2, 2, 1 and 1. How many edges does it have?
Answer
The degrees add to 12, and each edge adds 2 to the total, so there are 6 edges.
-
Describe a city's subway map as a graph. What are the nodes and what are the edges?
Answer
The stations are the nodes. Each stretch of track between two neighboring stations is an edge.
-
Can a graph with 5 nodes have a node of degree 5, if no edge joins a node to itself and no pair is joined twice?
Answer
No. A node can be joined to at most the 4 other nodes, so its degree is at most 4.
Go further
Optional background, for readers who want more than this page.
-
Nodes, edges and degree with friendly pictures and a few puzzles.
-
Shows that a search program needs only each node's neighbors, and turns a grid of squares into a graph, with code.