🔝​

Graph Theory

• Graph Theory
  • Books
  • Prerequisites
    • Asymptotic Notation Refresher
      • Big-O, Big-Omega, Big-Theta
    • Quick Examples
  • General Motivation
    • Example 1: GPS Navigation
    • Example 2: Warehouse Robotics
  • Course Content
    • Basic Definitions
      • Graphs
        • Exercise 1 — In-degree and Out-degree
      • Weighted Graphs
      • Paths and Connectivity
    • Graph Representations
      • Adjacency Matrix
        • Analysis
      • Adjacency List
        • Analysis
      • Edge List
        • Analysis
      • Summary and Comparison
        • Summary Takeaway
        • Exercise: Graph Representation in Real-World Scenarios
    • Traversal and Search
      • Breadth-First Search (BFS)
      • Depth-First Search (DFS)
      • Shortest Paths in Weighted Graphs
      • Coding Exercise 1: DFS Traversal and Tree Construction
        • Dijkstra’s Algorithm (1959) [1]
        • A-Star (A*) Search (1968) [2]
        • Exercise 2: Tracing Dijkstra’s Algorithm
        • Exercise 3: A* vs. Dijkstra
        • Traversal Cheat Sheet
  • Credits:
  • References

Books

• Introduction to Algorithms — Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022).
  Comprehensive reference covering algorithm design and analysis, including graph traversal, shortest paths, and spanning trees.

• Introduction to Graph Theory — Richard J. Trudeau.
  A visual and conceptual introduction to the fundamentals of graph theory and mathematical reasoning.

Prerequisites

• Basic Set Theory
  Sets, subsets, unions, intersections, Cartesian products, and relations.
• Data Structures
  Lists, stacks, queues, trees, heaps, and adjacency-based graph representations.
• Algorithmic Complexity
  Big-O notation, asymptotic analysis, and time–space trade-offs.
  Understanding how runtime grows with input size is essential for comparing graph algorithms.

Asymptotic Notation Refresher

Suppose we double the number of intersections in a city map. Will our shortest-path algorithm become twice as slow? Four times? Or barely slower at all? Questions like these arise constantly in graph-based planning, and answering them requires a scale-independent way of describing algorithmic growth.

Asymptotic notation provides this perspective. By focusing on how running time behaves as the graph size grows, rather than on machine-specific measurements, we obtain a clear and comparable description of algorithmic efficiency.

When we analyze graph algorithms, we usually care about how the running time grows with the input size $n$ as $n \to \infty$. We compare functions like $f(n)$ and $g(n)$ using the following notations:

Big-O, Big-Omega, Big-Theta

Intuition: $f$ does not grow faster than $g$, up to constant factors.

While Big-O describes an upper bound, it does not tell us whether the function ever grows faster than the comparison. To capture that aspect, we use Big-Omega.

Intuition: $f$ does not grow slower than $g$.

Neither an upper nor a lower bound alone gives the full picture. When both coincide, we obtain a tight characterization, expressed using Big-Theta.

Intuition: $f$ and $g$ grow at the same rate (up to constant factors).

The three notations form a hierarchy of expressiveness. Together, they let us distinguish between algorithms that merely avoid worst-case blowup and those that are genuinely efficient across all input sizes.

Quick Examples

• $ n^2 = O(n^3) $.
• $ n^3 = \Omega(n^2) $.
• $ 3n^2 + 5n + 7 = \Theta(n^2) $ (same growth rate as $ n^2 $).

We will use these notations throughout to describe the time and space complexity of graph algorithms such as BFS, DFS, Dijkstra, and A*.

With these tools in hand, we can now analyze the complexity of the graph algorithms introduced throughout this chapter.

General Motivation

Before introducing formal definitions, it is useful to understand why graphs arise so naturally in robotics and algorithmic reasoning. Many real-world systems, from transportation to autonomous navigation, can be expressed as collections of states and possible transitions. Graph theory provides the mathematical language for studying these relationships and describing how information or motion can flow through a system.

When a robot navigates an environment, its possible configurations and feasible transitions form exactly such a graph: each node represents a state, and each edge represents a valid move. Motion planning then becomes the problem of finding a path in this graph from an initial configuration to a goal while satisfying feasibility or optimality constraints.

