Graph | Dheerendra Varma

What is a Graph?

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices. Edges can be directed (one-way) or undirected (two-way). Weights assigned to edges represent costs, distances, or capacities.

Key terminology: a path is a sequence of vertices where consecutive pairs are connected by edges. A cycle is a path that starts and ends at the same vertex. A connected graph has a path between every pair of vertices. A DAG (Directed Acyclic Graph) is a directed graph with no cycles — the structure that represents build systems, course prerequisites, and computation graphs. The degree of a vertex is the number of edges incident to it; in directed graphs, in-degree counts incoming edges and out-degree counts outgoing edges.

Trees are a special case of graphs: connected, undirected, and acyclic. Adding any edge to a tree creates exactly one cycle. Removing any edge from a tree disconnects it.

Applications

Social networks model users as vertices and friendships as edges — "friends of friends" is a BFS problem. Google Maps models intersections as vertices and roads as weighted edges — shortest path is Dijkstra's algorithm. Package managers like Cargo model packages as vertices and dependencies as directed edges — install order is topological sort. Web crawlers model pages as vertices and hyperlinks as directed edges. Airline networks, circuit boards, and neural networks are all graphs.

Representations

The adjacency list is the standard representation for sparse graphs. Each vertex stores a list of its neighbours. Space complexity is O(V + E) and getting all neighbours of a vertex takes O(degree) time.

struct Graph {
    n: usize,
    adj: Vec<Vec<usize>>,        // unweighted
}
 
impl Graph {
    fn new(n: usize) -> Self {
        Graph { n, adj: vec![vec![]; n] }
    }
 
    fn add_edge_directed(&mut self, u: usize, v: usize) {
        self.adj[u].push(v);
    }
 
    fn add_edge_undirected(&mut self, u: usize, v: usize) {
        self.adj[u].push(v);
        self.adj[v].push(u);
    }
 
    fn neighbours(&self, u: usize) -> &[usize] {
        &self.adj[u]
    }
}
 
// Weighted adjacency list: (neighbour, weight)
struct WeightedGraph {
    adj: Vec<Vec<(usize, i32)>>,
}
 
impl WeightedGraph {
    fn new(n: usize) -> Self {
        WeightedGraph { adj: vec![vec![]; n] }
    }
 
    fn add_edge(&mut self, u: usize, v: usize, w: i32) {
        self.adj[u].push((v, w));
        self.adj[v].push((u, w)); // undirected
    }
}

The adjacency matrix uses a 2D array where matrix[u][v] is the edge weight (0 if no edge). Space is O(V²). Edge existence checks are O(1) but iterating neighbours is O(V). Prefer the matrix only for dense graphs where E ≈ V².

struct MatrixGraph {
    matrix: Vec<Vec<i32>>, // 0 = no edge
}
 
impl MatrixGraph {
    fn new(n: usize) -> Self {
        MatrixGraph { matrix: vec![vec![0; n]; n] }
    }
 
    fn add_edge(&mut self, u: usize, v: usize, w: i32) {
        self.matrix[u][v] = w;
        self.matrix[v][u] = w; // undirected
    }
 
    fn has_edge(&self, u: usize, v: usize) -> bool {
        self.matrix[u][v] != 0
    }
}

An edge list Vec<(usize, usize, i32)> stores all edges directly. Space is O(E). Used in Kruskal's MST algorithm which needs to sort all edges by weight.

Operations and Time Complexity

Operation	Adjacency List	Adjacency Matrix
Add vertex	O(1)	O(V²) rebuild
Add edge	O(1)	O(1)
Check edge (u,v)	O(degree(u))	O(1)
Get neighbours	O(degree)	O(V)
DFS / BFS	O(V + E)	O(V²)
Space	O(V + E)	O(V²)

Implementation in Rust

use std::collections::VecDeque;
 
fn dfs(adj: &Vec<Vec<usize>>, start: usize, visited: &mut Vec<bool>, order: &mut Vec<usize>) {
    visited[start] = true;
    order.push(start);
    for &next in &adj[start] {
        if !visited[next] {
            dfs(adj, next, visited, order);
        }
    }
}
 
