A graph is a set of vertices joined by edges — the most general way to store pairwise relationships. Road maps, social networks, task dependencies and the web are all graphs, and almost every algorithm here (BFS, DFS, topological sort, Dijkstra, MST) is an interview staple.

A graph with |V| = 5 and |E| = 6, next to a tree (a connected graph with no cycles)

Graph                                    Tree

v1 ───── v3                                  v1
│        │ ╲                                ╱  ╲
│        │  v5                            v2    v3
│        │ ╱
v2 ───── v4

V = {v1, v2, v3, v4, v5}
E = {(v1,v2), (v1,v3), (v2,v4), (v3,v4), (v3,v5), (v4,v5)}

Graph vs tree

	Tree	Graph
Edges	Exactly `n − 1` for `n` nodes	Any number, `0 … V(V−1)/2` (undirected)
Cycles	Never	Allowed
Connected	Always	May be disconnected
Root / hierarchy	One root, parent → child	No root; vertices are peers
Traversal	Pre/in/post-order, level order	BFS / DFS with a `visited` array (cycles would loop forever)

Directed and undirected graphs

Edges with a direction (arcs) versus symmetric edges

Directed graph                 Undirected graph

v1 ─────▶ v3                   v1 ───── v3
▲         ▲                    │        │ ╲
│         │                    │        │  v5
│         │                    │        │ ╱
v2 ─────▶ v4                   v2 ───── v4

indegree(v3)  = 2              degree(v3) = 3
outdegree(v3) = 0

	Directed graph (digraph)	Undirected graph
Edge `(u, v)`	Goes from `u` to `v` only	Joins `u` and `v` both ways
Degree	`indegree(v)` = edges into `v`, `outdegree(v)` = edges out of `v`	`degree(v)` = number of edges touching `v`
Degree sum	`Σ indegree = Σ outdegree = \|E\|`	`Σ degree = 2·\|E\|` (every edge is counted at both ends)
Maximum edges (no self-loops)	`\|V\| · (\|V\| − 1)` — every ordered pair	`\|V\| · (\|V\| − 1) / 2` — every unordered pair
Examples	Web links, task dependencies, follows on Twitter	Roads, friendships, electrical circuits

Undirected: 0 ≤ |E| ≤ |V|(|V|−1)/2 Directed: 0 ≤ |E| ≤ |V|(|V|−1)

Walk, path and cycle

In the undirected graph above:

Walk — any sequence of vertices where consecutive vertices are adjacent; vertices and edges may repeat: v1, v2, v4, v3, v1, v2.
Path — a walk with no repeated vertex: v1, v2, v4.
Cycle — a walk that starts and ends at the same vertex (a simple cycle repeats no other vertex): v1, v2, v4, v3, v1.
Connected (undirected) — a path exists between every pair of vertices. Strongly connected (directed) — a directed path exists in both directions between every pair.

Weighted and unweighted graphs

A weight (cost, distance, time, capacity) on every edge, or none

   Weighted                             Unweighted

        10                              v1 ───── v3
   v1 ─────── v3                        │        │ ╲
   │          │ ╲ 5                     │        │  v5
20 │       50 │  v5                     │        │ ╱
   │          │ ╱ 60                    v2 ───── v4
   v2 ─────── v4
        30

Unweighted — every edge counts as 1. The shortest path is the one with the fewest edges and BFS finds it.
Weighted — each edge carries a number. The shortest path minimises the sum of weights: Dijkstra (non-negative weights), Bellman–Ford (negative weights allowed), or a single pass over a topological order (DAGs).
Weights can be negative; a negative cycle makes “shortest path” undefined because going round it again always lowers the total.

Representation: adjacency matrix

A V × V matrix with mat[i][j] = 1 (or the weight) when there is an edge from i to j, else 0. An undirected graph gives a symmetric matrix; a directed graph does not.

Edges 0-1, 0-2, 1-2, 2-3 as a matrix — symmetric when undirected

Undirected                           Directed

0 ───── 1          0 1 2 3          0 ────▶ 1           0 1 2 3
│     ╱         0  0 1 1 0          │     ╱          0  0 1 1 0
│   ╱           1  1 0 1 0          │   ╱            1  0 0 1 0
│ ╱             2  1 1 0 1          ▼ ◀              2  0 0 0 1
2 ───── 3       3  0 0 1 0          2 ────▶ 3        3  0 0 0 0

Python

def build_matrix(n, edges, directed=False):
    mat = [[0] * n for _ in range(n)]
    for u, v in edges:
        mat[u][v] = 1
        if not directed:
            mat[v][u] = 1              # undirected: the matrix is symmetric
    return mat

edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
mat = build_matrix(4, edges)
for row in mat:
    print(*row)
print("adjacent(1, 2):", "true" if mat[1][2] else "false")   # O(1) lookup
print("adjacent(0, 3):", "true" if mat[0][3] else "false")
print("degree(2):", sum(mat[2]))                               # O(V): scan one row

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> buildMatrix(int n, const vector<pair<int,int>>& edges, bool directed) {
    vector<vector<int>> mat(n, vector<int>(n, 0));
    for (auto [u, v] : edges) {
        mat[u][v] = 1;
        if (!directed) mat[v][u] = 1;      // undirected: the matrix is symmetric
    }
    return mat;
}

int main() {
    vector<pair<int,int>> edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
    auto mat = buildMatrix(4, edges, false);
    for (auto& row : mat) {
        for (int x : row) cout << x << " ";
        cout << "\n";
    }
    cout << "adjacent(1, 2): " << (mat[1][2] ? "true" : "false") << "\n";   // O(1) lookup
    cout << "adjacent(0, 3): " << (mat[0][3] ? "true" : "false") << "\n";
    int deg = 0;
    for (int x : mat[2]) deg += x;                                           // O(V): scan one row
    cout << "degree(2): " << deg << "\n";
}

Java

public class Main {
    static int[][] buildMatrix(int n, int[][] edges, boolean directed) {
        int[][] mat = new int[n][n];
        for (int[] e : edges) {
            mat[e[0]][e[1]] = 1;
            if (!directed) mat[e[1]][e[0]] = 1;    // undirected: the matrix is symmetric
        }
        return mat;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
        int[][] mat = buildMatrix(4, edges, false);
        for (int[] row : mat) {
            StringBuilder sb = new StringBuilder();
            for (int x : row) sb.append(x).append(' ');
            System.out.println(sb.toString().trim());
        }
        System.out.println("adjacent(1, 2): " + (mat[1][2] == 1 ? "true" : "false"));   // O(1) lookup
        System.out.println("adjacent(0, 3): " + (mat[0][3] == 1 ? "true" : "false"));
        int deg = 0;
        for (int x : mat[2]) deg += x;                                                    // O(V): scan one row
        System.out.println("degree(2): " + deg);
    }
}

JavaScript

function buildMatrix(n, edges, directed = false) {
    const mat = Array.from({ length: n }, () => new Array(n).fill(0));
    for (const [u, v] of edges) {
        mat[u][v] = 1;
        if (!directed) mat[v][u] = 1;          // undirected: the matrix is symmetric
    }
    return mat;
}

const edges = [[0, 1], [0, 2], [1, 2], [2, 3]];
const mat = buildMatrix(4, edges);
for (const row of mat) console.log(row.join(" "));
console.log("adjacent(1, 2):", mat[1][2] ? "true" : "false");   // O(1) lookup
console.log("adjacent(0, 3):", mat[0][3] ? "true" : "false");
console.log("degree(2):", mat[2].reduce((a, b) => a + b, 0));   // O(V): scan one row

Output

0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
adjacent(1, 2): true
adjacent(0, 3): false
degree(2): 3

Adjacency matrix	Cost
Space	`Θ(V²)` — even for a graph with very few edges
Is `u` adjacent to `v`?	`Θ(1)` — read `mat[u][v]`
All neighbours of `u`	`Θ(V)` — scan row `u`
Degree of `u`	`Θ(V)` — count the 1s in row `u`
Add / remove an edge	`Θ(1)`
Add / remove a vertex	`Θ(V²)` — the whole matrix is rebuilt

Vertices with arbitrary names

Algorithms index arrays by vertex number, but real vertices are cities, user ids or strings. Keep two mappings: a hash map name → index to translate input, and an array index → name (just the list of names) to translate results back. Everything in between runs on plain integers.

Python

names = ["Delhi", "Mumbai", "Chennai", "Kolkata"]
index = {name: i for i, name in enumerate(names)}        # name -> vertex number
edges = [("Delhi", "Mumbai"), ("Delhi", "Kolkata"), ("Mumbai", "Chennai"), ("Chennai", "Kolkata")]

adj = [[] for _ in names]
for a, b in edges:
    u, v = index[a], index[b]                             # translate once, on input
    adj[u].append(v)
    adj[v].append(u)

for u, name in enumerate(names):                          # names[i] is the reverse mapping
    print(name + ":", " ".join(names[v] for v in adj[u]))
print("index of Chennai:", index["Chennai"])

C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    vector<string> names = {"Delhi", "Mumbai", "Chennai", "Kolkata"};
    unordered_map<string, int> index;                      // name -> vertex number
    for (int i = 0; i < (int)names.size(); i++) index[names[i]] = i;
    vector<pair<string, string>> edges = {{"Delhi", "Mumbai"}, {"Delhi", "Kolkata"},
                                          {"Mumbai", "Chennai"}, {"Chennai", "Kolkata"}};

    vector<vector<int>> adj(names.size());
    for (auto& [a, b] : edges) {
        int u = index[a], v = index[b];                    // translate once, on input
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int u = 0; u < (int)names.size(); u++) {         // names[i] is the reverse mapping
        cout << names[u] << ":";
        for (int v : adj[u]) cout << " " << names[v];
        cout << "\n";
    }
    cout << "index of Chennai: " << index["Chennai"] << "\n";
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Delhi", "Mumbai", "Chennai", "Kolkata"};
        Map<String, Integer> index = new HashMap<>();          // name -> vertex number
        for (int i = 0; i < names.length; i++) index.put(names[i], i);
        String[][] edges = {{"Delhi", "Mumbai"}, {"Delhi", "Kolkata"},
                            {"Mumbai", "Chennai"}, {"Chennai", "Kolkata"}};

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < names.length; i++) adj.add(new ArrayList<>());
        for (String[] e : edges) {
            int u = index.get(e[0]), v = index.get(e[1]);    // translate once, on input
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        for (int u = 0; u < names.length; u++) {             // names[i] is the reverse mapping
            StringBuilder sb = new StringBuilder(names[u] + ":");
            for (int v : adj.get(u)) sb.append(' ').append(names[v]);
            System.out.println(sb);
        }
        System.out.println("index of Chennai: " + index.get("Chennai"));
    }
}

JavaScript

const names = ["Delhi", "Mumbai", "Chennai", "Kolkata"];
const index = new Map(names.map((name, i) => [name, i]));    // name -> vertex number
const edges = [["Delhi", "Mumbai"], ["Delhi", "Kolkata"], ["Mumbai", "Chennai"], ["Chennai", "Kolkata"]];

const adj = names.map(() => []);
for (const [a, b] of edges) {
    const u = index.get(a), v = index.get(b);                // translate once, on input
    adj[u].push(v);
    adj[v].push(u);
}

names.forEach((name, u) =>                                   // names[i] is the reverse mapping
    console.log(name + ":", adj[u].map(v => names[v]).join(" ")));
console.log("index of Chennai:", index.get("Chennai"));

Output

Delhi: Mumbai Kolkata
Mumbai: Delhi Chennai
Chennai: Mumbai Kolkata
Kolkata: Delhi Chennai
index of Chennai: 2

Representation: adjacency list

An array of V lists; adj[u] holds the neighbours of u (for a weighted graph, (neighbour, weight) pairs). The lists are usually dynamic arrays (vector, ArrayList, Python list) — linked lists also work but are slower to scan. This is the default representation for every algorithm in these notes.

The same undirected graph as a list of neighbour lists — each edge appears twice

0 ───── 1            adj[0] → 1 → 2
│     ╱              adj[1] → 0 → 2
│   ╱                adj[2] → 0 → 1 → 3
│ ╱                  adj[3] → 2
2 ───── 3

Python

def build(n, edges, directed=False):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)               # undirected: store the edge at both ends
    return adj

adj = build(4, [(0, 1), (0, 2), (1, 2), (2, 3)])
for u in range(len(adj)):
    print(f"{u}:", *adj[u])
print("degree(2):", len(adj[2]))                               # O(1)
print("has edge 1-3:", "true" if 3 in adj[1] else "false")     # O(degree(1)) scan

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges, bool directed) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        if (!directed) adj[v].push_back(u);    // undirected: store the edge at both ends
    }
    return adj;
}

int main() {
    auto adj = build(4, {{0, 1}, {0, 2}, {1, 2}, {2, 3}}, false);
    for (int u = 0; u < (int)adj.size(); u++) {
        cout << u << ":";
        for (int v : adj[u]) cout << " " << v;
        cout << "\n";
    }
    cout << "degree(2): " << adj[2].size() << "\n";                       // O(1)
    bool has = find(adj[1].begin(), adj[1].end(), 3) != adj[1].end();   // O(degree(1)) scan
    cout << "has edge 1-3: " << (has ? "true" : "false") << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);   // undirected: store the edge at both ends
        }
        return adj;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(4, new int[][]{{0, 1}, {0, 2}, {1, 2}, {2, 3}}, false);
        for (int u = 0; u < adj.size(); u++) {
            StringBuilder sb = new StringBuilder(u + ":");
            for (int v : adj.get(u)) sb.append(' ').append(v);
            System.out.println(sb);
        }
        System.out.println("degree(2): " + adj.get(2).size());                    // O(1)
        System.out.println("has edge 1-3: " + (adj.get(1).contains(3) ? "true" : "false"));   // O(degree(1))
    }
}

JavaScript

function build(n, edges, directed = false) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        if (!directed) adj[v].push(u);         // undirected: store the edge at both ends
    }
    return adj;
}

const adj = build(4, [[0, 1], [0, 2], [1, 2], [2, 3]]);
adj.forEach((nbrs, u) => console.log(`${u}:`, nbrs.join(" ")));
console.log("degree(2):", adj[2].length);                                 // O(1)
console.log("has edge 1-3:", adj[1].includes(3) ? "true" : "false");      // O(degree(1)) scan

