Imagine a map of who owes whom money. Each person is a node, and each arrow connecting two people is an edge. Edges model relationships between things in a graph. section 6.2
An arrow gives an edge direction. If Alex points to Rama, Alex is Rama’s in-neighbor and Rama is Alex’s out-neighbor. Without arrows, the relationship is undirected, so both endpoints are simply neighbors. section 6.2 section 6.6
Representing edges in Python
A graph can store each node’s outgoing edges in a hash table: graph["you"] = ["alice", "bob", "claire"]. The list contains the nodes reached by edges leaving "you"; a node with no outgoing edges maps to an empty list. section 6.6
Edges support several useful ways to think about graphs:
- Breadth-first search follows edges while exploring a network, so searching the whole graph takes O(V + E), where V counts vertices and E counts edges. section 6.8
- Dependency edges can express task order: if eating breakfast depends on brushing teeth, the breakfast node comes later in a topological ordering. section 6.8
- A family tree is a special graph whose edges point toward parents without pointing back upward. section 6.8