Example 1: GPS Navigation

The most intuitive real-world example of a graph is the road network used by your car’s GPS or a mapping app. Intersections are nodes; road segments are edges. To find the “best” route, we assign each edge a weight (typically travel time), computed from distance, speed limits, and live traffic. A shortest-path algorithm then finds the path with minimum total weight from start to destination.

Example 2: Warehouse Robotics

Autonomous robots navigating a warehouse are another classic example. We can model the warehouse floor as a grid, where each free square is a node. Edges implicitly connect adjacent squares, representing a possible move. While a simple path-finding algorithm on this graph can find the route with the fewest moves, we can add weights to edges to represent “slower” zones or areas to avoid. This model also scales to complex multi-agent problems. To coordinate dozens of robots, the graph can be expanded to include time, allowing a search algorithm to find collision-free paths for the entire fleet.

These examples highlight how diverse systems can be described using the same graph abstraction. To work with such systems rigorously, we next introduce precise definitions for graphs, edges, weights, and paths, forming the mathematical foundation used throughout the rest of this material.

Course Content

Basic Definitions

To formalize the intuitions built from real-world examples, we now introduce the core definitions of graph theory. These definitions establish the vocabulary used for describing connectivity, relationships, and structure within a system, and they serve as the basis for later algorithmic analysis.

Graphs

A graph is one of the simplest and most powerful mathematical abstractions used to represent relationships between entities.
Formally, a graph is an ordered pair

$$ G = (V, E) $$

where $V$ is a finite, nonempty set of vertices (or nodes) and $E$ is a set of edges that connect pairs of vertices.
Each edge can be represented as an ordered or unordered pair $(u, v)$, depending on whether the graph is directed or undirected.

In an undirected graph, $(u, v) \in E$ implies $(v, u) \in E$, meaning that the connection between the two vertices is symmetric. In contrast, directed graphs encode asymmetric relationships, such as one-way communication links, dependencies, or flows of information.

The number of vertices connected to a vertex $v$ is called its degree.
In directed graphs, we often distinguish between the in-degree and out-degree, referring to the number of incoming and outgoing edges respectively.

Weighted Graphs

Many problems require not only knowing whether two vertices are connected, but also how costly that connection is.
A weighted graph extends the definition of $G = (V, E)$ by associating a real-valued weight function

$$ w : E \rightarrow \mathbb{R}^+ $$

that assigns a positive cost or length to each edge.
The weight may represent distance, time, energy, or any quantitative measure of effort required to traverse that edge.

The inclusion of weights allows us to formalize the notion of optimality.
A path connecting two vertices may exist, but the one with minimal total weight is often of greater interest than any arbitrary path.

Paths and Connectivity

A path in a graph is a finite sequence of vertices

$$ P = (v_0, v_1, \ldots, v_k) $$

such that each consecutive pair $(v_i, v_{i+1})$ is an edge in $E$.
The length of a path can refer either to the number of edges it contains (for unweighted graphs) or to the sum of edge weights (for weighted graphs).

A graph is said to be connected if, for every pair of vertices $u$ and $v$, there exists at least one path from $u$ to $v$.
Otherwise, the graph is disconnected, meaning that it consists of multiple connected components that are isolated from one another.
Connectivity plays a central role in determining whether traversal or communication between parts of the graph is possible.

In summary, this chapter introduced the essential components of a graph, vertices, edges, weights, and paths, and showed how these elements encode the structure of a system. With these definitions established, we can now examine how graphs are represented inside a computer, an important consideration for the efficiency of search and planning algorithms.

Graph Representations

Once a graph is defined mathematically, the next question is how to store it efficiently in a computer. Different applications require different operations, fast lookups, memory-efficient storage, or quick neighbor traversal, and the chosen data structure strongly influences algorithmic performance. This chapter compares the three standard representations used in practice.

Before we can run algorithms like BFS or Dijkstra, we must represent the abstract concept of a graph $G = (V, E)$ in a computer’s memory. The choice of representation is a fundamental design decision that has a major impact on both runtime and memory usage.

A representation is a data structure that allows us to store vertices and edges and perform key operations such as:

• Checking if an edge $(u, v)$ exists
• Finding all neighbors of a vertex $v$
• Adding or removing vertices and edges
• Storing and retrieving edge weights

We will explore the three most common methods:

1. Adjacency Matrix
2. Adjacency List
3. Edge List

Adjacency Matrix

An adjacency matrix represents a graph with $V$ vertices as a $V \times V$ matrix (a 2D array) of booleans or weights. For any two vertices $i$ and $j$, the entry $A[i, j]$ stores information about the edge $(i, j)$:

$$ A[i, j] = \begin{cases} w(i, j), & \text{if edge } (i, j) \in E \\
\infty\ \text{(or 0 for unweighted)}, & \text{otherwise} \end{cases} $$

For an undirected graph, the matrix is symmetric, meaning $A[i, j] = A[j, i]$.

Analysis

Pros

• Fast edge lookup: Checking if an edge $(i, j)$ exists or finding its weight is $O(1)$.
• Simple updates: Adding or removing an edge is $O(1)$.

Cons

• High space complexity: Requires $O(V^2)$ space regardless of how many edges exist.
• Inefficient for sparse graphs: Example with $V = 10{,}000$ vertices and each connected to $k = 15$ neighbors:
  $E \approx V \cdot k / 2 = 75{,}000$ edges.
  The matrix stores $V^2 = 10{,}000^2 = 10^8$ entries — over 99.9% are $\infty$.
• Slow neighbor iteration: To find all neighbors of vertex $i$, you must scan its entire row ($O(V)$).

Adjacency List

An adjacency list is the most common representation for sparse graphs. It consists of an array (or map) of $V$ lists. The list at index $i$ stores all neighbors of vertex $i$. For a weighted graph, each entry stores both the neighbor ID and the edge weight.

Analysis

Pros

• Space-efficient: $O(V + E)$ total space.
• Fast neighbor iteration: $O(\text{degree}(i))$, ideal for BFS/Dijkstra.

Cons

• Slower edge lookup: To check if $(i, j)$ exists, you must scan vertex $i$’s list ($O(\text{degree}(i))$).

Edge List

An edge list is the simplest of all representations.
It is a single list (or array) containing all edges in the graph.
For a weighted graph, each entry is a tuple $(u, v, w)$.

Analysis

Pros

• Very simple: Minimal implementation complexity.
• Space-efficient: $O(E)$.
• Ideal for edge-based algorithms such as Kruskal’s Minimum Spanning Tree.

Cons

• Slow neighbor iteration: Finding all neighbors of $i$ requires scanning all $E$ edges ($O(E)$).
• Slow node-centric operations: Adding nodes or checking degrees is inefficient.

Summary and Comparison

The best representation depends entirely on the graph’s density and the operations you need.

Choosing the right representation is a crucial design decision, as it determines which graph algorithms can run efficiently. With a representation selected, we can now study how to explore, traverse, and search graphs using systematic algorithms.

Summary Takeaway

• Use Adjacency Matrix for dense graphs or frequent edge lookups.
• Use Adjacency List for sparse graphs and search algorithms (BFS, Dijkstra, A*).
• Use Edge List for edge-sorted or edge-centric algorithms (Kruskal, clustering, etc.).

Traversal and Search

Graph traversal algorithms reveal the structure of a graph by visiting vertices according to specific rules. These methods form the backbone of motion planning, routing, and connectivity analysis. In this chapter, we examine several classical strategies, starting from uninformed exploration and progressing toward informed, cost-aware search. Once a graph is defined, we can explore it systematically using search algorithms. Traversal algorithms visit nodes according to specific rules, allowing us to enumerate vertices, discover components, or find optimal paths between nodes. Although many variants exist, two of the most fundamental search paradigms are breadth-first and depth-first exploration.

Breadth-First Search (BFS)

We begin with the simplest form of systematic exploration, which visits nodes in increasing order of distance. Breadth-First Search explores a graph in layers, visiting all vertices at distance one from the starting node before proceeding to vertices at distance two, and so on. This systematic expansion guarantees that the first time a vertex is reached, it is reached via the shortest possible path in terms of edge count.