Output

0: 1 2
1: 0 2
2: 0 1 3
3: 2
degree(2): 3
has edge 1-3: false

Adjacency list	Cost
Space	`Θ(V + E)` — `V + 2E` list entries undirected, `V + E` directed
Is `u` adjacent to `v`?	`O(degree(u))` — scan `adj[u]` (`O(1)` if each list is a hash set)
All neighbours of `u`	`Θ(degree(u))`
Degree of `u`	`Θ(1)` — the list length
Add an edge	`Θ(1)` — append
Remove an edge	`O(degree(u))` — find it first

Adjacency list vs adjacency matrix

Operation	Adjacency list	Adjacency matrix
Memory	`Θ(V + E)`	`Θ(V²)`
Is there an edge `u → v`?	`O(degree(u))`, worst `O(V)`	`Θ(1)`
Visit all neighbours of `u`	`Θ(degree(u))`	`Θ(V)`
Add an edge	`Θ(1)`	`Θ(1)`
Remove an edge	`O(V)`	`Θ(1)`
Whole traversal (BFS / DFS)	`Θ(V + E)`	`Θ(V²)`

Breadth First Search (BFS)

BFS explores a graph level by level from a source: first the source, then every vertex one edge away, then two edges away, and so on. A queue holds the frontier; a visited array stops cycles from being walked twice.

The traversal graph used for BFS and DFS: edges 0-1, 0-2, 1-3, 2-3, 2-4, 3-5, 4-5

0 ───── 1          level 0:  0
│       │          level 1:  1 2
2 ───── 3          level 2:  3 4
│       │          level 3:  5
4 ───── 5

Python

from collections import deque

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def bfs(adj, s):
    visited = [False] * len(adj)
    order = []
    q = deque([s])
    visited[s] = True                 # mark when enqueued, not when dequeued
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
    return order

adj = build(6, [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)])
print("from 0:", *bfs(adj, 0))
print("from 2:", *bfs(adj, 2))

C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

vector<int> bfs(const vector<vector<int>>& adj, int s) {
    vector<bool> visited(adj.size(), false);
    vector<int> order;
    queue<int> q;
    q.push(s);
    visited[s] = true;                 // mark when enqueued, not when dequeued
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (!visited[v]) { visited[v] = true; q.push(v); }
    }
    return order;
}

int main() {
    auto adj = build(6, {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}});
    for (int s : {0, 2}) {
        cout << "from " << s << ":";
        for (int u : bfs(adj, s)) cout << " " << u;
        cout << "\n";
    }
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static List<Integer> bfs(List<List<Integer>> adj, int s) {
        boolean[] visited = new boolean[adj.size()];
        List<Integer> order = new ArrayList<>();
        Deque<Integer> q = new ArrayDeque<>();
        q.add(s);
        visited[s] = true;                 // mark when enqueued, not when dequeued
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : adj.get(u))
                if (!visited[v]) { visited[v] = true; q.add(v); }
        }
        return order;
    }

    static String join(List<Integer> xs) {
        StringBuilder sb = new StringBuilder();
        for (int x : xs) sb.append(sb.length() == 0 ? "" : " ").append(x);
        return sb.toString();
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(6, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}});
        System.out.println("from 0: " + join(bfs(adj, 0)));
        System.out.println("from 2: " + join(bfs(adj, 2)));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function bfs(adj, s) {
    const visited = new Array(adj.length).fill(false);
    const order = [];
    const q = [s];
    let head = 0;                      // index into q: shift() would be O(n)
    visited[s] = true;                 // mark when enqueued, not when dequeued
    while (head < q.length) {
        const u = q[head++];
        order.push(u);
        for (const v of adj[u])
            if (!visited[v]) { visited[v] = true; q.push(v); }
    }
    return order;
}

const adj = build(6, [[0, 1], [0, 2], [1, 3], [2, 3], [2, 4], [3, 5], [4, 5]]);
console.log("from 0:", bfs(adj, 0).join(" "));
console.log("from 2:", bfs(adj, 2).join(" "));

Output

from 0: 0 1 2 3 4 5
from 2: 2 0 3 4 1 5

Time O(V + E) · Space O(V)

BFS on a disconnected graph and counting components

A single BFS only reaches the source's component. To cover a graph that may be disconnected, loop over every vertex and start a new BFS from each one that is still unvisited. Every restart is one more connected component.

A graph with 3 connected components: edges 0-2, 2-1, 3-4, 5-7, 5-6, 6-7

0 ───── 2        3 ───── 4        5 ───── 7
        │                         │     ╱
        │                         │   ╱
        1                         6 ╱

Python

from collections import deque

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def bfs(adj, s, visited):             # visits the component of s, returns it in BFS order
    comp = []
    q = deque([s])
    visited[s] = True
    while q:
        u = q.popleft()
        comp.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
    return comp

def bfs_all(adj):
    visited = [False] * len(adj)      # shared by every BFS call
    count = 0
    for u in range(len(adj)):
        if not visited[u]:            # a fresh start = a new component
            count += 1
            print(f"component {count}:", *bfs(adj, u, visited))
    return count

adj = build(8, [(0, 2), (2, 1), (3, 4), (5, 7), (5, 6), (6, 7)])
print("components:", bfs_all(adj))

C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

vector<int> bfs(const vector<vector<int>>& adj, int s, vector<bool>& visited) {
    vector<int> comp;                  // the component of s, in BFS order
    queue<int> q;
    q.push(s);
    visited[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        comp.push_back(u);
        for (int v : adj[u])
            if (!visited[v]) { visited[v] = true; q.push(v); }
    }
    return comp;
}

int bfsAll(const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);   // shared by every BFS call
    int count = 0;
    for (int u = 0; u < (int)adj.size(); u++) {
        if (visited[u]) continue;
        count++;                                 // a fresh start = a new component
        cout << "component " << count << ":";
        for (int x : bfs(adj, u, visited)) cout << " " << x;
        cout << "\n";
    }
    return count;
}

int main() {
    auto adj = build(8, {{0, 2}, {2, 1}, {3, 4}, {5, 7}, {5, 6}, {6, 7}});
    int total = bfsAll(adj);
    cout << "components: " << total << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static List<Integer> bfs(List<List<Integer>> adj, int s, boolean[] visited) {
        List<Integer> comp = new ArrayList<>();   // the component of s, in BFS order
        Deque<Integer> q = new ArrayDeque<>();
        q.add(s);
        visited[s] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            comp.add(u);
            for (int v : adj.get(u))
                if (!visited[v]) { visited[v] = true; q.add(v); }
        }
        return comp;
    }

    static int bfsAll(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];   // shared by every BFS call
        int count = 0;
        for (int u = 0; u < adj.size(); u++) {
            if (visited[u]) continue;
            count++;                                     // a fresh start = a new component
            StringBuilder sb = new StringBuilder("component " + count + ":");
            for (int x : bfs(adj, u, visited)) sb.append(' ').append(x);
            System.out.println(sb);
        }
        return count;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(8, new int[][]{{0, 2}, {2, 1}, {3, 4}, {5, 7}, {5, 6}, {6, 7}});
        System.out.println("components: " + bfsAll(adj));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function bfs(adj, s, visited) {        // visits the component of s, returns it in BFS order
    const comp = [];
    const q = [s];
    let head = 0;
    visited[s] = true;
    while (head < q.length) {
        const u = q[head++];
        comp.push(u);
        for (const v of adj[u])
            if (!visited[v]) { visited[v] = true; q.push(v); }
    }
    return comp;
}

function bfsAll(adj) {
    const visited = new Array(adj.length).fill(false);   // shared by every BFS call
    let count = 0;
    for (let u = 0; u < adj.length; u++) {
        if (visited[u]) continue;
        count++;                                           // a fresh start = a new component
        console.log(`component ${count}:`, bfs(adj, u, visited).join(" "));
    }
    return count;
}

const adj = build(8, [[0, 2], [2, 1], [3, 4], [5, 7], [5, 6], [6, 7]]);
console.log("components:", bfsAll(adj));

Output

component 1: 0 2 1
component 2: 3 4
component 3: 5 7 6
components: 3

Time O(V + E) · Space O(V)

Shortest path in an unweighted graph (BFS distances)

Because BFS visits vertices in order of their distance from the source, the first time it reaches a vertex is along a shortest path. Record dist[v] = dist[u] + 1 and parent[v] = u when v is enqueued from u; following parent backwards from any vertex rebuilds the path.

Edges 0-1, 0-2, 1-3, 2-3, 3-4, 4-5, 4-6; distances from 0

0 ───── 1                          dist:  0  1  1  2  3  4  4
│       │                          vertex 0  1  2  3  4  5  6
2 ───── 3 ───── 4 ───── 5
                │
                6

Python

from collections import deque

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def bfs_distances(adj, s):
    n = len(adj)
    dist = [-1] * n                   # -1 = not reached yet (doubles as visited)
    parent = [-1] * n
    dist[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1 # one more edge than u
                parent[v] = u
                q.append(v)
    return dist, parent

def path_to(parent, t):
    path = []
    while t != -1:                    # walk back to the source
        path.append(t)
        t = parent[t]
    return path[::-1]

adj = build(7, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6)])
dist, parent = bfs_distances(adj, 0)
for v in range(len(adj)):
    print(f"{v}: {dist[v]}")
print("path 0 -> 5:", *path_to(parent, 5))

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

void bfsDistances(const vector<vector<int>>& adj, int s, vector<int>& dist, vector<int>& parent) {
    int n = adj.size();
    dist.assign(n, -1);                // -1 = not reached yet (doubles as visited)
    parent.assign(n, -1);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1; // one more edge than u
                parent[v] = u;
                q.push(v);
            }
    }
}

vector<int> pathTo(const vector<int>& parent, int t) {
    vector<int> path;
    for (; t != -1; t = parent[t]) path.push_back(t);   // walk back to the source
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    auto adj = build(7, {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {4, 6}});
    vector<int> dist, parent;
    bfsDistances(adj, 0, dist, parent);
    for (int v = 0; v < (int)adj.size(); v++) cout << v << ": " << dist[v] << "\n";
    cout << "path 0 -> 5:";
    for (int v : pathTo(parent, 5)) cout << " " << v;
    cout << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static int[] parent;

    static int[] bfsDistances(List<List<Integer>> adj, int s) {
        int n = adj.size();
        int[] dist = new int[n];
        parent = new int[n];
        Arrays.fill(dist, -1);             // -1 = not reached yet (doubles as visited)
        Arrays.fill(parent, -1);
        dist[s] = 0;
        Deque<Integer> q = new ArrayDeque<>();
        q.add(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u))
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1; // one more edge than u
                    parent[v] = u;
                    q.add(v);
                }
        }
        return dist;
    }

    static List<Integer> pathTo(int t) {
        List<Integer> path = new ArrayList<>();
        for (; t != -1; t = parent[t]) path.add(t);   // walk back to the source
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(7, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {4, 6}});
        int[] dist = bfsDistances(adj, 0);
        for (int v = 0; v < adj.size(); v++) System.out.println(v + ": " + dist[v]);
        StringBuilder sb = new StringBuilder("path 0 -> 5:");
        for (int v : pathTo(5)) sb.append(' ').append(v);
        System.out.println(sb);
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function bfsDistances(adj, s) {
    const n = adj.length;
    const dist = new Array(n).fill(-1);    // -1 = not reached yet (doubles as visited)
    const parent = new Array(n).fill(-1);
    dist[s] = 0;
    const q = [s];
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        for (const v of adj[u])
            if (dist[v] === -1) {
                dist[v] = dist[u] + 1;     // one more edge than u
                parent[v] = u;
                q.push(v);
            }
    }
    return { dist, parent };
}

function pathTo(parent, t) {
    const path = [];
    for (; t !== -1; t = parent[t]) path.push(t);   // walk back to the source
    return path.reverse();
}

const adj = build(7, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5], [4, 6]]);
const { dist, parent } = bfsDistances(adj, 0);
dist.forEach((d, v) => console.log(`${v}: ${d}`));
console.log("path 0 -> 5:", pathTo(parent, 5).join(" "));

Output

0: 0
1: 1
2: 1
3: 2
4: 3
5: 4
6: 4
path 0 -> 5: 0 1 3 4 5

Time O(V + E) · Space O(V)

Applications of BFS

Depth First Search (DFS)

DFS goes as deep as possible before backtracking: from the current vertex it recurses into the first unvisited neighbour, and only when that whole branch is exhausted does it try the next neighbour. The recursion stack (or an explicit stack) replaces BFS's queue.

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def dfs_rec(adj, u, visited, order):
    visited[u] = True
    order.append(u)                   # pre-order: record u on entry
    for v in adj[u]:
        if not visited[v]:
            dfs_rec(adj, v, visited, order)

def dfs(adj, s):
    visited = [False] * len(adj)
    order = []
    dfs_rec(adj, s, visited, order)
    return order

adj = build(6, [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)])
print("from 0:", *dfs(adj, 0))
print("from 2:", *dfs(adj, 2))

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

void dfsRec(const vector<vector<int>>& adj, int u, vector<bool>& visited, vector<int>& order) {
    visited[u] = true;
    order.push_back(u);                // pre-order: record u on entry
    for (int v : adj[u])
        if (!visited[v]) dfsRec(adj, v, visited, order);
}

vector<int> dfs(const vector<vector<int>>& adj, int s) {
    vector<bool> visited(adj.size(), false);
    vector<int> order;
    dfsRec(adj, s, visited, order);
    return order;
}

int main() {
    auto adj = build(6, {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}});
    for (int s : {0, 2}) {
        cout << "from " << s << ":";
        for (int u : dfs(adj, s)) cout << " " << u;
        cout << "\n";
    }
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static void dfsRec(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> order) {
        visited[u] = true;
        order.add(u);                      // pre-order: record u on entry
        for (int v : adj.get(u))
            if (!visited[v]) dfsRec(adj, v, visited, order);
    }

    static List<Integer> dfs(List<List<Integer>> adj, int s) {
        boolean[] visited = new boolean[adj.size()];
        List<Integer> order = new ArrayList<>();
        dfsRec(adj, s, visited, order);
        return order;
    }

    static String join(List<Integer> xs) {
        StringBuilder sb = new StringBuilder();
        for (int x : xs) sb.append(sb.length() == 0 ? "" : " ").append(x);
        return sb.toString();
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(6, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}});
        System.out.println("from 0: " + join(dfs(adj, 0)));
        System.out.println("from 2: " + join(dfs(adj, 2)));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function dfsRec(adj, u, visited, order) {
    visited[u] = true;
    order.push(u);                         // pre-order: record u on entry
    for (const v of adj[u])
        if (!visited[v]) dfsRec(adj, v, visited, order);
}

