How do you find the shortest route from one place to another? First, draw the places and the connections between them. You’ve made a graph: a way to model which things are connected. Once the route is a graph, breadth-first search can look for the shortest path measured in steps. section 6.1 section 6.9
A graph has nodes (the things) and edges (their connections). Imagine tracking who owes whom money after a poker game. Each person is a node; an arrow from one person to another is an edge showing who owes whom. A directly connected node is a neighbor. When arrows matter, the person an arrow points toward is an out-neighbor of the person it points from. section 6.2
What do the connections mean?
- In a directed graph, an arrow goes one way. “Alex owes Rama” does not also say that Rama owes Alex. section 6.2 section 6.6
- In an undirected graph, the connection goes both ways, so you can simply talk about neighbors. section 6.6
How do you store those connections? In Python, a hash table can map each node to an array of its out-neighbors. Nodes with no outgoing edges map to empty arrays. The order in which you add the hash-table entries does not matter. section 6.6
graph = {}
graph["you"] = ["alice", "bob", "claire"]
This small Python listing shows one node mapped to the nodes its arrows point to. section 6.6
The same model supports different questions. Breadth-first search finds whether a path exists and, if it does, the shortest path in steps; searching a whole graph takes O(V+E), where V counts nodes and E counts edges. A graph of task dependencies can produce a topological sort: an ordering in which each task follows its prerequisites. A family tree is another kind of graph, with no edges pointing back. section 6.8 section 6.9
Sometimes connections have costs, such as travel time. Then each out-neighbor can be stored with its edge cost instead of appearing in a plain array. That representation lets Dijkstra’s algorithm track the cost of reaching each node. section 9.5
