Solution
A graph is a data structure made of vertices (nodes) connected by edges. Vertices can be cities, people, or other things; edges are the relationships or pathways between them. Unlike a tree, a graph need not have a single root or a hierarchy. Any two vertices may be connected, and cycles are allowed. A social network is a graph: people connect in many directions with no single starting point.
Directed graphs: Edges have a direction. You can go from one vertex to another only the way the edge points. On a map of one-way streets, if there is no directed edge from city A to city B, you cannot travel directly from A to B.
Undirected graphs: Edges have no direction. A connection can be used both ways. If Person A is friends with Person B, then Person B is friends with Person A.
Other differences: Directed edges model one-way roads or one-way links. Undirected edges model two-way roads or mutual friendship. Weighted graphs may add a distance or cost on each edge (as in Figure 4.4) in either the directed or undirected case.