The algorithm maintains a queue of vertices to be explored. When a vertex is dequeued, all of its unvisited neighbors are enqueued for later exploration. The process continues until the queue is empty or a target vertex is reached.

procedure BFS(G, s)
    for each vertex v in G do
        visited[v] ← false
        parent[v] ← NIL
    queue ← empty queue
    visited[s] ← true
    ENQUEUE(queue, s)
    while queue is not empty do
        u ← DEQUEUE(queue)
        for each neighbor v of u do
            if not visited[v] then
                visited[v] ← true
                parent[v] ← u
                ENQUEUE(queue, v)
    return parent

_{Breadth-First Search for Robot Motion Planning. YouTube video, Nov 12, 2017. Available at: https://www.youtube.com/watch?v=x6cGmE0XpY8&list=PLYZT24lofrjXcuu1iBNWu-NprW2wZD3zu&index=43}

Depth-First Search (DFS)

While BFS explores in expanding layers, Depth-First Search follows a single branch of the graph as far as possible before backtracking.
It uses a stack (either explicit or via recursion) to remember the path being followed.
This makes DFS more memory-efficient than BFS, though it does not guarantee finding the shortest path.

DFS is particularly useful for tasks such as detecting cycles, testing graph connectivity, and performing topological sorting in directed acyclic graphs.

procedure DFS(G, s)
    for each vertex v in G do
        visited[v] ← false
    STACK ← empty stack
    PUSH(STACK, s)
    while STACK is not empty do
        u ← POP(STACK)
        if not visited[u] then
            visited[u] ← true
            for each neighbor v of u in reverse order do
                if not visited[v] then
                    PUSH(STACK, v)

By changing the order in which neighbors are pushed onto the stack, DFS can yield different traversal sequences while maintaining the same overall structure.

Shortest Paths in Weighted Graphs

In graphs where edges carry positive weights, we are often interested in the shortest path between two vertices, that is, the path with the minimal total cost.
For a path $P = (v_0, v_1, \ldots, v_k)$, its cost is given by

$$ C(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) $$

The two most classical algorithms for finding shortest paths are Dijkstra’s algorithm and A* search.

Coding Exercise 1: DFS Traversal and Tree Construction

In this exercise, you will implement an iterative Depth-First Search (DFS) on a fixed undirected graph:

def dfs_order(G, start)

Your function should explore the graph starting from the node start and return:

• order: a list of nodes in the order they are first discovered,
• parent: a dictionary mapping each node to its parent in the DFS tree
  (the start node should have parent[start] = None)

After you implement the function, click Run ▶ below to animate your DFS traversal.
The visualization will show:

• red edges for the growing DFS tree,
• light-gray edges for non-tree edges,
• a green start node,
• the current node highlighted during traversal,
• and the discovery order displayed above each visited node.

def dfs_order(G, start): """ Implement Depth-First Search on the given undirected NetworkX graph G, starting from node `start`. Return: order : list of nodes in discovery order parent : dict mapping node -> its parent in the DFS tree (start has None) Hints: - Use an explicit stack (list) for iterative DFS. - When visiting a node for the first time, record its parent and append it to 'order'. - Push neighbors in a consistent order (e.g., sorted) to get deterministic output. """ order = [] parent = {start: None} visited = set() # TODO: replace with your DFS return order, parent

Start node: A B C D E E F G Run ▶ Show Solution 💡

✅ Reference Solution:

def dfs_order(G, start):
    order = []
    parent = {start: None}
    visited = set()
    stack = [(start, None)]
    while stack:
        node, par = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        parent[node] = par
        order.append(node)
        # deterministic neighbor order
        for nb in sorted(G.neighbors(node), reverse=True):
            if nb not in visited:
                stack.append((nb, node))
    return order, parent
    

Output:

Dijkstra’s Algorithm (1959) [1]

BFS and DFS operate under the assumption that all edges have equal cost or that costs are irrelevant. In many real systems, maps, robot motion, energy usage, transitions have different weights. Dijkstra’s algorithm extends the ideas of BFS to handle weighted graphs optimally.

Dijkstra’s algorithm generalizes BFS to weighted graphs by always expanding the vertex with the lowest cumulative cost from the start.
It maintains a priority queue of vertices, ordered by their current best-known distance.

Once a vertex has been expanded, its shortest distance is guaranteed and never updated again.

procedure DIJKSTRA(G, s)
    for each vertex v in G do
        dist[v] ← ∞
        parent[v] ← NIL
    dist[s] ← 0
    Q ← priority queue ordered by dist
    INSERT(Q, s)
    while Q is not empty do
        u ← EXTRACT-MIN(Q)
        for each neighbor v of u do
            alt ← dist[u] + w(u, v)
            if alt < dist[v] then
                dist[v] ← alt
                parent[v] ← u
                DECREASE-KEY(Q, v, alt)
    return dist, parent

The algorithm runs in $\mathcal{O}((V + E)\log V)$ time when implemented with a binary heap. It guarantees optimality when all edge weights are positive.

The efficiency of Dijkstra’s algorithm depends primarily on how the priority queue is implemented. Each vertex is inserted once into the queue and may be updated (via a ‘decrease-key’ operation) whenever a shorter path is found. Using a binary heap, both ‘insertion’ and ‘extraction’ of the minimum element take $O(\log V)$ time. Since every edge can cause at most one key update, there are up to $O(E)$ decrease-key operations and $O(V)$ extractions overall. This yields a total running time of $O((V + E)\log V)$, which simplifies to $O(E\log V)$ for sparse graphs where $E \approx O(V)$.
For dense graphs, where $E$ grows quadratically with $V$, the complexity approaches $O(V^2 \log V)$. In practice, the algorithm performs efficiently on most real-world graphs because they are typically sparse.

A-Star (A*) Search (1968) [2]

While Dijkstra’s algorithm finds optimal paths in weighted graphs, it does so without any knowledge of the goal’s location. In many applications, we can estimate how promising a particular direction might be. A* search incorporates this information through heuristics, guiding the algorithm toward the goal more efficiently.

A* extends Dijkstra’s algorithm by adding a heuristic function $h(v)$ that estimates the remaining cost from a vertex $v$ to the goal. This heuristic guides the search toward promising directions, potentially reducing the number of expanded nodes.

Each vertex maintains two quantities:
$g(v)$ — the cost from the start to $v$, and
$f(v) = g(v) + h(v)$ — the estimated total cost through $v$.

The algorithm always expands the vertex with the lowest $f(v)$. If the heuristic is admissible (never overestimates the true cost), the resulting path is guaranteed to be optimal.

procedure ASTAR(G, s, goal, h)
    for each vertex v in G do
        g[v] ← ∞
        f[v] ← ∞
        parent[v] ← NIL
    g[s] ← 0
    f[s] ← h(s)
    OPEN ← priority queue ordered by f
    INSERT(OPEN, s)
    while OPEN is not empty do
        u ← EXTRACT-MIN(OPEN)
        if u = goal then
            return RECONSTRUCT-PATH(parent, u)
        for each neighbor v of u do
            tentative ← g[u] + w(u, v)
            if tentative < g[v] then
                g[v] ← tentative
                f[v] ← g[v] + h(v)
                parent[v] ← u
                INSERT-OR-DECREASE(OPEN, v, f[v])

When $h(v) = 0$ for all vertices, A* reduces to Dijkstra’s algorithm. When $h$ is perfectly accurate, the algorithm expands only the nodes along the optimal path.

_{The hidden beauty of the A* algorithm. YouTube video by Polylog, Jan 20, 2023. Available at: https://www.youtube.com/watch?v=A60q6dcoCjw}

Together, BFS, DFS, Dijkstra, and A* form the foundation of graph search theory, illustrating how the structure of a graph and the information available about costs or heuristics influence the efficiency and guarantees of traversal algorithms.

Traversal Cheat Sheet

The following table summarizes the core properties of the traversal algorithms introduced so far.

Together, BFS, DFS, Dijkstra, and A* illustrate a progression from uninformed to informed search. As we refine our knowledge about the environment, edge costs, heuristic estimates, the algorithms become increasingly efficient while still guaranteeing correctness under appropriate conditions.

Credits:

This course page was created by Hanka Goralija, EPFL under the supervision of Prof. Aude Billard, and funded by IEEE RAS and EPFL.

References

1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271.
2. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.

Back to Top