fn bfs(adj: &Vec<Vec<usize>>, start: usize, n: usize) -> Vec<usize> {
    let mut visited = vec![false; n];
    let mut queue = VecDeque::new();
    let mut order = Vec::new();
    visited[start] = true;
    queue.push_back(start);
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &next in &adj[node] {
            if !visited[next] {
                visited[next] = true;
                queue.push_back(next);
            }
        }
    }
    order
}
 
fn connected_components(adj: &Vec<Vec<usize>>, n: usize) -> usize {
    let mut visited = vec![false; n];
    let mut components = 0;
    for i in 0..n {
        if !visited[i] {
            let mut order = Vec::new();
            dfs(adj, i, &mut visited, &mut order);
            components += 1;
        }
    }
    components
}

Fundamental Algorithms and Problems

BFS — Shortest Path with Path Reconstruction

BFS guarantees the shortest path in an unweighted graph because it explores vertices in order of their distance from the source. Track a parent array to reconstruct the actual path once the destination is reached.

use std::collections::VecDeque;
 
fn bfs_shortest_path(adj: &Vec<Vec<usize>>, src: usize, dst: usize, n: usize) -> Option<Vec<usize>> {
    let mut visited = vec![false; n];
    let mut parent  = vec![usize::MAX; n];
    let mut queue   = VecDeque::new();
 
    visited[src] = true;
    queue.push_back(src);
 
    while let Some(node) = queue.pop_front() {
        if node == dst {
            // Reconstruct path
            let mut path = vec![dst];
            let mut curr = dst;
            while curr != src {
                curr = parent[curr];
                path.push(curr);
            }
            path.reverse();
            return Some(path);
        }
        for &next in &adj[node] {
            if !visited[next] {
                visited[next] = true;
                parent[next] = node;
                queue.push_back(next);
            }
        }
    }
    None
}
 
fn main() {
    let n = 6;
    let mut adj = vec![vec![]; n];
    for (u, v) in [(0,1),(0,2),(1,3),(2,4),(3,5),(4,5)] {
        adj[u].push(v); adj[v].push(u);
    }
    println!("{:?}", bfs_shortest_path(&adj, 0, 5, n));
    // Some([0, 1, 3, 5]) or Some([0, 2, 4, 5])
}

Cycle Detection — Undirected and Directed Graphs

In an undirected graph, DFS detects a cycle if it reaches a visited vertex that is not the parent of the current vertex. In a directed graph, DFS uses a three-colour scheme: white (unvisited), grey (in the current recursion stack), black (fully processed). A back edge — reaching a grey vertex — indicates a cycle.

// Undirected cycle detection
fn has_cycle_undirected(adj: &Vec<Vec<usize>>, n: usize) -> bool {
    let mut visited = vec![false; n];
 
    fn dfs_u(adj: &Vec<Vec<usize>>, node: usize, parent: usize, visited: &mut Vec<bool>) -> bool {
        visited[node] = true;
        for &next in &adj[node] {
            if !visited[next] {
                if dfs_u(adj, next, node, visited) { return true; }
            } else if next != parent {
                return true; // back edge
            }
        }
        false
    }
 
    for i in 0..n {
        if !visited[i] && dfs_u(adj, i, usize::MAX, &mut visited) {
            return true;
        }
    }
    false
}
 
// Directed cycle detection (0=white, 1=grey, 2=black)
fn has_cycle_directed_dfs(adj: &Vec<Vec<usize>>, node: usize, color: &mut Vec<u8>) -> bool {
    color[node] = 1; // grey
    for &next in &adj[node] {
        if color[next] == 1 { return true; } // back edge
        if color[next] == 0 && has_cycle_directed_dfs(adj, next, color) { return true; }
    }
    color[node] = 2; // black
    false
}
 
fn has_cycle_directed(adj: &Vec<Vec<usize>>, n: usize) -> bool {
    let mut color = vec![0u8; n];
    (0..n).any(|i| color[i] == 0 && has_cycle_directed_dfs(adj, i, &mut color))
}
 
