liveBook · Manning

Graph

As explained in Algorithms Every Programmer Should Know

A graph is a data structure consisting of vertices and edges that represent entities and relationships.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines graph structure, compares representations and edge directions, and demonstrates cycle-safe traversal with an iterative DFS implementation.
Examples
Uses road maps, logistics, telecommunications networks, and social networks to illustrate graph applications.
What it assumes
Assumes familiarity with trees and earlier DFS and BFS traversal sketches while explaining graph structure and cycle-safe visitation.
What you can do after
Builds an iterative DFS traversal using an adjacency list and a visited set to avoid revisiting nodes.
How it connects
Connects graphs to trees, depth-first search, breadth-first search, adjacency matrices, and adjacency lists.

Also explained in

Compare how 25 books explain graph →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.