Imagine storing friendships. A list of people tells you who exists, but it does not directly answer who is friends with whom—or who is a friend of a friend. A graph stores entities together with their relationships, making those connections the point of the structure. section 1.5 section 13.16
A graph G = (V, E) has a set of vertices V and a set of edges E. Vertices represent distinct entities; each edge connects a pair of vertices. Think of vertices as places you can visit and edges as the connections you can follow between them. section 13.2
A few choices describe what those connections mean:
- In a directed graph, an edge goes from a source to a destination in one direction, like a Twitter follow. In an undirected graph, it can be followed both ways, like a Facebook friendship. section 13.16
- An edge can have a numerical weight. A loop connects a vertex to itself; a simple graph has no loops and at most one edge between any pair of vertices. A multigraph can have multiple edges between a pair. section 13.2
- A connected graph has a path between every pair of vertices. A cyclic graph has a path that starts and ends at the same vertex. A graph can also be sparse, with relatively few edges, or dense, with edges near the possible maximum. section 13.16 section 13.2
A tree is a restricted kind of graph: it is simple, undirected, connected, and acyclic. Trees suit hierarchies such as file systems; graphs also handle relationships that do not fit a hierarchy, such as friendships or program flow. section 13.1 section 13.7
G = ([v1, v2, v3, v4], [(v1,v2),(v1,v3),(v2,v4)])
This small graph lists four vertices and three edges as pairs of vertices. Read an edge such as (v1, v2) as a connection from its first vertex to its second. section 13.2
To implement a graph, store its vertices and edges so connections are easy to search and traverse. Adjacency lists and adjacency matrices are two common approaches; matrices are used only in niche contexts. Breadth-first search can find paths with the fewest edges from a starting vertex. Depth-first search follows paths to their ends and can help check connectivity or cycles. section 13.8 section 13.16
