Dots and lines
A graph is a set of vertices (dots, also called nodes) joined by edges (lines). Trees and linked lists are actually special kinds of graphs.
Think of it like this: A map: cities are vertices and roads are edges. A social network: people are vertices and friendships are edges. The internet: web pages are vertices and links are edges.
| Kind | Meaning | Example |
|---|---|---|
| undirected | edges go both ways | friendship, two-way roads |
| directed | edges have arrows | Instagram follows, one-way streets |
| weighted | edges have a number (cost, distance) | road lengths in km |
| unweighted | every edge counts the same | “how many hops?” |
Storing a graph: the adjacency list
For each vertex, keep a list of its neighbours. A dictionary of lists works well:
roads = [("Pune", "Mumbai"), ("Pune", "Nashik"), ("Mumbai", "Surat"), ("Nashik", "Surat")]
graph = {}
for a, b in roads:
graph.setdefault(a, []).append(b)
graph.setdefault(b, []).append(a) # two-way road
for city, neighbours in graph.items():
print(city, "->", neighbours)Output
Pune -> ['Mumbai', 'Nashik'] Mumbai -> ['Pune', 'Surat'] Nashik -> ['Pune', 'Surat'] Surat -> ['Mumbai', 'Nashik']
When vertices are numbered 0 to n − 1, a list of lists is even simpler: graph = [[] for _ in range(n)].
Tip: There's also the adjacency matrix: an n × n grid where
m[a][b] = 1means an edge. It's quick to check one edge, but uses n² memory – too much for big, sparse graphs.