A graph is a data structure made of states and connections. Each state is a node, or vertex; each connection is an edge. Graphs model relationships among objects and make many problems easy to visualize and process with algorithms. section 2.5
A road trip as a graph
Imagine traveling to the beach. Each stop becomes a node, each road becomes an edge, and the distance traveled becomes an edge weight. A search algorithm can then find a path through the connected stops. Similar graphs represent computer networks, web pages and links, or people and social relationships. section 2.5 section 2.13
Choose the graph category that matches the relationships and structure:
- Undirected graphs have mutual relationships, like roads usable in both directions; directed graphs have explicitly one-way relationships. section 2.14
- Disconnected graphs contain isolated groups or nodes; acyclic graphs contain no cycles, as with course prerequisites. section 2.14
- Complete graphs connect every node to every other node; complete bipartite graphs connect every node in one partition to every node in another. section 2.14
- Weighted graphs attach values such as distances to edges, helping algorithms distinguish between connections. section 2.14
Figure 2.26 Types of graphs
Use the graph-category figure to compare direction, cycles, connectivity, partitions and edge weights visually. section 2.14
For implementation, represent relationships with an array of arrays, an incidence matrix, an adjacency matrix or an adjacency list. An adjacency records a node directly connected to another node; the best encoding depends on processing needs, language and tools. When searching graphs that contain cycles, track visited nodes to avoid looping forever. section 2.6 section 2.13
