Graphs — The Complete Visual Reference

// Adjacency List — unweighted val graph: Map<Int, List<Int>> = mapOf( 0 to listOf(1, 2), 1 to listOf(0, 2, 3), 2 to listOf(0, 1, 3), 3 to listOf(1, 2) ) // Adjacency List — weighted val weighted: Map<Int, List<Pair<Int, Int>>> = mapOf( 0 to listOf(1 to 5, 2 to 3), 1 to listOf(0 to 5, 2 to 2, 3 to 4) )

// From an edge list fun buildGraph(n: Int, edges: List<IntArray>, undirected: Boolean = true): Array<MutableList<Int>> { val graph = Array(n) { mutableListOf<Int>() } for ((u, v) in edges) { graph[u].add(v) if (undirected) graph[v].add(u) } return graph } // Weighted graph fun buildWeightedGraph(n: Int, edges: Array<IntArray>): Array<MutableList<Pair<Int, Int>>> { val graph = Array(n) { mutableListOf<Pair<Int, Int>>() } for (e in edges) { graph[e[0]].add(e[1] to e[2]) } return graph } // Grid as implicit graph (4-directional) val dirs = listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1) fun neighbors(r: Int, c: Int, rows: Int, cols: Int): List<Pair<Int, Int>> = dirs.mapNotNull { (dr, dc) -> val nr = r + dr; val nc = c + dc if (nr in 0 until rows && nc in 0 until cols) nr to nc else null }

// Basic BFS fun bfs(graph: Map<Int, List<Int>>, start: Int): List<Int> { val visited = mutableSetOf(start) val queue = ArrayDeque<Int>() val order = mutableListOf<Int>() queue.addLast(start) while (queue.isNotEmpty()) { val node = queue.removeFirst() order.add(node) for (neighbor in graph[node].orEmpty()) { if (visited.add(neighbor)) queue.addLast(neighbor) } } return order } // BFS with shortest distances fun bfsDistance(graph: Map<Int, List<Int>>, start: Int): Map<Int, Int> { val dist = mutableMapOf(start to 0) val queue = ArrayDeque<Int>() queue.addLast(start) while (queue.isNotEmpty()) { val node = queue.removeFirst() for (neighbor in graph[node].orEmpty()) { if (neighbor !in dist) { dist[neighbor] = dist[node]!! + 1 queue.addLast(neighbor) } } } return dist }

// Recursive DFS fun dfs(graph: Map<Int, List<Int>>, start: Int): List<Int> { val visited = mutableSetOf<Int>() val order = mutableListOf<Int>() fun explore(node: Int) { if (!visited.add(node)) return order.add(node) for (neighbor in graph[node].orEmpty()) explore(neighbor) } explore(start) return order } // Iterative DFS (explicit stack) fun dfsIterative(graph: Map<Int, List<Int>>, start: Int): List<Int> { val visited = mutableSetOf<Int>() val stack = ArrayDeque<Int>() val order = mutableListOf<Int>() stack.addLast(start) while (stack.isNotEmpty()) { val node = stack.removeLast() if (!visited.add(node)) continue order.add(node) for (neighbor in graph[node].orEmpty()) { if (neighbor !in visited) stack.addLast(neighbor) } } return order }

// BFS/DFS: iterate all vertices, start new traversal from each unvisited fun connectedComponents(n: Int, graph: Map<Int, List<Int>>): Int { val visited = BooleanArray(n) var count = 0 for (v in 0 until n) { if (visited[v]) continue count++ val queue = ArrayDeque<Int>() queue.addLast(v); visited[v] = true while (queue.isNotEmpty()) { val node = queue.removeFirst() for (nb in graph[node].orEmpty()) if (!visited[nb]) { visited[nb] = true; queue.addLast(nb) } } } return count }