function dfs(adj, s) {
    const visited = new Array(adj.length).fill(false);
    const order = [];
    dfsRec(adj, s, visited, order);
    return order;
}

const adj = build(6, [[0, 1], [0, 2], [1, 3], [2, 3], [2, 4], [3, 5], [4, 5]]);
console.log("from 0:", dfs(adj, 0).join(" "));
console.log("from 2:", dfs(adj, 2).join(" "));

Output

from 0: 0 1 3 2 4 5
from 2: 2 0 1 3 5 4

Time O(V + E) · Space O(V) for visited + recursion stack

DFS on a disconnected graph and counting components

Exactly as with BFS: an outer loop over all vertices, a shared visited array, and one recursive DFS per unvisited vertex. The number of calls made by the outer loop is the number of connected components.

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def dfs_rec(adj, u, visited, comp):
    visited[u] = True
    comp.append(u)
    for v in adj[u]:
        if not visited[v]:
            dfs_rec(adj, v, visited, comp)

def count_components(adj):
    visited = [False] * len(adj)      # shared by every DFS call
    count = 0
    for u in range(len(adj)):
        if not visited[u]:            # unvisited vertex = start of a new component
            count += 1
            comp = []
            dfs_rec(adj, u, visited, comp)
            print(f"component {count}:", *comp)
    return count

adj = build(8, [(0, 2), (2, 1), (3, 4), (5, 7), (5, 6), (6, 7)])
print("components:", count_components(adj))

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

void dfsRec(const vector<vector<int>>& adj, int u, vector<bool>& visited, vector<int>& comp) {
    visited[u] = true;
    comp.push_back(u);
    for (int v : adj[u])
        if (!visited[v]) dfsRec(adj, v, visited, comp);
}

int countComponents(const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);   // shared by every DFS call
    int count = 0;
    for (int u = 0; u < (int)adj.size(); u++) {
        if (visited[u]) continue;                // unvisited vertex = start of a new component
        count++;
        vector<int> comp;
        dfsRec(adj, u, visited, comp);
        cout << "component " << count << ":";
        for (int x : comp) cout << " " << x;
        cout << "\n";
    }
    return count;
}

int main() {
    auto adj = build(8, {{0, 2}, {2, 1}, {3, 4}, {5, 7}, {5, 6}, {6, 7}});
    int total = countComponents(adj);
    cout << "components: " << total << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static void dfsRec(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> comp) {
        visited[u] = true;
        comp.add(u);
        for (int v : adj.get(u))
            if (!visited[v]) dfsRec(adj, v, visited, comp);
    }

    static int countComponents(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];   // shared by every DFS call
        int count = 0;
        for (int u = 0; u < adj.size(); u++) {
            if (visited[u]) continue;                    // unvisited vertex = start of a new component
            count++;
            List<Integer> comp = new ArrayList<>();
            dfsRec(adj, u, visited, comp);
            StringBuilder sb = new StringBuilder("component " + count + ":");
            for (int x : comp) sb.append(' ').append(x);
            System.out.println(sb);
        }
        return count;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(8, new int[][]{{0, 2}, {2, 1}, {3, 4}, {5, 7}, {5, 6}, {6, 7}});
        System.out.println("components: " + countComponents(adj));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function dfsRec(adj, u, visited, comp) {
    visited[u] = true;
    comp.push(u);
    for (const v of adj[u])
        if (!visited[v]) dfsRec(adj, v, visited, comp);
}

function countComponents(adj) {
    const visited = new Array(adj.length).fill(false);   // shared by every DFS call
    let count = 0;
    for (let u = 0; u < adj.length; u++) {
        if (visited[u]) continue;                          // unvisited vertex = start of a new component
        count++;
        const comp = [];
        dfsRec(adj, u, visited, comp);
        console.log(`component ${count}:`, comp.join(" "));
    }
    return count;
}

const adj = build(8, [[0, 2], [2, 1], [3, 4], [5, 7], [5, 6], [6, 7]]);
console.log("components:", countComponents(adj));

Output

component 1: 0 2 1
component 2: 3 4
component 3: 5 7 6
components: 3

Time O(V + E) · Space O(V)

Applications of DFS

Cycle detection — a back edge to a vertex that is still on the recursion stack (directed) or to a visited non-parent (undirected).
Topological sorting — vertices in decreasing order of DFS finish time.
Strongly connected components — Kosaraju's and Tarjan's algorithms are two DFS passes, or one DFS with low-link values.
Mazes and puzzles — explore one path to the end before trying another; backtracking is DFS over the state space.
Path finding — any path (not necessarily shortest) between two vertices; articulation points and bridges via discovery times.

	BFS	DFS
Data structure	Queue	Stack / recursion
Visits	By distance (level order)	Along one branch, then backtracks
Finds shortest paths (unweighted)	Yes	No
Memory	`O(width)` — the frontier	`O(depth)` — the current path
Typical uses	Shortest path, nearest neighbour, level-wise processing	Cycles, topological order, SCCs, connectivity, backtracking

Detect a cycle in an undirected graph

Edges 0-1, 1-2, 1-3, 2-3 versus 0-1, 1-2, 1-3

Graph 1 (cycle)              Graph 2 (no cycle — a tree)

0 ───── 1 ───── 2            0 ───── 1 ───── 2
        │     ╱                      │
        │   ╱                        │
        3 ╱                          3

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def has_cycle_from(adj, u, parent, visited):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            if has_cycle_from(adj, v, u, visited):
                return True
        elif v != parent:             # visited, and not the edge we arrived by -> cycle
            return True
    return False

def has_cycle(adj):
    visited = [False] * len(adj)
    for u in range(len(adj)):         # every component
        if not visited[u] and has_cycle_from(adj, u, -1, visited):
            return True
    return False

g1 = build(4, [(0, 1), (1, 2), (1, 3), (2, 3)])
g2 = build(4, [(0, 1), (1, 2), (1, 3)])
print("graph 1:", "cycle" if has_cycle(g1) else "no cycle")
print("graph 2:", "cycle" if has_cycle(g2) else "no cycle")

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

bool hasCycleFrom(const vector<vector<int>>& adj, int u, int parent, vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycleFrom(adj, v, u, visited)) return true;
        } else if (v != parent) {      // visited, and not the edge we arrived by -> cycle
            return true;
        }
    }
    return false;
}

bool hasCycle(const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    for (int u = 0; u < (int)adj.size(); u++)   // every component
        if (!visited[u] && hasCycleFrom(adj, u, -1, visited)) return true;
    return false;
}

int main() {
    auto g1 = build(4, {{0, 1}, {1, 2}, {1, 3}, {2, 3}});
    auto g2 = build(4, {{0, 1}, {1, 2}, {1, 3}});
    cout << "graph 1: " << (hasCycle(g1) ? "cycle" : "no cycle") << "\n";
    cout << "graph 2: " << (hasCycle(g2) ? "cycle" : "no cycle") << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static boolean hasCycleFrom(List<List<Integer>> adj, int u, int parent, boolean[] visited) {
        visited[u] = true;
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                if (hasCycleFrom(adj, v, u, visited)) return true;
            } else if (v != parent) {      // visited, and not the edge we arrived by -> cycle
                return true;
            }
        }
        return false;
    }

    static boolean hasCycle(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];
        for (int u = 0; u < adj.size(); u++)   // every component
            if (!visited[u] && hasCycleFrom(adj, u, -1, visited)) return true;
        return false;
    }

    public static void main(String[] args) {
        List<List<Integer>> g1 = build(4, new int[][]{{0, 1}, {1, 2}, {1, 3}, {2, 3}});
        List<List<Integer>> g2 = build(4, new int[][]{{0, 1}, {1, 2}, {1, 3}});
        System.out.println("graph 1: " + (hasCycle(g1) ? "cycle" : "no cycle"));
        System.out.println("graph 2: " + (hasCycle(g2) ? "cycle" : "no cycle"));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function hasCycleFrom(adj, u, parent, visited) {
    visited[u] = true;
    for (const v of adj[u]) {
        if (!visited[v]) {
            if (hasCycleFrom(adj, v, u, visited)) return true;
        } else if (v !== parent) {         // visited, and not the edge we arrived by -> cycle
            return true;
        }
    }
    return false;
}

function hasCycle(adj) {
    const visited = new Array(adj.length).fill(false);
    for (let u = 0; u < adj.length; u++)   // every component
        if (!visited[u] && hasCycleFrom(adj, u, -1, visited)) return true;
    return false;
}

const g1 = build(4, [[0, 1], [1, 2], [1, 3], [2, 3]]);
const g2 = build(4, [[0, 1], [1, 2], [1, 3]]);
console.log("graph 1:", hasCycle(g1) ? "cycle" : "no cycle");
console.log("graph 2:", hasCycle(g2) ? "cycle" : "no cycle");

Output

graph 1: cycle
graph 2: no cycle

Time O(V + E) · Space O(V)

Detect a cycle in a directed graph

Edges 0→1, 1→2, 2→3, 3→1 versus 0→1, 0→2, 1→3, 2→3

Graph 1 (cycle 1 → 2 → 3 → 1)      Graph 2 (no cycle — a DAG)

0 ────▶ 1 ────▶ 2                  0 ────▶ 1
        ▲       │                  │       │
        │       ▼                  ▼       ▼
        └────── 3                  2 ────▶ 3

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)                  # directed: one direction only
    return adj

def has_cycle_from(adj, u, visited, on_stack):
    visited[u] = True
    on_stack[u] = True                    # u is an ancestor of everything below
    for v in adj[u]:
        if not visited[v]:
            if has_cycle_from(adj, v, visited, on_stack):
                return True
        elif on_stack[v]:                 # back edge to an ancestor -> cycle
            return True
    on_stack[u] = False                   # done with u's subtree
    return False

def has_cycle(adj):
    n = len(adj)
    visited, on_stack = [False] * n, [False] * n
    for u in range(n):
        if not visited[u] and has_cycle_from(adj, u, visited, on_stack):
            return True
    return False

g1 = build(4, [(0, 1), (1, 2), (2, 3), (3, 1)])
g2 = build(4, [(0, 1), (0, 2), (1, 3), (2, 3)])
print("graph 1:", "cycle" if has_cycle(g1) else "no cycle")
print("graph 2:", "cycle" if has_cycle(g2) else "no cycle")

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) adj[u].push_back(v);   // directed: one direction only
    return adj;
}

bool hasCycleFrom(const vector<vector<int>>& adj, int u, vector<bool>& visited, vector<bool>& onStack) {
    visited[u] = true;
    onStack[u] = true;                    // u is an ancestor of everything below
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycleFrom(adj, v, visited, onStack)) return true;
        } else if (onStack[v]) {          // back edge to an ancestor -> cycle
            return true;
        }
    }
    onStack[u] = false;                   // done with u's subtree
    return false;
}

bool hasCycle(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false), onStack(n, false);
    for (int u = 0; u < n; u++)
        if (!visited[u] && hasCycleFrom(adj, u, visited, onStack)) return true;
    return false;
}

int main() {
    auto g1 = build(4, {{0, 1}, {1, 2}, {2, 3}, {3, 1}});
    auto g2 = build(4, {{0, 1}, {0, 2}, {1, 3}, {2, 3}});
    cout << "graph 1: " << (hasCycle(g1) ? "cycle" : "no cycle") << "\n";
    cout << "graph 2: " << (hasCycle(g2) ? "cycle" : "no cycle") << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);   // directed: one direction only
        return adj;
    }

    static boolean hasCycleFrom(List<List<Integer>> adj, int u, boolean[] visited, boolean[] onStack) {
        visited[u] = true;
        onStack[u] = true;                    // u is an ancestor of everything below
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                if (hasCycleFrom(adj, v, visited, onStack)) return true;
            } else if (onStack[v]) {          // back edge to an ancestor -> cycle
                return true;
            }
        }
        onStack[u] = false;                   // done with u's subtree
        return false;
    }

    static boolean hasCycle(List<List<Integer>> adj) {
        int n = adj.size();
        boolean[] visited = new boolean[n], onStack = new boolean[n];
        for (int u = 0; u < n; u++)
            if (!visited[u] && hasCycleFrom(adj, u, visited, onStack)) return true;
        return false;
    }

    public static void main(String[] args) {
        List<List<Integer>> g1 = build(4, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 1}});
        List<List<Integer>> g2 = build(4, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}});
        System.out.println("graph 1: " + (hasCycle(g1) ? "cycle" : "no cycle"));
        System.out.println("graph 2: " + (hasCycle(g2) ? "cycle" : "no cycle"));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) adj[u].push(v);       // directed: one direction only
    return adj;
}

function hasCycleFrom(adj, u, visited, onStack) {
    visited[u] = true;
    onStack[u] = true;                        // u is an ancestor of everything below
    for (const v of adj[u]) {
        if (!visited[v]) {
            if (hasCycleFrom(adj, v, visited, onStack)) return true;
        } else if (onStack[v]) {              // back edge to an ancestor -> cycle
            return true;
        }
    }
    onStack[u] = false;                       // done with u's subtree
    return false;
}

function hasCycle(adj) {
    const n = adj.length;
    const visited = new Array(n).fill(false), onStack = new Array(n).fill(false);
    for (let u = 0; u < n; u++)
        if (!visited[u] && hasCycleFrom(adj, u, visited, onStack)) return true;
    return false;
}

const g1 = build(4, [[0, 1], [1, 2], [2, 3], [3, 1]]);
const g2 = build(4, [[0, 1], [0, 2], [1, 3], [2, 3]]);
console.log("graph 1:", hasCycle(g1) ? "cycle" : "no cycle");
console.log("graph 2:", hasCycle(g2) ? "cycle" : "no cycle");

Output