fn main() {
    let n = 4;
    let adj_acyclic   = vec![vec![1,2], vec![3], vec![3], vec![]];
    let adj_cyclic    = vec![vec![1], vec![2], vec![0], vec![]];
    println!("{}", has_cycle_directed(&adj_acyclic, n)); // false
    println!("{}", has_cycle_directed(&adj_cyclic,  n)); // true
}

Topological Sort — Kahn's Algorithm

Topological sort orders the vertices of a DAG such that every directed edge (u, v) has u appearing before v. It exists if and only if the graph has no directed cycles. Kahn's algorithm computes in-degrees for all vertices, then repeatedly dequeues vertices with in-degree zero and decrements the in-degree of their neighbours. If all vertices are processed, the graph is a DAG; if some remain, they form a cycle.

use std::collections::VecDeque;
 
fn topological_sort(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    let mut in_degree = vec![0usize; n];
 
    for &(u, v) in edges {
        adj[u].push(v);
        in_degree[v] += 1;
    }
 
    let mut queue: VecDeque<usize> = (0..n).filter(|&i| in_degree[i] == 0).collect();
    let mut order = Vec::new();
 
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &next in &adj[node] {
            in_degree[next] -= 1;
            if in_degree[next] == 0 { queue.push_back(next); }
        }
    }
 
    if order.len() == n { Some(order) } else { None } // None = cycle detected
}
 
fn main() {
    // Course prerequisites: 0->2, 1->2, 2->3
    let edges = [(0,2),(1,2),(2,3)];
    println!("{:?}", topological_sort(4, &edges)); // Some([0, 1, 2, 3])
 
    // Graph with cycle: 0->1->2->0
    let cyclic = [(0,1),(1,2),(2,0)];
    println!("{:?}", topological_sort(3, &cyclic)); // None
}

Union-Find — Disjoint Set Union

Union-Find efficiently answers "are these two vertices in the same connected component?" and "does adding this edge create a cycle?". Each element starts in its own set. find returns the root representative of an element's set, using path compression to flatten the tree. union merges two sets by rank — attach the smaller-rank tree under the larger-rank root — preventing the tree from becoming a chain.

struct UnionFind {
    parent: Vec<usize>,
    rank:   Vec<usize>,
}
 
impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind { parent: (0..n).collect(), rank: vec![0; n] }
    }
 
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]); // path compression
        }
        self.parent[x]
    }
 
    fn union(&mut self, x: usize, y: usize) -> bool {
        let (px, py) = (self.find(x), self.find(y));
        if px == py { return false; } // already connected — adding edge creates cycle
        match self.rank[px].cmp(&self.rank[py]) {
            std::cmp::Ordering::Less    => self.parent[px] = py,
            std::cmp::Ordering::Greater => self.parent[py] = px,
            std::cmp::Ordering::Equal   => { self.parent[py] = px; self.rank[px] += 1; }
        }
        true
    }
 
    fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}
 
fn main() {
    let mut uf = UnionFind::new(5);
    uf.union(0, 1);
    uf.union(1, 2);
    uf.union(3, 4);
 
    println!("{}", uf.connected(0, 2)); // true
    println!("{}", uf.connected(0, 3)); // false
    println!("{}", uf.union(2, 0));     // false (already same set — would create cycle)
}

DFS — Find All Connected Components

Run DFS from every unvisited vertex. Each DFS call from a new starting vertex discovers exactly one connected component. This is the building block of "number of islands", "friend circles", and "number of provinces" problems.

fn all_components(adj: &Vec<Vec<usize>>, n: usize) -> Vec<Vec<usize>> {
    let mut visited = vec![false; n];
    let mut components = Vec::new();
 
    for i in 0..n {
        if !visited[i] {
            let mut component = Vec::new();
            dfs(adj, i, &mut visited, &mut component);
            components.push(component);
        }
    }
    components
}
 
fn main() {
    let n = 7;
    let mut adj = vec![vec![]; n];
    for (u, v) in [(0,1),(0,2),(1,2),(3,4),(5,6)] {
        adj[u].push(v); adj[v].push(u);
    }
    let comps = all_components(&adj, n);
    println!("components: {}", comps.len()); // 3
    for (i, c) in comps.iter().enumerate() {
        println!("  component {i}: {:?}", c);
    }
}