// Undirected: DFS — visited neighbor that's NOT parent = cycle fun hasCycleUndirected(n: Int, graph: Map<Int, List<Int>>): Boolean { val visited = BooleanArray(n) fun dfs(node: Int, parent: Int): Boolean { visited[node] = true for (nb in graph[node].orEmpty()) { if (!visited[nb]) { if (dfs(nb, node)) return true } else if (nb != parent) return true } return false } return (0 until n).any { !visited[it] && dfs(it, -1) } } // Directed: three-color DFS — edge to GRAY = back edge = cycle fun hasCycleDirected(n: Int, graph: Map<Int, List<Int>>): Boolean { val color = IntArray(n) // 0=WHITE, 1=GRAY, 2=BLACK fun dfs(node: Int): Boolean { color[node] = 1 for (nb in graph[node].orEmpty()) { if (color[nb] == 1) return true // back edge if (color[nb] == 0 && dfs(nb)) return true } color[node] = 2; return false } return (0 until n).any { color[it] == 0 && dfs(it) } }

// DFS-based: reverse postorder fun topoSortDFS(n: Int, graph: Map<Int, List<Int>>): List<Int> { val visited = BooleanArray(n) val order = ArrayDeque<Int>() fun dfs(node: Int) { visited[node] = true for (nb in graph[node].orEmpty()) if (!visited[nb]) dfs(nb) order.addFirst(node) } for (i in 0 until n) if (!visited[i]) dfs(i) return order.toList() } // Kahn's BFS-based: remove vertices with in-degree 0 fun topoSortKahns(n: Int, graph: Map<Int, List<Int>>): List<Int> { val inDegree = IntArray(n) for (nbs in graph.values) for (v in nbs) inDegree[v]++ val queue = ArrayDeque<Int>() for (i in 0 until n) if (inDegree[i] == 0) queue.addLast(i) val order = mutableListOf<Int>() while (queue.isNotEmpty()) { val node = queue.removeFirst(); order.add(node) for (nb in graph[node].orEmpty()) { inDegree[nb]-- if (inDegree[nb] == 0) queue.addLast(nb) } } if (order.size != n) throw IllegalArgumentException("Cycle!") return order }