graph 1: cycle
graph 2: no cycle

Time O(V + E) · Space O(V)

Topological sort — Kahn's algorithm (BFS)

The DAG used for both topological sorts: edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1

5 ────▶ 2 ────▶ 3
│               │
▼               ▼
0 ◀──── 4 ────▶ 1

Count indegrees
indeg[v] = number of edges into v, one pass over the adjacency lists.
Seed the queue
Enqueue every vertex with indeg[v] == 0.
Process
Dequeue u, append it to the order; for every neighbour v: indeg[v] -= 1, and enqueue v when it reaches 0.
Finish
When the queue is empty the order is complete — if it holds fewer than V vertices, the graph has a cycle (next section).

Python

from collections import deque

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    return adj

def kahn(adj):
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1                 # step 1: indegrees
    q = deque(u for u in range(n) if indeg[u] == 0)   # step 2: no prerequisites
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1                 # "remove" edge u -> v
            if indeg[v] == 0:
                q.append(v)               # all prerequisites of v are done
    return order

adj = build(6, [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)])
print("topological order:", *kahn(adj))

C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) adj[u].push_back(v);
    return adj;
}

vector<int> kahn(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) indeg[v]++;              // step 1: indegrees
    queue<int> q;
    for (int u = 0; u < n; u++)
        if (indeg[u] == 0) q.push(u);                 // step 2: no prerequisites
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);           // all prerequisites of v are done
    }
    return order;
}

int main() {
    auto adj = build(6, {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}});
    cout << "topological order:";
    for (int u : kahn(adj)) cout << " " << u;
    cout << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        return adj;
    }

    static List<Integer> kahn(List<List<Integer>> adj) {
        int n = adj.size();
        int[] indeg = new int[n];
        for (int u = 0; u < n; u++)
            for (int v : adj.get(u)) indeg[v]++;          // step 1: indegrees
        Deque<Integer> q = new ArrayDeque<>();
        for (int u = 0; u < n; u++)
            if (indeg[u] == 0) q.add(u);                  // step 2: no prerequisites
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : adj.get(u))
                if (--indeg[v] == 0) q.add(v);            // all prerequisites of v are done
        }
        return order;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(6, new int[][]{{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}});
        StringBuilder sb = new StringBuilder("topological order:");
        for (int u : kahn(adj)) sb.append(' ').append(u);
        System.out.println(sb);
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) adj[u].push(v);
    return adj;
}

function kahn(adj) {
    const n = adj.length;
    const indeg = new Array(n).fill(0);
    for (const nbrs of adj)
        for (const v of nbrs) indeg[v]++;                 // step 1: indegrees
    const q = [];
    for (let u = 0; u < n; u++)
        if (indeg[u] === 0) q.push(u);                    // step 2: no prerequisites
    const order = [];
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        order.push(u);
        for (const v of adj[u])
            if (--indeg[v] === 0) q.push(v);              // all prerequisites of v are done
    }
    return order;
}

const adj = build(6, [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]);
console.log("topological order:", kahn(adj).join(" "));

Output

topological order: 4 5 2 0 3 1

Time O(V + E) · Space O(V)

Cycle detection with Kahn's algorithm

Kahn's algorithm only ever outputs vertices whose indegree reached 0. The vertices on a cycle depend on each other, so none of them ever reaches 0 and they are never output. Therefore: fewer than V vertices in the result ⇔ the graph has a cycle. This is the iterative alternative to the recursion-stack method.

Python

from collections import deque

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    return adj

def kahn_count(adj):
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    count = 0                             # vertices that made it into the order
    while q:
        u = q.popleft()
        count += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return count                          # vertices on a cycle never reach indegree 0

def report(name, adj):
    c = kahn_count(adj)
    verdict = "no cycle" if c == len(adj) else "cycle"
    print(f"{name}: {verdict} ({c} of {len(adj)} vertices ordered)")

report("graph 1", build(6, [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]))
report("graph 2", build(4, [(0, 1), (1, 2), (2, 3), (3, 1)]))

C++

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) adj[u].push_back(v);
    return adj;
}

int kahnCount(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) indeg[v]++;
    queue<int> q;
    for (int u = 0; u < n; u++)
        if (indeg[u] == 0) q.push(u);
    int count = 0;                                    // vertices that made it into the order
    while (!q.empty()) {
        int u = q.front(); q.pop();
        count++;
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return count;                                     // vertices on a cycle never reach indegree 0
}

void report(const string& name, const vector<vector<int>>& adj) {
    int c = kahnCount(adj), n = adj.size();
    cout << name << ": " << (c == n ? "no cycle" : "cycle") << " (" << c << " of " << n << " vertices ordered)\n";
}

int main() {
    report("graph 1", build(6, {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}}));
    report("graph 2", build(4, {{0, 1}, {1, 2}, {2, 3}, {3, 1}}));
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        return adj;
    }

    static int kahnCount(List<List<Integer>> adj) {
        int n = adj.size();
        int[] indeg = new int[n];
        for (int u = 0; u < n; u++)
            for (int v : adj.get(u)) indeg[v]++;
        Deque<Integer> q = new ArrayDeque<>();
        for (int u = 0; u < n; u++)
            if (indeg[u] == 0) q.add(u);
        int count = 0;                                    // vertices that made it into the order
        while (!q.isEmpty()) {
            int u = q.poll();
            count++;
            for (int v : adj.get(u))
                if (--indeg[v] == 0) q.add(v);
        }
        return count;                                     // vertices on a cycle never reach indegree 0
    }

    static void report(String name, List<List<Integer>> adj) {
        int c = kahnCount(adj), n = adj.size();
        System.out.println(name + ": " + (c == n ? "no cycle" : "cycle") + " (" + c + " of " + n + " vertices ordered)");
    }

    public static void main(String[] args) {
        report("graph 1", build(6, new int[][]{{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}}));
        report("graph 2", build(4, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 1}}));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) adj[u].push(v);
    return adj;
}

function kahnCount(adj) {
    const n = adj.length;
    const indeg = new Array(n).fill(0);
    for (const nbrs of adj)
        for (const v of nbrs) indeg[v]++;
    const q = [];
    for (let u = 0; u < n; u++)
        if (indeg[u] === 0) q.push(u);
    let count = 0, head = 0;                              // count = vertices that made it into the order
    while (head < q.length) {
        const u = q[head++];
        count++;
        for (const v of adj[u])
            if (--indeg[v] === 0) q.push(v);
    }
    return count;                                         // vertices on a cycle never reach indegree 0
}

function report(name, adj) {
    const c = kahnCount(adj), n = adj.length;
    console.log(`${name}: ${c === n ? "no cycle" : "cycle"} (${c} of ${n} vertices ordered)`);
}

report("graph 1", build(6, [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]));
report("graph 2", build(4, [[0, 1], [1, 2], [2, 3], [3, 1]]));

Output

graph 1: no cycle (6 of 6 vertices ordered)
graph 2: cycle (1 of 4 vertices ordered)

Time O(V + E) · Space O(V)

Topological sort using DFS

Visit every vertex
For u in 0 … V−1: if u is unvisited, call dfs(u) — this covers disconnected DAGs.
dfs(u)
Mark u visited, recurse into every unvisited neighbour, and then push u onto the stack (post-order).
Read the stack
Pop until empty — the pop order is a topological order.

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    return adj

def dfs(adj, u, visited, stack):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(adj, v, visited, stack)
    stack.append(u)                       # post-order: u is pushed after all its descendants

def topo_sort(adj):
    n = len(adj)
    visited = [False] * n
    stack = []
    for u in range(n):
        if not visited[u]:
            dfs(adj, u, visited, stack)
    return stack[::-1]                    # pop everything = reverse finish order

adj = build(6, [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)])
print("topological order:", *topo_sort(adj))

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) adj[u].push_back(v);
    return adj;
}

void dfs(const vector<vector<int>>& adj, int u, vector<bool>& visited, vector<int>& stack) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfs(adj, v, visited, stack);
    stack.push_back(u);                   // post-order: u is pushed after all its descendants
}

vector<int> topoSort(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    vector<int> stack;
    for (int u = 0; u < n; u++)
        if (!visited[u]) dfs(adj, u, visited, stack);
    reverse(stack.begin(), stack.end());  // pop everything = reverse finish order
    return stack;
}

int main() {
    auto adj = build(6, {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}});
    cout << "topological order:";
    for (int u : topoSort(adj)) cout << " " << u;
    cout << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        return adj;
    }

    static void dfs(List<List<Integer>> adj, int u, boolean[] visited, Deque<Integer> stack) {
        visited[u] = true;
        for (int v : adj.get(u))
            if (!visited[v]) dfs(adj, v, visited, stack);
        stack.push(u);                        // post-order: u is pushed after all its descendants
    }

    static List<Integer> topoSort(List<List<Integer>> adj) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int u = 0; u < n; u++)
            if (!visited[u]) dfs(adj, u, visited, stack);
        List<Integer> order = new ArrayList<>();
        while (!stack.isEmpty()) order.add(stack.pop());   // pop everything = reverse finish order
        return order;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(6, new int[][]{{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}});
        StringBuilder sb = new StringBuilder("topological order:");
        for (int u : topoSort(adj)) sb.append(' ').append(u);
        System.out.println(sb);
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) adj[u].push(v);
    return adj;
}

function dfs(adj, u, visited, stack) {
    visited[u] = true;
    for (const v of adj[u])
        if (!visited[v]) dfs(adj, v, visited, stack);
    stack.push(u);                            // post-order: u is pushed after all its descendants
}

function topoSort(adj) {
    const n = adj.length;
    const visited = new Array(n).fill(false);
    const stack = [];
    for (let u = 0; u < n; u++)
        if (!visited[u]) dfs(adj, u, visited, stack);
    return stack.reverse();                   // pop everything = reverse finish order
}

const adj = build(6, [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]);
console.log("topological order:", topoSort(adj).join(" "));

Output

topological order: 5 4 2 3 1 0

Time O(V + E) · Space O(V)

Shortest path in a DAG

In a DAG a vertex's distance is final as soon as every vertex that can reach it is settled — and a topological order lists exactly those vertices first. One relaxation pass in topological order therefore gives all shortest paths, even with negative weights, in linear time. No priority queue, no repeated passes.

Weighted DAG: 0→1 (2), 0→4 (1), 1→2 (3), 4→2 (2), 4→5 (4), 2→3 (6), 5→3 (1)

     2        3        6
0 ──────▶ 1 ──────▶ 2 ──────▶ 3
│                   ▲         ▲
│ 1               2 │         │ 1
▼                   │         │
4 ──────────────────┘         │
│                             │
└────────────▶ 5 ─────────────┘
       4

Initialise
dist[v] = INF for all v, dist[s] = 0.
Topological order
DFS-based (or Kahn's) topological sort of the whole graph.
Relax in order
For each u in topological order with dist[u] != INF: for each edge u → v with weight w, if dist[u] + w < dist[v] set dist[v] = dist[u] + w.

Python

INF = 10 ** 9

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))             # weighted, directed
    return adj

def dfs(adj, u, visited, stack):
    visited[u] = True
    for v, _ in adj[u]:
        if not visited[v]:
            dfs(adj, v, visited, stack)
    stack.append(u)

def dag_shortest(adj, s):
    n = len(adj)
    visited, stack = [False] * n, []
    for u in range(n):
        if not visited[u]:
            dfs(adj, u, visited, stack)
    dist = [INF] * n
    dist[s] = 0
    for u in reversed(stack):             # topological order
        if dist[u] == INF:
            continue                      # unreachable: nothing to relax from here
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w     # relax u -> v
    return dist

adj = build(6, [(0, 1, 2), (0, 4, 1), (1, 2, 3), (4, 2, 2), (4, 5, 4), (2, 3, 6), (5, 3, 1)])
for s in (0, 1):
    print(f"from {s}:", *("INF" if d == INF else d for d in dag_shortest(adj, s)))

C++

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;
struct Edge { int u, v, w; };

vector<vector<pair<int,int>>> build(int n, const vector<Edge>& edges) {
    vector<vector<pair<int,int>>> adj(n);
    for (auto& e : edges) adj[e.u].push_back({e.v, e.w});   // weighted, directed
    return adj;
}

void dfs(const vector<vector<pair<int,int>>>& adj, int u, vector<bool>& visited, vector<int>& stack) {
    visited[u] = true;
    for (auto [v, w] : adj[u])
        if (!visited[v]) dfs(adj, v, visited, stack);
    stack.push_back(u);
}

vector<int> dagShortest(const vector<vector<pair<int,int>>>& adj, int s) {
    int n = adj.size();
    vector<bool> visited(n, false);
    vector<int> stack;
    for (int u = 0; u < n; u++)
        if (!visited[u]) dfs(adj, u, visited, stack);
    vector<int> dist(n, INF);
    dist[s] = 0;
    for (int i = n - 1; i >= 0; i--) {          // topological order = reverse finish order
        int u = stack[i];
        if (dist[u] == INF) continue;           // unreachable: nothing to relax from here
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;   // relax u -> v
    }
    return dist;
}

int main() {
    auto adj = build(6, {{0, 1, 2}, {0, 4, 1}, {1, 2, 3}, {4, 2, 2}, {4, 5, 4}, {2, 3, 6}, {5, 3, 1}});
    for (int s : {0, 1}) {
        cout << "from " << s << ":";
        for (int d : dagShortest(adj, s)) {
            if (d == INF) cout << " INF"; else cout << " " << d;
        }
        cout << "\n";
    }
}

Java

import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;

    static List<List<int[]>> build(int n, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});   // weighted, directed
        return adj;
    }

    static void dfs(List<List<int[]>> adj, int u, boolean[] visited, Deque<Integer> stack) {
        visited[u] = true;
        for (int[] e : adj.get(u))
            if (!visited[e[0]]) dfs(adj, e[0], visited, stack);
        stack.push(u);
    }

    static int[] dagShortest(List<List<int[]>> adj, int s) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int u = 0; u < n; u++)
            if (!visited[u]) dfs(adj, u, visited, stack);
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[s] = 0;
        while (!stack.isEmpty()) {                  // popping gives topological order
            int u = stack.pop();
            if (dist[u] == INF) continue;           // unreachable: nothing to relax from here
            for (int[] e : adj.get(u))
                if (dist[u] + e[1] < dist[e[0]]) dist[e[0]] = dist[u] + e[1];   // relax u -> v
        }
        return dist;
    }

    public static void main(String[] args) {
        List<List<int[]>> adj = build(6, new int[][]{{0, 1, 2}, {0, 4, 1}, {1, 2, 3}, {4, 2, 2}, {4, 5, 4}, {2, 3, 6}, {5, 3, 1}});
        for (int s : new int[]{0, 1}) {
            StringBuilder sb = new StringBuilder("from " + s + ":");
            for (int d : dagShortest(adj, s)) sb.append(' ').append(d == INF ? "INF" : String.valueOf(d));
            System.out.println(sb);
        }
    }
}

