Think of a directed graph as a network of one-way relationships. Its vertices represent entities, while each edge points from a source to a destination, so travel is allowed only in that direction. A follow on Twitter is a natural example: one person can follow another without being followed back. section 13.4
Use directed graphs when the relationship itself has direction:
- Model one-way roads, workflows, processes, and state machines, where moving from u to v does not imply a direct route from v to u. section 13.4
- Distinguish directed relationships from undirected ones: Facebook friendship and LinkedIn connections are two-way, while Twitter and Instagram follows are not necessarily mutual. section 13.4
- Represent the structure with an adjacency list or, in niche contexts, an adjacency matrix; directed edges can also represent an undirected edge as two opposite edges. section 13.16 section 13.4
- Check connectivity carefully: weak connectivity ignores directions, whereas strong connectivity requires a path in both directions between vertices. section 13.6
A campaign network
Suppose everyone on a campaign follows the Tiger, but the Tiger follows nobody. The edges point toward the Tiger, so the network is directed. The Crocodile may follow the Monkey independently; unless a reverse edge exists, the Monkey cannot travel directly back to the Crocodile. Larger networks can be divided into strongly connected components when vertices reach one another in both directions. section 13.4 section 13.6
Compare the direction of edges and the routes permitted between connected vertices. section 13.4
