Chapter 18 — Graphs

Graph

A data structure made of vertices connected by edges

Vertex

A point or node in a graph

Edge

A connection between two vertices

Adjacent vertices

Vertices that are directly connected by an edge

Path

A specific sequence of edges used to get from one vertex to another

Graph relationship

The connection between data points inside a graph

Social network graph

A graph where people are vertices and friendships are edges

Recommendation graph

A graph where products are vertices and similar-product recommendations are edges

Map graph

A graph where locations are vertices and roads or routes are edges

Undirected graph

A graph where connections go both ways

Directed graph

A graph where connections have a specific direction

Weighted graph

A graph where edges have values such as distance, price, cost, or time

Weight

The value assigned to an edge in a weighted graph

Why weighted graphs matter

They let connections represent more than just “connected” or “not connected”

Graph in code

A graph can be represented by vertices that store their adjacent vertices

Adjacency list

A graph representation where each vertex stores a list of its neighboring vertices

Weighted graph in code

A graph where each vertex stores adjacent vertices and edge weights, often using a hash table

Graph search

Exploring a graph to find a vertex, check a connection, or traverse all vertices

Why search a graph

To find a vertex, check whether vertices are connected, or visit every vertex

Visited set

A set used to track which vertices have already been visited

Why visited tracking matters

It prevents infinite loops and repeated work in graphs with cycles

Depth-First Search

A graph search that goes as deep as possible down one path before backtracking

DFS

Depth-First Search

DFS memory trick

Go deep first, then backtrack

DFS use case

Useful for exploring a path fully before trying other paths

Breadth-First Search

A graph search that explores all nearby vertices before moving farther away

BFS

Breadth-First Search

BFS memory trick

Explore level by level

BFS use case

Useful for finding the shortest path in an unweighted graph

Queue in BFS

BFS uses a queue to process vertices in the order they are discovered

Stack or recursion in DFS

DFS can use recursion or a stack to go deep before backtracking

Graph search Big O

O(V + E)

V in O(V + E)

The number of vertices in the graph

E in O(V + E)

The number of edges in the graph

Why graph search is O(V + E)

The search may visit every vertex and examine every edge

Why not O(V + 2E)

Big O drops constants, so V + 2E becomes O(V + E)

Shortest path in an unweighted graph

The path with the fewest number of edges or connections

Shortest path in a weighted graph

The path with the lowest total weight, such as lowest cost or shortest distance

Dijkstra’s Algorithm

An algorithm used to find the shortest path in a weighted graph

Dijkstra use case

Finding the cheapest, shortest, or lowest-cost path through a weighted graph

Cheapest known prices table

A table Dijkstra uses to track the best known cost from the starting vertex to other vertices

Previous stopover table

A table Dijkstra uses to rebuild the final shortest path

Unvisited vertices

Vertices that Dijkstra has not fully processed yet

Dijkstra with array efficiency

Can be O(V²) in the simple implementation from the guide

Dijkstra optimization

A priority queue can make some implementations faster

Main lesson of Chapter 18

Graphs model relationships, and graph algorithms help search connections and find efficient pat