JavaScript

const INF = 1e9;

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) adj[u].push([v, w]);   // weighted, directed
    return adj;
}

function dfs(adj, u, visited, stack) {
    visited[u] = true;
    for (const [v] of adj[u])
        if (!visited[v]) dfs(adj, v, visited, stack);
    stack.push(u);
}

function dagShortest(adj, s) {
    const n = adj.length;
    const visited = new Array(n).fill(false), stack = [];
    for (let u = 0; u < n; u++)
        if (!visited[u]) dfs(adj, u, visited, stack);
    const dist = new Array(n).fill(INF);
    dist[s] = 0;
    for (const u of stack.reverse()) {            // topological order
        if (dist[u] === INF) continue;            // unreachable: nothing to relax from here
        for (const [v, w] of adj[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;   // relax u -> v
    }
    return dist;
}

const adj = build(6, [[0, 1, 2], [0, 4, 1], [1, 2, 3], [4, 2, 2], [4, 5, 4], [2, 3, 6], [5, 3, 1]]);
for (const s of [0, 1])
    console.log(`from ${s}:`, dagShortest(adj, s).map(d => d === INF ? "INF" : d).join(" "));

Output

from 0: 0 2 3 6 1 5
from 1: INF 0 3 9 INF INF

Time O(V + E) · Space O(V)

Dijkstra's algorithm

Single-source shortest paths in a weighted graph with non-negative edge weights. It is a greedy BFS: instead of a FIFO queue it always expands the unsettled vertex with the smallest tentative distance, so each vertex is settled exactly once, in increasing order of distance.

The weighted graph used for Dijkstra, Prim and Kruskal: 0-1 (4), 0-2 (1), 1-2 (2), 1-3 (5), 2-3 (8), 2-4 (10), 3-4 (2)

           4
  0 ─────────── 1
  │           ╱ │
1 │        2 ╱  │ 5
  │        ╱    │
  2 ─────────── 3
   ╲     8     ╱
 10 ╲         ╱ 2
     ╲       ╱
         4

Initialise
dist[s] = 0, every other dist[v] = INF; push (0, s) into a min-heap keyed by distance.
Extract-min
Pop (d, u). If d > dist[u] it is a stale entry — skip it (lazy deletion).
Relax
For every edge u → v with weight w: if dist[u] + w < dist[v], set dist[v] = dist[u] + w, parent[v] = u, and push (dist[v], v).
Stop
When the heap is empty every reachable vertex is settled; INF marks the unreachable ones.

Python

import heapq

INF = 10 ** 9

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))             # undirected, weighted
    return adj

def dijkstra(adj, s):
    n = len(adj)
    dist, parent = [INF] * n, [-1] * n
    dist[s] = 0
    pq = [(0, s)]                         # (distance, vertex) min-heap
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                      # stale entry: u was already settled with a smaller d
        for v, w in adj[u]:
            if d + w < dist[v]:           # relax u -> v
                dist[v] = d + w
                parent[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, parent

def path_to(parent, t):
    path = []
    while t != -1:
        path.append(t)
        t = parent[t]
    return path[::-1]

adj = build(5, [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)])
dist, parent = dijkstra(adj, 0)
print("dist:", *dist)
print("path 0 -> 4:", *path_to(parent, 4))

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int INF = 1e9;
struct Edge { int u, v, w; };

vector<vector<pair<int,int>>> build(int n, const vector<Edge>& edges) {
    vector<vector<pair<int,int>>> adj(n);
    for (auto& e : edges) {
        adj[e.u].push_back({e.v, e.w});
        adj[e.v].push_back({e.u, e.w});   // undirected, weighted
    }
    return adj;
}

vector<int> dijkstra(const vector<vector<pair<int,int>>>& adj, int s, vector<int>& parent) {
    int n = adj.size();
    vector<int> dist(n, INF);
    parent.assign(n, -1);
    dist[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;   // min-heap of (distance, vertex)
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;        // stale entry: u was already settled with a smaller d
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {        // relax u -> v
                dist[v] = d + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    auto adj = build(5, {{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2}});
    vector<int> parent;
    vector<int> dist = dijkstra(adj, 0, parent);
    cout << "dist:";
    for (int d : dist) cout << " " << d;
    cout << "\npath 0 -> 4:";
    vector<int> path;
    for (int t = 4; t != -1; t = parent[t]) path.push_back(t);
    reverse(path.begin(), path.end());
    for (int v : path) cout << " " << v;
    cout << "\n";
}

Java

import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;

    static List<List<int[]>> build(int n, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});   // undirected, weighted
        }
        return adj;
    }

    static int[] parent;

    static int[] dijkstra(List<List<int[]>> adj, int s) {
        int n = adj.size();
        int[] dist = new int[n];
        parent = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(parent, -1);
        dist[s] = 0;
        // min-heap of {distance, vertex}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        pq.add(new int[]{0, s});
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;        // stale entry: u was already settled with a smaller d
            for (int[] e : adj.get(u)) {
                int v = e[0], w = e[1];
                if (d + w < dist[v]) {        // relax u -> v
                    dist[v] = d + w;
                    parent[v] = u;
                    pq.add(new int[]{dist[v], v});
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        List<List<int[]>> adj = build(5, new int[][]{{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2}});
        int[] dist = dijkstra(adj, 0);
        StringBuilder sb = new StringBuilder("dist:");
        for (int d : dist) sb.append(' ').append(d);
        System.out.println(sb);
        List<Integer> path = new ArrayList<>();
        for (int t = 4; t != -1; t = parent[t]) path.add(t);
        Collections.reverse(path);
        sb = new StringBuilder("path 0 -> 4:");
        for (int v : path) sb.append(' ').append(v);
        System.out.println(sb);
    }
}

JavaScript

const INF = 1e9;

// Minimal binary min-heap of [key, value] pairs (JavaScript has no built-in priority queue).
class MinHeap {
    constructor() { this.a = []; }
    get size() { return this.a.length; }
    less(i, j) { const x = this.a[i], y = this.a[j]; return x[0] !== y[0] ? x[0] < y[0] : x[1] < y[1]; }
    swap(i, j) { [this.a[i], this.a[j]] = [this.a[j], this.a[i]]; }
    push(item) {
        this.a.push(item);
        for (let i = this.a.length - 1; i > 0; i = (i - 1) >> 1)
            if (this.less(i, (i - 1) >> 1)) this.swap(i, (i - 1) >> 1); else break;
    }
    pop() {
        const top = this.a[0], last = this.a.pop();
        if (this.a.length) {
            this.a[0] = last;
            for (let i = 0; ;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < this.a.length && this.less(l, m)) m = l;
                if (r < this.a.length && this.less(r, m)) m = r;
                if (m === i) break;
                this.swap(i, m); i = m;
            }
        }
        return top;
    }
}

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) { adj[u].push([v, w]); adj[v].push([u, w]); }   // undirected, weighted
    return adj;
}

function dijkstra(adj, s) {
    const n = adj.length;
    const dist = new Array(n).fill(INF), parent = new Array(n).fill(-1);
    dist[s] = 0;
    const pq = new MinHeap();                 // [distance, vertex]
    pq.push([0, s]);
    while (pq.size) {
        const [d, u] = pq.pop();
        if (d > dist[u]) continue;            // stale entry: u was already settled with a smaller d
        for (const [v, w] of adj[u]) {
            if (d + w < dist[v]) {            // relax u -> v
                dist[v] = d + w;
                parent[v] = u;
                pq.push([dist[v], v]);
            }
        }
    }
    return { dist, parent };
}

const adj = build(5, [[0, 1, 4], [0, 2, 1], [1, 2, 2], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2]]);
const { dist, parent } = dijkstra(adj, 0);
console.log("dist:", dist.join(" "));
const path = [];
for (let t = 4; t !== -1; t = parent[t]) path.push(t);
console.log("path 0 -> 4:", path.reverse().join(" "));

Output

dist: 0 3 1 8 10
path 0 -> 4: 0 2 1 3 4

Time O((V + E) log V) with a binary heap · Space O(V + E)

The textbook version without a heap scans the whole dist array to find the minimum each round. It is O(V²) — fine for dense graphs or an adjacency matrix, and worth knowing because it is what the heap version optimises:

Python — O(V²) array version

INF = 10 ** 9

def dijkstra_matrix(graph, src):          # graph[u][v] = weight, 0 = no edge
    n = len(graph)
    dist = [INF] * n
    dist[src] = 0
    settled = [False] * n
    for _ in range(n):
        u = -1                            # O(V) scan for the closest unsettled vertex
        for i in range(n):
            if not settled[i] and (u == -1 or dist[i] < dist[u]):
                u = i
        if dist[u] == INF:
            break                         # the rest is unreachable
        settled[u] = True
        for v in range(n):
            if graph[u][v] and not settled[v]:
                dist[v] = min(dist[v], dist[u] + graph[u][v])
    return dist

graph = [[0, 4, 1, 0, 0],
         [4, 0, 2, 5, 0],
         [1, 2, 0, 8, 10],
         [0, 5, 8, 0, 2],
         [0, 0, 10, 2, 0]]
print(*dijkstra_matrix(graph, 0))

Output

0 3 1 8 10

Bellman–Ford algorithm

Single-source shortest paths that allow negative edge weights and detect negative cycles. Instead of picking vertices cleverly it relaxes every edge, V − 1 times. After pass i, every shortest path that uses at most i edges is final; a shortest path has at most V − 1 edges, so V − 1 passes suffice.

Directed graph with negative edges: 0→1 (−1), 0→2 (4), 1→2 (3), 1→3 (2), 1→4 (2), 3→2 (5), 3→1 (1), 4→3 (−3)

          -1             2
  0 ──────────▶ 1 ──────────▶ 4
  │           ▲ │ ╲           │
4 │         1 │ │  ╲ 2        │ -3
  ▼           │ ▼   ▼         │
  2 ◀─────────┴─────3 ◀───────┘
          5   3

Initialise
dist[s] = 0, every other dist[v] = INF.
Relax V − 1 times
For every edge (u, v, w): if dist[u] != INF and dist[u] + w < dist[v], set dist[v] = dist[u] + w.
Check for a negative cycle
One more pass over all edges — if any edge can still be relaxed, a negative-weight cycle is reachable from s.

Python

INF = 10 ** 9

def bellman_ford(n, edges, s):            # edges: list of (u, v, w); no adjacency list needed
    dist = [INF] * n
    dist[s] = 0
    for _ in range(n - 1):                # V - 1 passes
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w     # relax u -> v
    for u, v, w in edges:                 # pass V: anything still improving = negative cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None
    return dist

edges = [(0, 1, -1), (0, 2, 4), (1, 2, 3), (1, 3, 2), (1, 4, 2), (3, 2, 5), (3, 1, 1), (4, 3, -3)]
d = bellman_ford(5, edges, 0)
print("graph 1:", *d)
d = bellman_ford(5, edges + [(3, 4, -1)], 0)         # 3 -> 4 -> 3 has weight -4
print("graph 2:", "negative-weight cycle" if d is None else " ".join(map(str, d)))

C++

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;
struct Edge { int u, v, w; };

// returns false when a negative-weight cycle is reachable from s
bool bellmanFord(int n, const vector<Edge>& edges, int s, vector<int>& dist) {
    dist.assign(n, INF);
    dist[s] = 0;
    for (int i = 0; i < n - 1; i++)       // V - 1 passes
        for (auto& e : edges)
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
                dist[e.v] = dist[e.u] + e.w;          // relax u -> v
    for (auto& e : edges)                 // pass V: anything still improving = negative cycle
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) return false;
    return true;
}

void report(const char* name, int n, const vector<Edge>& edges) {
    vector<int> dist;
    cout << name << ":";
    if (!bellmanFord(n, edges, 0, dist)) { cout << " negative-weight cycle\n"; return; }
    for (int d : dist) cout << " " << d;
    cout << "\n";
}

int main() {
    vector<Edge> edges = {{0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2}, {3, 2, 5}, {3, 1, 1}, {4, 3, -3}};
    report("graph 1", 5, edges);
    edges.push_back({3, 4, -1});          // 3 -> 4 -> 3 has weight -4
    report("graph 2", 5, edges);
}

Java

import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;

    // returns null when a negative-weight cycle is reachable from s
    static int[] bellmanFord(int n, List<int[]> edges, int s) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[s] = 0;
        for (int i = 0; i < n - 1; i++)       // V - 1 passes
            for (int[] e : edges)
                if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]])
                    dist[e[1]] = dist[e[0]] + e[2];       // relax u -> v
        for (int[] e : edges)                 // pass V: anything still improving = negative cycle
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
        return dist;
    }

    static void report(String name, int n, List<int[]> edges) {
        int[] dist = bellmanFord(n, edges, 0);
        StringBuilder sb = new StringBuilder(name + ":");
        if (dist == null) sb.append(" negative-weight cycle");
        else for (int d : dist) sb.append(' ').append(d);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        List<int[]> edges = new ArrayList<>(List.of(new int[]{0, 1, -1}, new int[]{0, 2, 4}, new int[]{1, 2, 3},
                new int[]{1, 3, 2}, new int[]{1, 4, 2}, new int[]{3, 2, 5}, new int[]{3, 1, 1}, new int[]{4, 3, -3}));
        report("graph 1", 5, edges);
        edges.add(new int[]{3, 4, -1});       // 3 -> 4 -> 3 has weight -4
        report("graph 2", 5, edges);
    }
}

JavaScript

const INF = 1e9;

