Graphs Cheatsheet

REFERENCE v1.0

Graphs Quick Reference

Everything you need day‑to‑day – traversals, shortest paths, and algorithms.

Graph Basics

Terminology

Vertex (V) – node
Edge (E) – connection
Directed – one‑way edge
Undirected – two‑way edge
Weighted – edge has cost
Cycle – path starts/ends at same vertex
Connected – path exists between any two vertices
DAG – Directed Acyclic Graph
Degree – number of edges (in/out for directed)

Graph Types

Undirected Graph
Directed Graph (Digraph)
Weighted Graph
Unweighted Graph
Cyclic / Acyclic
Connected / Disconnected
Complete Graph
Bipartite Graph

Graph Representations

Adjacency List

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
adj.get(u).add(v);        // directed
adj.get(v).add(u);        // undirected (add both)

// Weighted
List<List<int[]>> adj = new ArrayList<>();
adj.get(u).add(new int[]{v, w});

Adjacency Matrix

int[][] adj = new int[n][n];
adj[u][v] = 1;            // directed
adj[u][v] = adj[v][u] = 1; // undirected

// Weighted
adj[u][v] = weight;
adj[v][u] = weight;       // undirected

DFS (Depth‑First Search)

Recursive DFS

boolean[] visited = new boolean[n];

void dfs(int u, List<List<Integer>> adj) {
    visited[u] = true;
    System.out.print(u + " ");
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            dfs(v, adj);
        }
    }
}

// DFS with parent (for cycle detection)
boolean hasCycle(int u, int parent, List<List<Integer>> adj, boolean[] visited) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            if (hasCycle(v, u, adj, visited)) return true;
        } else if (v != parent) {
            return true;
        }
    }
    return false;
}

Iterative DFS (Stack)

void dfsIterative(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (!visited[u]) {
            visited[u] = true;
            System.out.print(u + " ");
            for (int v : adj.get(u)) {
                if (!visited[v]) stack.push(v);
            }
        }
    }
}

BFS (Breadth‑First Search)

void bfs(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    visited[start] = true;
    q.offer(start);
    while (!q.isEmpty()) {
        int u = q.poll();
        System.out.print(u + " ");
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                q.offer(v);
            }
        }
    }
}

// BFS with distance (shortest path in unweighted graph)
int[] bfsDistance(int start, List<List<Integer>> adj) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    Queue<Integer> q = new LinkedList<>();
    dist[start] = 0;
    q.offer(start);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.offer(v);
            }
        }
    }
    return dist;
}

Shortest Path Algorithms

Dijkstra (Single Source – Non‑negative Weights)

int[] dijkstra(int src, List<List<int[]>> adj, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0];
        int d = curr[1];
        if (d > dist[u]) continue;
        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            int w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

Bellman‑Ford (Negative Weights, Detects Negative Cycles)

int[] bellmanFord(int src, int[][] edges, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    // Check for negative cycles
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            return null;  // negative cycle detected
        }
    }
    return dist;
}

Floyd‑Warshall (All‑Pairs Shortest Path)

void floydWarshall(int[][] dist, int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

Minimum Spanning Tree (MST)

Prim's Algorithm

int prim(List<List<int[]>> adj, int n) {
    boolean[] visited = new boolean[n];
    int[] minEdge = new int[n];
    Arrays.fill(minEdge, Integer.MAX_VALUE);
    minEdge[0] = 0;
    int total = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || minEdge[j] < minEdge[u])) {
                u = j;
            }
        }
        visited[u] = true;
        total += minEdge[u];
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (!visited[v] && w < minEdge[v]) {
                minEdge[v] = w;
            }
        }
    }
    return total;
}

Kruskal's Algorithm (Union‑Find)

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) { int temp = ra; ra = rb; rb = temp; }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }
}

int kruskal(int[][] edges, int n) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);  // sort by weight
    UnionFind uf = new UnionFind(n);
    int total = 0, count = 0;
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (uf.union(u, v)) {
            total += w;
            count++;
            if (count == n - 1) break;
        }
    }
    return total;
}

Topological Sort (DAG)

DFS Method

void topologicalSortDFS(List<List<Integer>> adj, int n) {
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfsTopo(i, adj, visited, stack);
    }
    while (!stack.isEmpty()) System.out.print(stack.pop() + " ");
}

void dfsTopo(int u, List<List<Integer>> adj, boolean[] visited, Stack<Integer> stack) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) dfsTopo(v, adj, visited, stack);
    }
    stack.push(u);
}

Kahn's Algorithm (BFS / Indegree)

int[] topologicalSortKahn(List<List<Integer>> adj, int n) {
    int[] indegree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : adj.get(u)) indegree[v]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.offer(i);
    }
    int[] result = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        result[idx++] = u;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) q.offer(v);
        }
    }
    return (idx == n) ? result : null;  // null if cycle
}

Common Graph Problems

Easy

Number of Connected Components
BFS / DFS Traversal
Find Path (DFS/BFS)
Detect Cycle (Undirected)
Bipartite Graph Check

Medium

Shortest Path (BFS)
Dijkstra (Weighted)
Topological Sort
Detect Cycle (Directed)
Course Schedule
Number of Islands

Hard

Dijkstra with State
Bellman‑Ford / Floyd‑Warshall
Kruskal / Prim (MST)
Alien Dictionary
Critical Connections
Word Ladder

Complexities Summary

Algorithm	Time Complexity	Space Complexity
DFS / BFS	O(V + E)	O(V)
Dijkstra (Heap)	O((V + E) log V)	O(V)
Dijkstra (Array)	O(V²)	O(V)
Bellman‑Ford	O(VE)	O(V)
Floyd‑Warshall	O(V³)	O(V²)
Prim (Adj Matrix)	O(V²)	O(V)
Prim (Heap)	O(E log V)	O(V)
Kruskal	O(E log E)	O(V)
Topological Sort	O(V + E)	O(V)

📌 Quick Reference

Unweighted shortest path: BFS
Weighted no negative: Dijkstra (Heap)
Negative weights: Bellman‑Ford
All‑pairs: Floyd‑Warshall
MST: Prim (dense) or Kruskal (sparse)
Cycle detection (undirected): DFS with parent
Cycle detection (directed): DFS with 3 states or Kahn's
DAG ordering: Topological Sort (DFS or Kahn's)

← Back to All Cheatsheets