import java.util.PriorityQueue fun dijkstra(graph: Array<MutableList<Pair<Int, Int>>>, source: Int, n: Int): IntArray { val dist = IntArray(n) { Int.MAX_VALUE } dist[source] = 0 val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second }) pq.add(source to 0) while (pq.isNotEmpty()) { val (u, d) = pq.poll() if (d > dist[u]) continue // stale entry for ((v, w) in graph[u]) { val nd = dist[u] + w if (nd < dist[v]) { dist[v] = nd; pq.add(v to nd) } } } return dist }

// Handles NEGATIVE weights. Detects negative cycles. fun bellmanFord(n: Int, edges: List<Triple<Int,Int,Int>>, src: Int): IntArray? { val dist = IntArray(n) { Int.MAX_VALUE }; dist[src] = 0 repeat(n - 1) { for ((u, v, w) in edges) if (dist[u] != Int.MAX_VALUE && dist[u] + w < dist[v]) dist[v] = dist[u] + w } // Check for negative cycles for ((u, v, w) in edges) if (dist[u] != Int.MAX_VALUE && dist[u] + w < dist[v]) return null return dist }

// dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) fun floydWarshall(n: Int, edges: List<Triple<Int,Int,Int>>): Array<IntArray> { val INF = Int.MAX_VALUE / 2 val dist = Array(n) { i -> IntArray(n) { j -> if (i == j) 0 else INF } } for ((u, v, w) in edges) dist[u][v] = minOf(dist[u][v], w) for (k in 0 until n) for (i in 0 until n) for (j in 0 until n) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j] return dist }

class UnionFind(n: Int) { val parent = IntArray(n) { it } val rank = IntArray(n) var components = n; private set fun find(x: Int): Int { if (parent[x] != x) parent[x] = find(parent[x]) // path compression return parent[x] } fun union(x: Int, y: Int): Boolean { val rx = find(x); val ry = find(y) if (rx == ry) return false when { rank[rx] < rank[ry] -> parent[rx] = ry rank[rx] > rank[ry] -> parent[ry] = rx else -> { parent[ry] = rx; rank[rx]++ } } components--; return true } fun connected(x: Int, y: Int) = find(x) == find(y) }

// Kruskal's: sort edges, greedily add cheapest non-cycle edge fun kruskal(n: Int, edges: List<Triple<Int,Int,Int>>): Int { val uf = UnionFind(n) var total = 0 for ((u, v, w) in edges.sortedBy { it.third }) { if (uf.union(u, v)) total += w } return total } // Prim's: grow tree, add cheapest frontier edge (min-heap) fun prim(n: Int, graph: Array<MutableList<Pair<Int,Int>>>): Int { val inMST = BooleanArray(n) val pq = PriorityQueue<Pair<Int,Int>>(compareBy { it.second }) pq.add(0 to 0) var total = 0 while (pq.isNotEmpty()) { val (u, w) = pq.poll() if (inMST[u]) continue inMST[u] = true; total += w for ((v, wt) in graph[u]) if (!inMST[v]) pq.add(v to wt) } return total }

fun numIslands(grid: Array<CharArray>): Int { val rows = grid.size; val cols = grid[0].size var count = 0 fun dfs(r: Int, c: Int) { if (r !in 0 until rows || c !in 0 until cols || grid[r][c] != '1') return grid[r][c] = '0' dfs(r-1,c); dfs(r+1,c); dfs(r,c-1); dfs(r,c+1) } for (r in 0 until rows) for (c in 0 until cols) if (grid[r][c] == '1') { count++; dfs(r, c) } return count }

// Start BFS from ALL sources simultaneously fun orangesRotting(grid: Array<IntArray>): Int { val rows = grid.size; val cols = grid[0].size val queue = ArrayDeque<Pair<Int,Int>>() var fresh = 0 for (r in 0 until rows) for (c in 0 until cols) when (grid[r][c]) { 2 -> queue.addLast(r to c); 1 -> fresh++ } if (fresh == 0) return 0 val dirs = listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1) var minutes = 0 while (queue.isNotEmpty()) { var rotted = false repeat(queue.size) { val (r, c) = queue.removeFirst() for ((dr, dc) in dirs) { val nr = r+dr; val nc = c+dc if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc]==1) { grid[nr][nc] = 2; fresh--; queue.addLast(nr to nc); rotted = true } } } if (rotted) minutes++ } return if (fresh == 0) minutes else -1 }

// 2-color BFS: if neighbor has SAME color, not bipartite fun isBipartite(graph: Array<IntArray>): Boolean { val n = graph.size; val color = IntArray(n) { -1 } for (start in 0 until n) { if (color[start] != -1) continue val queue = ArrayDeque<Int>() queue.addLast(start); color[start] = 0 while (queue.isNotEmpty()) { val node = queue.removeFirst() for (nb in graph[node]) { if (color[nb] == -1) { color[nb] = 1 - color[node]; queue.addLast(nb) } else if (color[nb] == color[node]) return false } } } return true }

// Tarjan's SCC fun tarjan(n: Int, graph: Map<Int, List<Int>>): List<List<Int>> { val disc = IntArray(n){-1}; val low = IntArray(n); val onStk = BooleanArray(n) val stk = ArrayDeque<Int>(); val sccs = mutableListOf<List<Int>>(); var t = 0 fun dfs(u: Int) { disc[u] = t; low[u] = t; t++; stk.addLast(u); onStk[u] = true for (v in graph[u].orEmpty()) { if (disc[v]==-1) { dfs(v); low[u] = minOf(low[u], low[v]) } else if (onStk[v]) low[u] = minOf(low[u], disc[v]) } if (low[u] == disc[u]) { val comp = mutableListOf<Int>() while (true) { val v = stk.removeLast(); onStk[v]=false; comp.add(v); if(v==u) break } sccs.add(comp) } } for (i in 0 until n) if (disc[i]==-1) dfs(i) return sccs }

// Bridge: edge (u,v) where low[v] > disc[u] // Articulation point: root with ≥2 children, or non-root with low[v] ≥ disc[u] fun findBridges(n: Int, graph: Map<Int, List<Int>>): List<Pair<Int,Int>> { val disc = IntArray(n){-1}; val low = IntArray(n); var t = 0 val bridges = mutableListOf<Pair<Int,Int>>() fun dfs(u: Int, parent: Int) { disc[u] = t; low[u] = t; t++ for (v in graph[u].orEmpty()) { if (disc[v]==-1) { dfs(v, u); low[u] = minOf(low[u], low[v]) if (low[v] > disc[u]) bridges.add(u to v) } else if (v != parent) low[u] = minOf(low[u], disc[v]) } } for (i in 0 until n) if (disc[i]==-1) dfs(i, -1) return bridges }

fun aStar(graph: Map<Int,List<Pair<Int,Int>>>, start: Int, target: Int, h: (Int)->Int): Int { val pq = PriorityQueue<Triple<Int,Int,Int>>(compareBy { it.first }) val g = mutableMapOf(start to 0) pq.add(Triple(h(start), 0, start)) while (pq.isNotEmpty()) { val (_, gc, node) = pq.poll() if (node == target) return gc if (gc > (g[node] ?: Int.MAX_VALUE)) continue for ((nb, w) in graph[node].orEmpty()) { val ng = gc + w if (ng < (g[nb] ?: Int.MAX_VALUE)) { g[nb] = ng; pq.add(Triple(ng+h(nb), ng, nb)) } } } return -1 }

// BFS-based Ford-Fulkerson: find augmenting paths with BFS fun maxFlow(n: Int, cap: Array<IntArray>, s: Int, t: Int): Int { val res = Array(n) { i -> cap[i].copyOf() } var total = 0 while (true) { val parent = IntArray(n){-1}; parent[s] = s val queue = ArrayDeque<Pair<Int,Int>>() queue.addLast(s to Int.MAX_VALUE) while (queue.isNotEmpty()) { val (u, flow) = queue.removeFirst() for (v in 0 until n) { if (parent[v]==-1 && res[u][v]>0) { parent[v] = u; val nf = minOf(flow, res[u][v]) if (v==t) { total+=nf; var c=v; while(c!=s){ val p=parent[c]; res[p][c]-=nf; res[c][p]+=nf; c=p }; break } queue.addLast(v to nf) } } } if (parent[t]==-1) break } return total }

// 1. Mark visited BEFORE enqueuing, not after dequeuing // WRONG: check visited on dequeue → duplicates in queue // RIGHT: visited.add(neighbor) returns false if already visited // 2. Undirected graphs: add BOTH directions for ((u, v) in edges) { graph[u]!!.add(v) graph[v]!!.add(u) // DON'T FORGET THIS } // 3. Undirected vs directed cycle detection are DIFFERENT // Undirected: back-to-parent is NOT a cycle (exclude parent) // Directed: use three-color (WHITE/GRAY/BLACK) // 4. Adjacency matrix for V=100,000 → 40 GB! Use adj list // 5. Dijkstra does NOT work with negative weights → use Bellman-Ford // 6. Handle disconnected graphs: loop over ALL vertices for (i in 0 until n) { if (!visited[i]) explore(i) // don't just start from vertex 0! } // 7. Integer overflow in shortest path // WRONG: dist[u] + w (overflows if dist[u] == MAX_VALUE) // RIGHT: check dist[u] != MAX_VALUE first // 8. Stale entries in Dijkstra's PQ val (u, d) = pq.poll() if (d > dist[u]) continue // skip stale! // 9. Grid bounds checking if (nr in 0 until rows && nc in 0 until cols) { /* safe */ } // 10. Topological sort on cyclic graph gives WRONG results silently // Use Kahn's — it detects cycles (processed < n means cycle)