function bellmanFord(n, edges, s) {           // edges: [u, v, w]; returns null on a negative cycle
    const dist = new Array(n).fill(INF);
    dist[s] = 0;
    for (let i = 0; i < n - 1; i++)           // V - 1 passes
        for (const [u, v, w] of edges)
            if (dist[u] !== INF && dist[u] + w < dist[v]) dist[v] = dist[u] + w;   // relax u -> v
    for (const [u, v, w] of edges)            // pass V: anything still improving = negative cycle
        if (dist[u] !== INF && dist[u] + w < dist[v]) return null;
    return dist;
}

function report(name, n, edges) {
    const dist = bellmanFord(n, edges, 0);
    console.log(`${name}:`, dist === null ? "negative-weight cycle" : dist.join(" "));
}

const edges = [[0, 1, -1], [0, 2, 4], [1, 2, 3], [1, 3, 2], [1, 4, 2], [3, 2, 5], [3, 1, 1], [4, 3, -3]];
report("graph 1", 5, edges);
report("graph 2", 5, [...edges, [3, 4, -1]]);   // 3 -> 4 -> 3 has weight -4

Output

graph 1: 0 -1 2 -2 1
graph 2: negative-weight cycle

Time O(V · E) · Space O(V)

	BFS	DAG pass	Dijkstra	Bellman–Ford
Weights	none / all equal	any (DAG only)	non-negative	any
Negative cycles	—	impossible in a DAG	wrong result	detected
Time	`O(V + E)`	`O(V + E)`	`O((V + E) log V)`	`O(V · E)`
Typical use	hops, grids	scheduling, DP on DAGs	maps, routing	currency arbitrage, distance-vector routing (RIP)

Strongly connected components — Kosaraju's algorithm

The digraph used for both SCC algorithms: 0→1, 1→2, 2→0, 1→3, 3→4, 4→5, 5→3, 4→6

0 ───▶ 1 ───▶ 3 ───▶ 4 ───▶ 6
▲      │      ▲      │
│      ▼      │      ▼
└───── 2      └───── 5

SCCs: {0, 1, 2}   {3, 4, 5}   {6}

DFS and record finish order
Run DFS over the whole graph, pushing each vertex onto a stack as it finishes (the same post-order used for topological sort).
Reverse the graph
Build rev with every edge u → v turned into v → u.
DFS the reversed graph in stack order
Pop vertices from the stack; for each unvisited one, DFS in rev — every vertex reached is in its SCC.

Python

def build(n, edges, reverse=False):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        if reverse:
            adj[v].append(u)
        else:
            adj[u].append(v)
    return adj

def dfs(adj, u, visited, out):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(adj, v, visited, out)
    out.append(u)                             # post-order

def kosaraju(n, edges):
    adj = build(n, edges)
    visited, finish = [False] * n, []
    for u in range(n):                        # step 1: finish order on the original graph
        if not visited[u]:
            dfs(adj, u, visited, finish)
    rev = build(n, edges, reverse=True)       # step 2: reversed graph
    visited = [False] * n
    sccs = []
    for u in reversed(finish):                # step 3: latest finisher first
        if not visited[u]:
            comp = []
            dfs(rev, u, visited, comp)        # reaches exactly one SCC
            sccs.append(sorted(comp))
    return sccs

edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (4, 6)]
sccs = kosaraju(7, edges)
for comp in sccs:
    print("SCC:", *comp)
print("count:", len(sccs))

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges, bool reverse) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) {
        if (reverse) adj[v].push_back(u); else adj[u].push_back(v);
    }
    return adj;
}

void dfs(const vector<vector<int>>& adj, int u, vector<bool>& visited, vector<int>& out) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfs(adj, v, visited, out);
    out.push_back(u);                             // post-order
}

vector<vector<int>> kosaraju(int n, const vector<pair<int,int>>& edges) {
    auto adj = build(n, edges, false);
    vector<bool> visited(n, false);
    vector<int> finish;
    for (int u = 0; u < n; u++)                   // step 1: finish order on the original graph
        if (!visited[u]) dfs(adj, u, visited, finish);
    auto rev = build(n, edges, true);             // step 2: reversed graph
    visited.assign(n, false);
    vector<vector<int>> sccs;
    for (int i = n - 1; i >= 0; i--) {            // step 3: latest finisher first
        int u = finish[i];
        if (visited[u]) continue;
        vector<int> comp;
        dfs(rev, u, visited, comp);               // reaches exactly one SCC
        sort(comp.begin(), comp.end());
        sccs.push_back(comp);
    }
    return sccs;
}

int main() {
    vector<pair<int,int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {4, 6}};
    auto sccs = kosaraju(7, edges);
    for (auto& comp : sccs) {
        cout << "SCC:";
        for (int v : comp) cout << " " << v;
        cout << "\n";
    }
    cout << "count: " << sccs.size() << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean reverse) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            if (reverse) adj.get(e[1]).add(e[0]); else adj.get(e[0]).add(e[1]);
        }
        return adj;
    }

    static void dfs(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> out) {
        visited[u] = true;
        for (int v : adj.get(u))
            if (!visited[v]) dfs(adj, v, visited, out);
        out.add(u);                                   // post-order
    }

    static List<List<Integer>> kosaraju(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, false);
        boolean[] visited = new boolean[n];
        List<Integer> finish = new ArrayList<>();
        for (int u = 0; u < n; u++)                   // step 1: finish order on the original graph
            if (!visited[u]) dfs(adj, u, visited, finish);
        List<List<Integer>> rev = build(n, edges, true);   // step 2: reversed graph
        visited = new boolean[n];
        List<List<Integer>> sccs = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {            // step 3: latest finisher first
            int u = finish.get(i);
            if (visited[u]) continue;
            List<Integer> comp = new ArrayList<>();
            dfs(rev, u, visited, comp);               // reaches exactly one SCC
            Collections.sort(comp);
            sccs.add(comp);
        }
        return sccs;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {4, 6}};
        List<List<Integer>> sccs = kosaraju(7, edges);
        for (List<Integer> comp : sccs) {
            StringBuilder sb = new StringBuilder("SCC:");
            for (int v : comp) sb.append(' ').append(v);
            System.out.println(sb);
        }
        System.out.println("count: " + sccs.size());
    }
}

JavaScript

function build(n, edges, reverse = false) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        if (reverse) adj[v].push(u); else adj[u].push(v);
    }
    return adj;
}

function dfs(adj, u, visited, out) {
    visited[u] = true;
    for (const v of adj[u])
        if (!visited[v]) dfs(adj, v, visited, out);
    out.push(u);                                      // post-order
}

function kosaraju(n, edges) {
    const adj = build(n, edges);
    let visited = new Array(n).fill(false);
    const finish = [];
    for (let u = 0; u < n; u++)                       // step 1: finish order on the original graph
        if (!visited[u]) dfs(adj, u, visited, finish);
    const rev = build(n, edges, true);                // step 2: reversed graph
    visited = new Array(n).fill(false);
    const sccs = [];
    for (let i = n - 1; i >= 0; i--) {                // step 3: latest finisher first
        const u = finish[i];
        if (visited[u]) continue;
        const comp = [];
        dfs(rev, u, visited, comp);                   // reaches exactly one SCC
        sccs.push(comp.sort((a, b) => a - b));
    }
    return sccs;
}

const edges = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3], [4, 6]];
const sccs = kosaraju(7, edges);
for (const comp of sccs) console.log("SCC:", comp.join(" "));
console.log("count:", sccs.length);

Output

SCC: 0 1 2
SCC: 3 4 5
SCC: 6
count: 3

Time O(V + E) · Space O(V + E) for the reversed graph

Strongly connected components — Tarjan's algorithm

One DFS pass instead of two. Every vertex gets a discovery time disc[u] and a low-link low[u]: the smallest discovery time reachable from u's subtree using at most one back edge to a vertex that is still on the stack. A vertex with low[u] == disc[u] is the root of an SCC — everything above it on the stack belongs to that component.

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    return adj

def tarjan(adj):
    n = len(adj)
    disc, low = [-1] * n, [0] * n
    on_stack, stack, sccs = [False] * n, [], []
    timer = [0]

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        stack.append(u)
        on_stack[u] = True
        for v in adj[u]:
            if disc[v] == -1:                 # tree edge
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:                 # back edge into the current SCC
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:                 # u is the root of an SCC
            comp = []
            while True:
                v = stack.pop()
                on_stack[v] = False
                comp.append(v)
                if v == u:
                    break
            sccs.append(sorted(comp))

    for u in range(n):
        if disc[u] == -1:
            dfs(u)
    return sccs

adj = build(7, [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (4, 6)])
sccs = tarjan(adj)
for comp in sccs:
    print("SCC:", *comp)
