Chapter 6: Graph and Tree Algorithms

Graphs and trees model connections and relationships. They form the foundation of countless problems in computing, from social networks and navigation systems to compilers and search engines. Understanding their structure and the algorithms that operate on them is essential to advanced coding and efficient design.

Understanding Graphs and Networks

A graph consists of vertices (also called nodes) and edges that connect them. Edges may be directed or undirected, and they can also carry weights that represent cost, distance, or strength of connection. Graphs can be stored as adjacency lists, adjacency matrices, or edge lists depending on the type of operations required.

Common graph representations

An adjacency list stores for each vertex the list of its neighbours. This is efficient for sparse graphs with relatively few edges. An adjacency matrix uses a two-dimensional array and is convenient for dense graphs but requires more memory.

# adjacency list example
graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'D'],
  'D': ['B', 'C']
}

Directed, weighted, and undirected graphs

In directed graphs, edges have directio, such as links on the web where one page points to another. Weighted graphs attach a numerical value to each edge, representing distance, time, or cost. Many real-world systems combine both properties, creating directed weighted networks.

Breadth-First and Depth-First Search

Traversal algorithms explore the structure of a graph. Breadth-first search (BFS) visits vertices level by level, while depth-first search (DFS) explores as far as possible along each branch before backtracking. Both are key for discovering paths, detecting connectivity, and exploring problem states.

Breadth-first search

BFS uses a queue to visit vertices in order of distance from the starting point. It guarantees the shortest path in an unweighted graph and forms the foundation of many pathfinding algorithms.

from collections import deque

def bfs(graph, start):
  visited = set([start])
  queue = deque([start])
  order = []

  while queue:
    v = queue.popleft()
    order.append(v)
    for n in graph[v]:
      if n not in visited:
        visited.add(n)
        queue.append(n)
  return order

Depth-first search

DFS uses a stack (explicitly or through recursion) to dive deep into each branch before exploring siblings. It is often used for tasks like cycle detection, topological sorting, and component analysis.

def dfs(graph, start, visited=None):
  if visited is None:
    visited = set()
  visited.add(start)
  for n in graph[start]:
    if n not in visited:
      dfs(graph, n, visited)
  return visited

Minimum Spanning Trees

A spanning tree connects all vertices of a graph with the smallest possible number of edges. A minimum spanning tree (MST) is one whose total edge weight is minimal. MSTs are important in network design, clustering, and circuit layout.

Kruskal’s algorithm

Kruskal’s algorithm builds an MST by sorting all edges by weight and adding them one by one, skipping those that would form a cycle. It uses a disjoint-set data structure to track which vertices are already connected.

def kruskal(n, edges):
  parent = list(range(n))
  def find(x):
    if parent[x] != x:
      parent[x] = find(parent[x])
    return parent[x]
  def union(a, b):
    pa, pb = find(a), find(b)
    if pa != pb:
      parent[pb] = pa

  mst = []
  for u, v, w in sorted(edges, key=lambda x: x[2]):
    if find(u) != find(v):
      union(u, v)
      mst.append((u, v, w))
  return mst

Prim’s algorithm

Prim’s algorithm starts from any vertex and grows the MST by repeatedly adding the smallest edge that connects a new vertex to the tree. It works well with adjacency lists and a priority queue.

import heapq

def prim(n, adj):
  visited = [False] * n
  pq = [(0, 0, -1)]  # weight, vertex, parent
  mst = []
  while pq:
    w, u, p = heapq.heappop(pq)
    if visited[u]:
      continue
    visited[u] = True
    if p != -1:
      mst.append((p, u, w))
    for v, w2 in adj[u]:
      if not visited[v]:
        heapq.heappush(pq, (w2, v, u))
  return mst

Balanced Trees and Heaps

Trees are hierarchical data structures where each node can have children. They are widely used for indexing, searching, and maintaining sorted order. Balanced trees and heaps keep operations efficient even as data grows.

Binary search trees

In a binary search tree (BST), all keys in the left subtree are smaller than the node’s key, and all keys in the right subtree are larger. Searching, insertion, and deletion can all run in O(log n) time if the tree remains balanced.

Heaps and priority queues

A heap is a complete binary tree that satisfies the heap property: each node is smaller (in a min-heap) or larger (in a max-heap) than its children. Python’s heapq module provides an efficient heap-based priority queue implementation.

import heapq

nums = [8, 3, 6, 1, 9]
heapq.heapify(nums)
heapq.heappush(nums, 2)
smallest = heapq.heappop(nums)

Graphs in Real-World Systems

Graphs and trees are everywhere in technology. They describe routes, dependencies, and hierarchies, providing structure to complex systems. Algorithms built on them drive search engines, compilers, and social platforms alike.

Network routing and logistics

Routing algorithms in the Internet or in transport networks rely on graph traversal and pathfinding to find efficient routes. Dijkstra’s and A* algorithms both operate on graph principles to minimise total cost or time.

Data structures and hierarchies

Trees model parent–child relationships naturally, which makes them ideal for representing file systems, XML and JSON documents, or organisational charts. Their recursive definition also simplifies many algorithms that process nested data.

Recommendation and influence networks

Social and recommendation systems use graph algorithms to evaluate relationships between entities. Concepts such as centrality, clustering, and flow all stem from the fundamental graph algorithms introduced in this chapter.