A graph connects vertices (nodes) with edges to represent relationships. Unlike a tree, it has no parent-child hierarchy: nodes can connect across the network, creating cycles. section 1.4.5 section 1.5
Figure 1.10 The transition from a tree to a relational graph. The structural tree rules are broken to form a cycle or a closed loop. One node can be connected to multiple nodes.
See how adding a cycle and lateral connections breaks a tree’s hierarchy. section 1.4.5
Graphs model systems such as road maps, logistics, telecommunications networks, and social networks. To traverse a graph with DFS or BFS without revisiting nodes forever, track visited nodes in a set. section 1.4.5
Figure 1.11 Traversal paths shown through a network with a cycle. Left: Depth-First Search (DFS) traces deep pathways until it detects dead-ends and mismatches. Right: A Breadth-First Search (BFS) expands to all neigboring or adjacent nodes. Both traversals use a visited set to track already visited nodes to avoid infinite loops.
Compare DFS’s deep paths with BFS’s expansion across neighboring nodes; both track visited nodes. section 1.4.5
Choose a representation to record connections:
- An adjacency matrix records connections between pairs of vertices as 1 or 0. section 1.5
- An adjacency list maps each vertex to its neighboring vertices. section 1.5
- Undirected graphs have mutual connections; directed graphs restrict connections to one direction. section 1.5
