print("count:", len(sccs))

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Tarjan {
    const vector<vector<int>>& adj;
    vector<int> disc, low, stack;
    vector<bool> onStack;
    vector<vector<int>> sccs;
    int timer = 0;

    Tarjan(const vector<vector<int>>& g) : adj(g), disc(g.size(), -1), low(g.size(), 0), onStack(g.size(), false) {}

    void dfs(int u) {
        disc[u] = low[u] = timer++;
        stack.push_back(u);
        onStack[u] = true;
        for (int v : adj[u]) {
            if (disc[v] == -1) {                  // tree edge
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (onStack[v]) {              // back edge into the current SCC
                low[u] = min(low[u], disc[v]);
            }
        }
        if (low[u] == disc[u]) {                  // u is the root of an SCC
            vector<int> comp;
            while (true) {
                int v = stack.back(); stack.pop_back();
                onStack[v] = false;
                comp.push_back(v);
                if (v == u) break;
            }
            sort(comp.begin(), comp.end());
            sccs.push_back(comp);
        }
    }

    vector<vector<int>> run() {
        for (int u = 0; u < (int)adj.size(); u++)
            if (disc[u] == -1) dfs(u);
        return sccs;
    }
};

int main() {
    vector<vector<int>> adj(7);
    for (auto [u, v] : vector<pair<int,int>>{{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {4, 6}})
        adj[u].push_back(v);
    auto sccs = Tarjan(adj).run();
    for (auto& comp : sccs) {
        cout << "SCC:";
        for (int v : comp) cout << " " << v;
        cout << "\n";
    }
    cout << "count: " << sccs.size() << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> adj;
    static int[] disc, low;
    static boolean[] onStack;
    static Deque<Integer> stack = new ArrayDeque<>();
    static List<List<Integer>> sccs = new ArrayList<>();
    static int timer = 0;

    static void dfs(int u) {
        disc[u] = low[u] = timer++;
        stack.push(u);
        onStack[u] = true;
        for (int v : adj.get(u)) {
            if (disc[v] == -1) {                      // tree edge
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {                  // back edge into the current SCC
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (low[u] == disc[u]) {                      // u is the root of an SCC
            List<Integer> comp = new ArrayList<>();
            while (true) {
                int v = stack.pop();
                onStack[v] = false;
                comp.add(v);
                if (v == u) break;
            }
            Collections.sort(comp);
            sccs.add(comp);
        }
    }

    public static void main(String[] args) {
        int n = 7;
        int[][] edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {4, 6}};
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        disc = new int[n]; low = new int[n]; onStack = new boolean[n];
        Arrays.fill(disc, -1);
        for (int u = 0; u < n; u++)
            if (disc[u] == -1) dfs(u);
        for (List<Integer> comp : sccs) {
            StringBuilder sb = new StringBuilder("SCC:");
            for (int v : comp) sb.append(' ').append(v);
            System.out.println(sb);
        }
        System.out.println("count: " + sccs.size());
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) adj[u].push(v);
    return adj;
}

function tarjan(adj) {
    const n = adj.length;
    const disc = new Array(n).fill(-1), low = new Array(n).fill(0);
    const onStack = new Array(n).fill(false), stack = [], sccs = [];
    let timer = 0;

    function dfs(u) {
        disc[u] = low[u] = timer++;
        stack.push(u);
        onStack[u] = true;
        for (const v of adj[u]) {
            if (disc[v] === -1) {                     // tree edge
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {                  // back edge into the current SCC
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (low[u] === disc[u]) {                     // u is the root of an SCC
            const comp = [];
            for (;;) {
                const v = stack.pop();
                onStack[v] = false;
                comp.push(v);
                if (v === u) break;
            }
            sccs.push(comp.sort((a, b) => a - b));
        }
    }

    for (let u = 0; u < n; u++)
        if (disc[u] === -1) dfs(u);
    return sccs;
}

const adj = build(7, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3], [4, 6]]);
const sccs = tarjan(adj);
for (const comp of sccs) console.log("SCC:", comp.join(" "));
console.log("count:", sccs.length);

Output

SCC: 6
SCC: 3 4 5
SCC: 0 1 2
count: 3

Time O(V + E) · Space O(V)

Articulation points (cut vertices)

The graph used for articulation points and bridges: edges 0-1, 0-2, 1-2, 1-3, 3-4; vertices 1 and 3 are articulation points

0 ───── 1 ───── 3 ───── 4
│     ╱
│   ╱
2 ╱

remove 1 → {0, 2} and {3, 4}    remove 3 → {0, 1, 2} and {4}
remove 0, 2 or 4 → still connected

Naive solution. Remove every vertex in turn and count the connected components of what is left (skipping the removed vertex). If the count goes above 1, the vertex is an articulation point. One DFS per vertex: O(V · (V + E)).

Python — naive O(V · (V + E))

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def dfs(adj, u, visited):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(adj, v, visited)

def components_without(adj, removed):
    visited = [False] * len(adj)
    visited[removed] = True                   # pretend the vertex is gone
    count = 0
    for u in range(len(adj)):
        if not visited[u]:
            count += 1
            dfs(adj, u, visited)
    return count

def articulation_points_naive(adj):
    return [u for u in range(len(adj)) if components_without(adj, u) > 1]

adj = build(5, [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)])
print("articulation points (naive):", *articulation_points_naive(adj))

Output

articulation points (naive): 1 3

First idea (DFS tree, root only). Run a DFS and look at its tree. If the root has two or more DFS children, the root is an articulation point: the subtrees are separate branches that no back edge can connect (an undirected DFS tree has no cross edges, so an edge between two subtrees would have been a tree edge). The rule is only valid for the root — any other vertex can have several children that are still joined through back edges to its ancestors.

Python — the root rule

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def dfs(adj, u, visited):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(adj, v, visited)

def root_children(adj, root):
    visited = [False] * len(adj)
    visited[root] = True
    children = 0
    for v in adj[root]:
        if not visited[v]:                    # each unvisited neighbour starts a new subtree
            children += 1
            dfs(adj, v, visited)
    return children

adj = build(5, [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)])
for root in (0, 3):
    c = root_children(adj, root)
    print(f"root {root}: {c} DFS child(ren) ->", "articulation point" if c >= 2 else "not an articulation point")

Output

root 0: 1 DFS child(ren) -> not an articulation point
root 3: 2 DFS child(ren) -> articulation point

Tarjan's algorithm (low-link values). Give every vertex a discovery time disc[u] (the DFS counter when u is first visited) and a low value low[u]: the smallest discovery time reachable from u's subtree using tree edges plus at most one back edge. A non-root u is an articulation point iff some DFS child v has low[v] ≥ disc[u] — nothing in v's subtree climbs above u, so removing u strands that subtree.

Discover
On entering u: disc[u] = low[u] = timer++, children = 0.
Tree edge
For an unvisited neighbour v: children++, dfs(v), then low[u] = min(low[u], low[v]). If u is not the root and low[v] >= disc[u], mark u.
Back edge
For a visited neighbour v that is not the parent: low[u] = min(low[u], disc[v]).
Root rule
After the loop: if u is the root and children >= 2, mark u.

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def articulation_points(adj):
    n = len(adj)
    disc, low, parent = [-1] * n, [0] * n, [-1] * n
    is_ap = [False] * n
    timer = [0]

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in adj[u]:
            if disc[v] == -1:                     # tree edge
                parent[v] = u
                children += 1
                dfs(v)
                low[u] = min(low[u], low[v])
                if parent[u] != -1 and low[v] >= disc[u]:
                    is_ap[u] = True               # v's subtree cannot climb above u
            elif v != parent[u]:                  # back edge
                low[u] = min(low[u], disc[v])
        if parent[u] == -1 and children >= 2:
            is_ap[u] = True                       # root rule

    for u in range(n):
        if disc[u] == -1:
            dfs(u)
    print("disc:", *disc)
    print("low:", *low)
    return [u for u in range(n) if is_ap[u]]

adj = build(5, [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)])
print("articulation points:", *articulation_points(adj))

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

vector<int> disc, low, parent;
vector<bool> isAp;
int timer = 0;

void dfs(const vector<vector<int>>& adj, int u) {
    disc[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (disc[v] == -1) {                      // tree edge
            parent[v] = u;
            children++;
            dfs(adj, v);
            low[u] = min(low[u], low[v]);
            if (parent[u] != -1 && low[v] >= disc[u])
                isAp[u] = true;                   // v's subtree cannot climb above u
        } else if (v != parent[u]) {              // back edge
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent[u] == -1 && children >= 2) isAp[u] = true;   // root rule
}

int main() {
    auto adj = build(5, {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {3, 4}});
    int n = adj.size();
    disc.assign(n, -1); low.assign(n, 0); parent.assign(n, -1); isAp.assign(n, false);
    for (int u = 0; u < n; u++)
        if (disc[u] == -1) dfs(adj, u);
    cout << "disc:";
    for (int d : disc) cout << " " << d;
    cout << "\nlow:";
    for (int l : low) cout << " " << l;
    cout << "\narticulation points:";
    for (int u = 0; u < n; u++)
        if (isAp[u]) cout << " " << u;
    cout << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static List<List<Integer>> adj;
    static int[] disc, low, parent;
    static boolean[] isAp;
    static int timer = 0;

    static void dfs(int u) {
        disc[u] = low[u] = timer++;
        int children = 0;
        for (int v : adj.get(u)) {
            if (disc[v] == -1) {                      // tree edge
                parent[v] = u;
                children++;
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
                if (parent[u] != -1 && low[v] >= disc[u])
                    isAp[u] = true;                   // v's subtree cannot climb above u
            } else if (v != parent[u]) {              // back edge
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (parent[u] == -1 && children >= 2) isAp[u] = true;   // root rule
    }

    public static void main(String[] args) {
        adj = build(5, new int[][]{{0, 1}, {0, 2}, {1, 2}, {1, 3}, {3, 4}});
        int n = adj.size();
        disc = new int[n]; low = new int[n]; parent = new int[n]; isAp = new boolean[n];
        Arrays.fill(disc, -1);
        Arrays.fill(parent, -1);
        for (int u = 0; u < n; u++)
            if (disc[u] == -1) dfs(u);
        StringBuilder sb = new StringBuilder("disc:");
        for (int d : disc) sb.append(' ').append(d);
        System.out.println(sb);
        sb = new StringBuilder("low:");
        for (int l : low) sb.append(' ').append(l);
        System.out.println(sb);
        sb = new StringBuilder("articulation points:");
        for (int u = 0; u < n; u++)
            if (isAp[u]) sb.append(' ').append(u);
        System.out.println(sb);
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function articulationPoints(adj) {
    const n = adj.length;
    const disc = new Array(n).fill(-1), low = new Array(n).fill(0), parent = new Array(n).fill(-1);
    const isAp = new Array(n).fill(false);
    let timer = 0;

    function dfs(u) {
        disc[u] = low[u] = timer++;
        let children = 0;
        for (const v of adj[u]) {
            if (disc[v] === -1) {                     // tree edge
                parent[v] = u;
                children++;
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
                if (parent[u] !== -1 && low[v] >= disc[u])
                    isAp[u] = true;                   // v's subtree cannot climb above u
            } else if (v !== parent[u]) {             // back edge
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (parent[u] === -1 && children >= 2) isAp[u] = true;   // root rule
    }

    for (let u = 0; u < n; u++)
        if (disc[u] === -1) dfs(u);
    console.log("disc:", disc.join(" "));
    console.log("low:", low.join(" "));
    return [...Array(n).keys()].filter(u => isAp[u]);
}

const adj = build(5, [[0, 1], [0, 2], [1, 2], [1, 3], [3, 4]]);
console.log("articulation points:", articulationPoints(adj).join(" "));

Output

disc: 0 1 2 3 4
low: 0 0 0 3 4
articulation points: 1 3

Time O(V + E) · Space O(V)

Bridges (cut edges)

Edges 0-1, 0-2, 1-2, 1-3, 3-4 versus 0-1, 1-2, 2-0, 2-3, 3-4, 4-2

Graph 1                           Graph 2 (two triangles sharing 2)

0 ───── 1 ═════ 3 ═════ 4         0 ───── 1         3 ───── 4
│     ╱                            ╲     ╱           ╲     ╱
│   ╱                               ╲   ╱             ╲   ╱
2 ╱                                   2 ───────────────┘

bridges: 1-3, 3-4                 bridges: none (2 is an articulation point, though)

Python

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def bridges(adj):
    n = len(adj)
    disc, low = [-1] * n, [0] * n
    found = []
    timer = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in adj[u]:
            if disc[v] == -1:                     # tree edge
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:              # v's subtree never reaches u or above
                    found.append((min(u, v), max(u, v)))
            elif v != parent:                     # back edge
                low[u] = min(low[u], disc[v])

    for u in range(n):
        if disc[u] == -1:
            dfs(u, -1)
    return sorted(found)

g1 = build(5, [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)])
g2 = build(5, [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)])
for name, g in (("graph 1", g1), ("graph 2", g2)):
    b = bridges(g)
    print(f"{name}:", " ".join(f"{u}-{v}" for u, v in b) if b else "none")

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

struct Bridges {
    const vector<vector<int>>& adj;
    vector<int> disc, low;
    vector<pair<int,int>> found;
    int timer = 0;

    Bridges(const vector<vector<int>>& g) : adj(g), disc(g.size(), -1), low(g.size(), 0) {}

    void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        for (int v : adj[u]) {
            if (disc[v] == -1) {                      // tree edge
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u])                 // v's subtree never reaches u or above
                    found.push_back({min(u, v), max(u, v)});
            } else if (v != parent) {                 // back edge
                low[u] = min(low[u], disc[v]);
            }
        }
    }

    vector<pair<int,int>> run() {
        for (int u = 0; u < (int)adj.size(); u++)
            if (disc[u] == -1) dfs(u, -1);
        sort(found.begin(), found.end());
        return found;
    }
};

void report(const string& name, const vector<vector<int>>& g) {
    auto b = Bridges(g).run();
    cout << name << ":";
    if (b.empty()) cout << " none";
    for (auto [u, v] : b) cout << " " << u << "-" << v;
    cout << "\n";
}

int main() {
    report("graph 1", build(5, {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {3, 4}}));
    report("graph 2", build(5, {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 2}}));
}

Java

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static List<List<Integer>> adj;
    static int[] disc, low;
    static List<int[]> found;
    static int timer;

    static void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        for (int v : adj.get(u)) {
            if (disc[v] == -1) {                      // tree edge
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u])                 // v's subtree never reaches u or above
                    found.add(new int[]{Math.min(u, v), Math.max(u, v)});
            } else if (v != parent) {                 // back edge
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }

    static List<int[]> bridges(List<List<Integer>> g) {
        adj = g;
        int n = g.size();
        disc = new int[n]; low = new int[n]; found = new ArrayList<>(); timer = 0;
        Arrays.fill(disc, -1);
        for (int u = 0; u < n; u++)
            if (disc[u] == -1) dfs(u, -1);
        found.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        return found;
    }

    static void report(String name, List<List<Integer>> g) {
        List<int[]> b = bridges(g);
        StringBuilder sb = new StringBuilder(name + ":");
        if (b.isEmpty()) sb.append(" none");
        for (int[] e : b) sb.append(' ').append(e[0]).append('-').append(e[1]);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        report("graph 1", build(5, new int[][]{{0, 1}, {0, 2}, {1, 2}, {1, 3}, {3, 4}}));
        report("graph 2", build(5, new int[][]{{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 2}}));
    }
}

JavaScript

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    return adj;
}

function bridges(adj) {
    const n = adj.length;
    const disc = new Array(n).fill(-1), low = new Array(n).fill(0);
    const found = [];
    let timer = 0;

    function dfs(u, parent) {
        disc[u] = low[u] = timer++;
        for (const v of adj[u]) {
            if (disc[v] === -1) {                     // tree edge
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u])                 // v's subtree never reaches u or above
                    found.push([Math.min(u, v), Math.max(u, v)]);
            } else if (v !== parent) {                // back edge
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }

    for (let u = 0; u < n; u++)
        if (disc[u] === -1) dfs(u, -1);
    return found.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
}

function report(name, g) {
    const b = bridges(g);
    console.log(`${name}:`, b.length ? b.map(([u, v]) => `${u}-${v}`).join(" ") : "none");
}

report("graph 1", build(5, [[0, 1], [0, 2], [1, 2], [1, 3], [3, 4]]));
report("graph 2", build(5, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 2]]));

Output

graph 1: 1-3 3-4
graph 2: none

Time O(V + E) · Space O(V)

	Articulation point `u`	Bridge `u – v`
Condition (tree edge `u → v`)	`low[v] >= disc[u]`	`low[v] > disc[u]`
Root special case	Yes — `>= 2` DFS children	None
Removing it	Disconnects the graph; also removes its edges	Disconnects the graph; vertices stay
Relation	Both endpoints of a bridge are articulation points unless they have degree 1	A graph can have articulation points but no bridges (graph 2 above)

Minimum spanning tree — Kruskal's algorithm

The weighted graph from Dijkstra again: 0-1 (4), 0-2 (1), 1-2 (2), 1-3 (5), 2-3 (8), 2-4 (10), 3-4 (2) — its MST uses 0-2, 1-2, 3-4, 1-3

           4                                   MST (total 10)
  0 ─────────── 1
  │           ╱ │                              0       1
1 │        2 ╱  │ 5                          1 │     ╱ │ 5
  │        ╱    │                              │  2 ╱  │
  2 ─────────── 3                              2 ╱     3
   ╲     8     ╱                                       │ 2
 10 ╲         ╱ 2                                      4
     ╲       ╱
         4

Sort
All E edges by weight, ascending — O(E log E).
Initialise
mst = {}, total = 0, every vertex in its own set.
Scan
For each edge (u, v, w) in sorted order, while |mst| < V − 1: if u and v are in different sets, add the edge, total += w, and merge the two sets.
Return
total and the chosen edges.

Naive version (from the notes). Keep the partial MST as a separate graph and, for every candidate edge, run a DFS in it to see whether u can already reach v — if so, the edge would form a cycle. Correct, but each check costs O(V) and there are E of them: O(E · V).

Python — naive O(E · V) cycle check

def connected(mst_adj, u, v):             # DFS inside the partial MST: can u already reach v?
    visited = [False] * len(mst_adj)
    stack = [u]
    visited[u] = True
    while stack:
        x = stack.pop()
        if x == v:
            return True
        for y in mst_adj[x]:
            if not visited[y]:
                visited[y] = True
                stack.append(y)
    return False

def kruskal_naive(n, edges):
    mst_adj = [[] for _ in range(n)]      # a second graph holding only chosen edges
    total, chosen = 0, []
    for u, v, w in sorted(edges, key=lambda e: (e[2], e[0], e[1])):
        if len(chosen) == n - 1:
            break
        if not connected(mst_adj, u, v):  # O(V) check per edge
            mst_adj[u].append(v)
            mst_adj[v].append(u)
            chosen.append((u, v, w))
            total += w
    return total, chosen

edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)]
total, chosen = kruskal_naive(5, edges)
for u, v, w in chosen:
    print(f"{u}-{v} ({w})")
print("total weight:", total)

Output

0-2 (1)
1-2 (2)
3-4 (2)
1-3 (5)
total weight: 10

Efficient version. The “are u and v already connected?” question is exactly what a disjoint set (union–find) answers in near-constant time: find(u) == find(v) means same component; union(u, v) merges two. With path compression (point every node on the find path straight at the root) and union by rank (hang the shorter tree under the taller) each operation is O(α(V)), effectively constant, so the sort dominates.

Python

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])   # path compression
        return self.parent[u]

    def union(self, u, v):                # returns false if u and v were already joined
        ru, rv = self.find(u), self.find(v)
        if ru == rv:
            return False
        if self.rank[ru] < self.rank[rv]:  # union by rank: shorter tree under the taller
            ru, rv = rv, ru
        self.parent[rv] = ru
        if self.rank[ru] == self.rank[rv]:
            self.rank[ru] += 1
        return True

def kruskal(n, edges):
    edges = sorted(edges, key=lambda e: (e[2], e[0], e[1]))   # by weight (ties: by endpoints)
    ds = DisjointSet(n)
    total, chosen = 0, []
    for u, v, w in edges:
        if len(chosen) == n - 1:
            break                         # a spanning tree has exactly V - 1 edges
        if ds.union(u, v):                # different components -> no cycle
            chosen.append((u, v, w))
            total += w
    return total, chosen

edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)]
total, chosen = kruskal(5, edges)
for u, v, w in chosen:
    print(f"{u}-{v} ({w})")
print("total weight:", total)

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Edge { int u, v, w; };

struct DisjointSet {
    vector<int> parent, rank_;
    DisjointSet(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int u) {
        if (parent[u] != u) parent[u] = find(parent[u]);   // path compression
        return parent[u];
    }
    bool unite(int u, int v) {            // false if u and v were already joined
        int ru = find(u), rv = find(v);
        if (ru == rv) return false;
        if (rank_[ru] < rank_[rv]) swap(ru, rv);           // union by rank
        parent[rv] = ru;
        if (rank_[ru] == rank_[rv]) rank_[ru]++;
        return true;
    }
};

int kruskal(int n, vector<Edge> edges, vector<Edge>& chosen) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        if (a.w != b.w) return a.w < b.w;                  // by weight (ties: by endpoints)
        return a.u != b.u ? a.u < b.u : a.v < b.v;
    });
    DisjointSet ds(n);
    int total = 0;
    for (auto& e : edges) {
        if ((int)chosen.size() == n - 1) break;            // a spanning tree has V - 1 edges
        if (ds.unite(e.u, e.v)) {                          // different components -> no cycle
            chosen.push_back(e);
            total += e.w;
        }
    }
    return total;
}

int main() {
    vector<Edge> edges = {{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2}};
    vector<Edge> chosen;
    int total = kruskal(5, edges, chosen);
    for (auto& e : chosen) cout << e.u << "-" << e.v << " (" << e.w << ")\n";
    cout << "total weight: " << total << "\n";
}

Java

import java.util.*;

public class Main {
    static class DisjointSet {
        int[] parent, rank;
        DisjointSet(int n) {
            parent = new int[n]; rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int u) {
            if (parent[u] != u) parent[u] = find(parent[u]);   // path compression
            return parent[u];
        }
        boolean union(int u, int v) {         // false if u and v were already joined
            int ru = find(u), rv = find(v);
            if (ru == rv) return false;
            if (rank[ru] < rank[rv]) { int t = ru; ru = rv; rv = t; }   // union by rank
            parent[rv] = ru;
            if (rank[ru] == rank[rv]) rank[ru]++;
            return true;
        }
    }

    static List<int[]> chosen = new ArrayList<>();

    static int kruskal(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> a[2] != b[2] ? a[2] - b[2]        // by weight
                                   : a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);   // ties: by endpoints
        DisjointSet ds = new DisjointSet(n);
        int total = 0;
        for (int[] e : edges) {
            if (chosen.size() == n - 1) break;              // a spanning tree has V - 1 edges
            if (ds.union(e[0], e[1])) {                     // different components -> no cycle
                chosen.add(e);
                total += e[2];
            }
        }
        return total;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2}};
        int total = kruskal(5, edges);
        for (int[] e : chosen) System.out.println(e[0] + "-" + e[1] + " (" + e[2] + ")");
        System.out.println("total weight: " + total);
    }
}

JavaScript

class DisjointSet {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(u) {
        if (this.parent[u] !== u) this.parent[u] = this.find(this.parent[u]);   // path compression
        return this.parent[u];
    }
    union(u, v) {                             // false if u and v were already joined
        let ru = this.find(u), rv = this.find(v);
        if (ru === rv) return false;
        if (this.rank[ru] < this.rank[rv]) [ru, rv] = [rv, ru];   // union by rank
        this.parent[rv] = ru;
        if (this.rank[ru] === this.rank[rv]) this.rank[ru]++;
        return true;
    }
}

function kruskal(n, edges) {
    const sorted = [...edges].sort((a, b) => a[2] - b[2] || a[0] - b[0] || a[1] - b[1]);   // by weight, ties by endpoints
    const ds = new DisjointSet(n);
    let total = 0;
    const chosen = [];
    for (const [u, v, w] of sorted) {
        if (chosen.length === n - 1) break;   // a spanning tree has V - 1 edges
        if (ds.union(u, v)) {                 // different components -> no cycle
            chosen.push([u, v, w]);
            total += w;
        }
    }
    return { total, chosen };
}

const edges = [[0, 1, 4], [0, 2, 1], [1, 2, 2], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2]];
const { total, chosen } = kruskal(5, edges);
for (const [u, v, w] of chosen) console.log(`${u}-${v} (${w})`);
console.log("total weight:", total);

Output

0-2 (1)
1-2 (2)
3-4 (2)
1-3 (5)
total weight: 10

Time O(E log E) for the sort; the union–find work is O(E · α(V)) · Space O(V + E)

Minimum spanning tree — Prim's algorithm

Initialise
inMST[v] = false for all v; push (0, start, −1) into a min-heap keyed by weight.
Extract-min
Pop (w, v, from). If v is already in the tree, skip (a stale entry).
Add
Mark inMST[v]; if from != −1 record the edge from – v and total += w.
Push neighbours
For every edge v – x with weight w' where x is not in the tree: push (w', x, v).

Python

import heapq

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))             # undirected, weighted
    return adj

def prim(adj, start=0):
    n = len(adj)
    in_mst = [False] * n
    pq = [(0, start, -1)]                 # (weight, vertex, from) min-heap
    total, chosen = 0, []
    while pq:
        w, v, frm = heapq.heappop(pq)
        if in_mst[v]:
            continue                      # stale entry: v was added via a cheaper edge
        in_mst[v] = True
        if frm != -1:
            chosen.append((frm, v, w))    # the edge that brought v into the tree
            total += w
        for x, wx in adj[v]:
            if not in_mst[x]:
                heapq.heappush(pq, (wx, x, v))
    return total, chosen

adj = build(5, [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)])
total, chosen = prim(adj)
for u, v, w in chosen:
    print(f"{u}-{v} ({w})")
print("total weight:", total)

C++

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

struct Edge { int u, v, w; };

vector<vector<pair<int,int>>> build(int n, const vector<Edge>& edges) {
    vector<vector<pair<int,int>>> adj(n);
    for (auto& e : edges) {
        adj[e.u].push_back({e.v, e.w});
        adj[e.v].push_back({e.u, e.w});   // undirected, weighted
    }
    return adj;
}

int prim(const vector<vector<pair<int,int>>>& adj, int start, vector<Edge>& chosen) {
    int n = adj.size();
    vector<bool> inMst(n, false);
    using Item = tuple<int,int,int>;     // (weight, vertex, from) — tuples compare lexicographically
    priority_queue<Item, vector<Item>, greater<Item>> pq;
    pq.push({0, start, -1});
    int total = 0;
    while (!pq.empty()) {
        auto [w, v, from] = pq.top(); pq.pop();
        if (inMst[v]) continue;           // stale entry: v was added via a cheaper edge
        inMst[v] = true;
        if (from != -1) {
            chosen.push_back({from, v, w});   // the edge that brought v into the tree
            total += w;
        }
        for (auto [x, wx] : adj[v])
            if (!inMst[x]) pq.push({wx, x, v});
    }
    return total;
}

int main() {
    auto adj = build(5, {{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2}});
    vector<Edge> chosen;
    int total = prim(adj, 0, chosen);
    for (auto& e : chosen) cout << e.u << "-" << e.v << " (" << e.w << ")\n";
    cout << "total weight: " << total << "\n";
}

Java

import java.util.*;

public class Main {
    static List<List<int[]>> build(int n, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});   // undirected, weighted
        }
        return adj;
    }

    static List<int[]> chosen = new ArrayList<>();

    static int prim(List<List<int[]>> adj, int start) {
        int n = adj.size();
        boolean[] inMst = new boolean[n];
        // min-heap of {weight, vertex, from}, compared field by field
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
                a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
        pq.add(new int[]{0, start, -1});
        int total = 0;
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int w = top[0], v = top[1], from = top[2];
            if (inMst[v]) continue;           // stale entry: v was added via a cheaper edge
            inMst[v] = true;
            if (from != -1) {
                chosen.add(new int[]{from, v, w});   // the edge that brought v into the tree
                total += w;
            }
            for (int[] e : adj.get(v))
                if (!inMst[e[0]]) pq.add(new int[]{e[1], e[0], v});
        }
        return total;
    }

    public static void main(String[] args) {
        List<List<int[]>> adj = build(5, new int[][]{{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2}});
        int total = prim(adj, 0);
        for (int[] e : chosen) System.out.println(e[0] + "-" + e[1] + " (" + e[2] + ")");
        System.out.println("total weight: " + total);
    }
}

JavaScript

// Minimal binary min-heap of [weight, vertex, from] triples, compared field by field
// (JavaScript has no built-in priority queue; a sorted array with splice() also works for small graphs).
class MinHeap {
    constructor() { this.a = []; }
    get size() { return this.a.length; }
    less(i, j) {
        const x = this.a[i], y = this.a[j];
        return x[0] !== y[0] ? x[0] < y[0] : x[1] !== y[1] ? x[1] < y[1] : x[2] < y[2];
    }
    swap(i, j) { [this.a[i], this.a[j]] = [this.a[j], this.a[i]]; }
    push(item) {
        this.a.push(item);
        for (let i = this.a.length - 1; i > 0; i = (i - 1) >> 1)
            if (this.less(i, (i - 1) >> 1)) this.swap(i, (i - 1) >> 1); else break;
    }
    pop() {
        const top = this.a[0], last = this.a.pop();
        if (this.a.length) {
            this.a[0] = last;
            for (let i = 0; ;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < this.a.length && this.less(l, m)) m = l;
                if (r < this.a.length && this.less(r, m)) m = r;
                if (m === i) break;
                this.swap(i, m); i = m;
            }
        }
        return top;
    }
}

function build(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) { adj[u].push([v, w]); adj[v].push([u, w]); }   // undirected, weighted
    return adj;
}

function prim(adj, start = 0) {
    const n = adj.length;
    const inMst = new Array(n).fill(false);
    const pq = new MinHeap();                 // [weight, vertex, from]
    pq.push([0, start, -1]);
    let total = 0;
    const chosen = [];
    while (pq.size) {
        const [w, v, from] = pq.pop();
        if (inMst[v]) continue;               // stale entry: v was added via a cheaper edge
        inMst[v] = true;
        if (from !== -1) {
            chosen.push([from, v, w]);        // the edge that brought v into the tree
            total += w;
        }
        for (const [x, wx] of adj[v])
            if (!inMst[x]) pq.push([wx, x, v]);
    }
    return { total, chosen };
}

const adj = build(5, [[0, 1, 4], [0, 2, 1], [1, 2, 2], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2]]);
const { total, chosen } = prim(adj);
for (const [u, v, w] of chosen) console.log(`${u}-${v} (${w})`);
console.log("total weight:", total);

Output

0-2 (1)
2-1 (2)
1-3 (5)
3-4 (2)
total weight: 10

Time O((V + E) log V) with a binary heap; O(V²) with an array scan · Space O(V + E)

	Kruskal	Prim
Grows	A forest: picks edges globally, cheapest first	One tree from a start vertex, cheapest outgoing edge first
Input it wants	Edge list (sorted)	Adjacency list (or matrix)
Data structure	Disjoint set (union–find)	Min-heap keyed by edge weight
Time	`O(E log E)`	`O((V + E) log V)` heap · `O(V²)` array
Best for	Sparse graphs, edges already sorted, streaming edges, disconnected graphs (gives a forest)	Dense graphs (`E ≈ V²` — use the `O(V²)` array version), adjacency-matrix input
Result	Same total weight; with distinct edge weights the MST is unique and both return the identical tree	Same

Which algorithm when

Problem	Algorithm	Graph type	Time	Remember
Traverse / reach / count components	BFS or DFS	Any	`O(V + E)`	Shared `visited` array; outer loop over all vertices for disconnected graphs
Shortest path, unweighted	BFS	Any	`O(V + E)`	`dist[v] = dist[u] + 1`, `parent[]` for the path
Cycle detection	DFS (`parent` / `onStack`) or Kahn	Undirected / directed	`O(V + E)`	Undirected: visited non-parent; directed: vertex on the recursion stack
Topological order	Kahn (BFS) or DFS finish order	DAG	`O(V + E)`	Kahn detects cycles for free; min-heap gives the lexicographically smallest order
Shortest path, weighted DAG	One relaxation pass in topological order	DAG, any weights	`O(V + E)`	Also longest path (negate weights)
Shortest path, non-negative weights	Dijkstra	Directed or undirected, `w ≥ 0`	`O((V + E) log V)`	Min-heap of `(dist, v)`, skip stale entries
Shortest path, negative weights	Bellman–Ford	Directed, any weights	`O(V · E)`	`V − 1` passes over all edges; a `V`-th improvement = negative cycle
Strongly connected components	Kosaraju (2 DFS) or Tarjan (1 DFS)	Directed	`O(V + E)`	Kosaraju: reverse graph + finish order; Tarjan: `low[u] == disc[u]`
Articulation points / bridges	Tarjan low-link DFS	Undirected	`O(V + E)`	`low[v] >= disc[u]` (vertex, root: ≥ 2 children) · `low[v] > disc[u]` (edge)
Minimum spanning tree	Kruskal or Prim	Undirected, weighted, connected	`O(E log E)` · `O((V + E) log V)`	Kruskal: sort + union–find (sparse); Prim: heap from a start vertex (dense)

Interview Q&A

BFS or DFS — how do you decide?

Why does Dijkstra fail with negative edge weights?

Kahn's algorithm or DFS for topological sort?

Adjacency list or adjacency matrix — which do you choose and why?

Kruskal or Prim — which would you use?

What does the low-link value mean, and what are the three conditions built on it?