Chapter 8

Graphs: Theory, Algorithms & Applications

Master graph theory and its most powerful algorithms. From BFS and DFS to shortest paths, minimum spanning trees, and topological sorting—learn to solve real-world connectivity, pathfinding, and network problems with deep theoretical understanding and production-ready C# code.

Algorithms

Problem Categories

40+

C# Examples

2000+

Lines of Code

Table of Contents

8.1 Graph Fundamentals 8.2 Graph Representations 8.3 BFS - Breadth-First Search 8.4 DFS - Depth-First Search 8.5 Topological Sort 8.6 Shortest Path Algorithms 8.7 Minimum Spanning Trees 8.8 Union-Find (Disjoint Set) 8.9 Grid Problems 8.10 Bipartite Graphs 8.11 Interview Tips

8.1

Graph Fundamentals

A graph is a fundamental data structure representing relationships between objects through vertices (nodes) and edges (connections). Master the terminology and taxonomy that forms the foundation for all graph algorithms.

Core Concepts

A graph G = (V, E) consists of vertices (nodes) and edges (connections). Graphs model networks: social connections, road systems, dependencies, and more.

Graph Properties & Types

Directed vs Undirected

Undirected: Edges have no direction; bidirectional. Edge (u,v) means u↔v.

Directed: Edges point from source to destination. Edge u→v means direction matters.

Weighted vs Unweighted

Unweighted: All edges equal; unit cost of 1.

Weighted: Each edge has associated cost/distance/capacity.

Cyclic vs Acyclic

Acyclic: DAG (Directed Acyclic Graph) has no cycles. Essential for dependencies.

Cyclic: Contains cycles; requires detection in many algorithms.

Connected vs Disconnected

Connected: Path exists between every pair of vertices.

Disconnected: Has isolated components unreachable from others.

Essential Terminology

Term	Definition	Example
Degree	Edges incident to vertex. Directed: in-degree, out-degree.	Vertex with 3 edges: degree 3
Path	Sequence where adjacent vertices connected by edge	A→B→C→D
Simple Path	Path with no repeating vertices	A→B→C valid; A→B→A invalid
Cycle	Path starting and ending at same vertex	A→B→C→A (length 3)
Connected Component	Maximal subset with all vertices mutually reachable	Separate clusters in disconnected graph
Strongly Connected	All vertices mutually reachable (directed graphs)	A→B→C→A forms strongly connected component

💡

Key Insight: Before applying an algorithm, identify graph type. Is it directed/undirected, weighted/unweighted, cyclic/acyclic, connected/disconnected? Wrong assumptions cause incorrect solutions.

8.2

Graph Representations

Three primary representations: adjacency matrix, adjacency list, and edge list. Each has distinct trade-offs in space, time complexity, and practical use cases.

1. Adjacency Matrix

2D array matrix[u][v] where entry indicates edge. Unweighted: 0/1. Weighted: stores weight.

Adjacency Matrix Implementation

Directed weighted graph using 2D array. O(1) edge lookup, O(V²) space.

Dense Graphs2D ArrayFast Lookup

Time Lookup

O(1)

Space

O(V²)

Neighbors

O(V)

Best For

Dense Graphs

public class AdjacencyMatrixGraph {
    private int[][] matrix;
    private int vertices;
    private const int INF = int.MaxValue / 2;

    public AdjacencyMatrixGraph(int v) {
        vertices = v;
        matrix = new int[v][];
        for (int i = 0; i < v; i++) {
            matrix[i] = new int[v];
            for (int j = 0; j < v; j++)
                matrix[i][j] = INF;
            matrix[i][i] = 0;
        }
    }

    public void AddEdge(int u, int v, int weight = 1) {
        matrix[u][v] = weight;
    }

    public int GetWeight(int u, int v) => matrix[u][v];

    public List<int> GetNeighbors(int u) {
        var neighbors = new List<int>();
        for (int v = 0; v < vertices; v++)
            if (matrix[u][v] != INF)
                neighbors.Add(v);
        return neighbors;
    }
}

2. Adjacency List

Dictionary/array mapping each vertex to list of neighbors. Most common, space-efficient for sparse graphs.

Adjacency List Implementation

Using Dictionary<int, List<int>> or List<List<int>>. O(1) average neighbor lookup, O(V+E) space.

Sparse GraphsHash MapEfficient

Space

O(V+E)

Neighbors

O(degree)

Add Edge

O(1)

Best For

Sparse Graphs

public class AdjacencyListGraph {
    private Dictionary<int, List<(int, int)>> adjList;
    // Tuple: (neighbor, weight)
    private int vertices;

    public AdjacencyListGraph(int v) {
        vertices = v;
        adjList = new Dictionary<int, List<(int, int)>>();
        for (int i = 0; i < v; i++)
            adjList[i] = new List<(int, int)>();
    }

    public void AddEdge(int u, int v, int weight = 1) {
        adjList[u].Add((v, weight));
    }

    public List<(int, int)> GetNeighbors(int u) {
        return adjList.ContainsKey(u) ? adjList[u] : new List<(int, int)>();
    }

    public List<int> GetUnweightedNeighbors(int u) {
        var neighbors = new List<int>();
        foreach (var (neighbor, _) in adjList[u])
            neighbors.Add(neighbor);
        return neighbors;
    }
}

3. Edge List

Array of edges Edge { from, to, weight }. Simple, useful for Kruskal's MST algorithm.

Edge List Implementation

Simple list of Edge objects. O(E) space, good for algorithms like Kruskal's.

Edge BasedSimple

public class Edge : IComparable<Edge> {
    public int From { get; set; }
    public int To { get; set; }
    public int Weight { get; set; }

    public Edge(int from, int to, int weight) {
        From = from;
        To = to;
        Weight = weight;
    }

    public int CompareTo(Edge other) {
        return Weight.CompareTo(other.Weight);
    }
}

Representation Comparison

Property	Adjacency Matrix	Adjacency List	Edge List
Space	O(V²)	O(V+E)	O(E)
Edge Lookup (u,v)	O(1)	O(degree(u))	O(E)
Get Neighbors	O(V)	O(degree(u))	O(E)
Add Edge	O(1)	O(1)	O(1)
Best For	Dense graphs, frequent lookups	Sparse graphs, most algorithms	Sorting edges, Kruskal's MST

💡

Practical Choice: Use adjacency list for most problems (BFS, DFS, Dijkstra, Prim's). Use edge list when sorting edges (Kruskal's). Use matrix only for dense graphs or when edge lookup is critical.

8.3

BFS - Breadth-First Search

Explores graph level-by-level using a queue. Essential for shortest paths in unweighted graphs, level-order traversal, and multi-source problems.

Algorithm Theory

BFS explores vertices by distance: visits all vertices at distance k before distance k+1. Uses a queue (FIFO). Perfect for shortest paths in unweighted graphs.

Initialize: Create queue, add source, mark source as visited

Process: Dequeue vertex u, explore all unvisited neighbors v

Enqueue: For each unvisited neighbor, mark visited, enqueue

Repeat: Continue until queue empty

BFS - Unweighted Shortest Path

Find shortest path in unweighted graph from source to all vertices using Queue.

Shortest PathQueueUnweighted

Time

O(V+E)

Space

O(V)

Visited

Boolean Array

public int[] BFS(AdjacencyListGraph graph, int source, int vertices) {
    int[] distance = new int[vertices];
    bool[] visited = new bool[vertices];
    
    for (int i = 0; i < vertices; i++)
        distance[i] = -1;

    var queue = new Queue<int>();
    queue.Enqueue(source);
    visited[source] = true;
    distance[source] = 0;

    while (queue.Count > 0) {
        int u = queue.Dequeue();
        
        foreach (var (v, _) in graph.GetNeighbors(u)) {
            if (!visited[v]) {
                visited[v] = true;
                distance[v] = distance[u] + 1;
                queue.Enqueue(v);
            }
        }
    }

    return distance;
}

Problem: Number of Islands (Medium)

Given: 2D grid with '1' (land) and '0' (water). Find: Number of connected islands (use BFS/DFS to explore each island).

Number of Islands - BFS Solution

Mark each land cell as visited while exploring islands with BFS. Time: O(m*n).

Grid BFSConnected Components

public int NumIslands(char[][] grid) {
    int rows = grid.Length;
    int cols = grid[0].Length;
    int islands = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                BFS(grid, r, c, rows, cols);
                islands++;
            }
        }
    }

    return islands;
}

private void BFS(char[][] grid, int startR, int startC, int rows, int cols) {
    var queue = new Queue<(int, int)>();
    queue.Enqueue((startR, startC));
    grid[startR][startC] = '0'; // Mark visited

    int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, 
                                           new int[] { 0, -1 }, new int[] { -1, 0 } };

    while (queue.Count > 0) {
        var (r, c) = queue.Dequeue();

        foreach (var dir in directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                grid[nr][nc] = '0';
                queue.Enqueue((nr, nc));
            }
        }
    }
}

Problem: Rotting Oranges (Medium) - Multi-Source BFS

Given: Grid with fresh (1), rotten (2), empty (0). Each minute, rotten spreads to adjacent fresh. Find: Minutes until all fresh rot, or -1 if impossible.

Rotting Oranges - Multi-Source BFS

Initialize queue with all rotten oranges; expand level-by-level (one minute per level).

Multi-Source BFSTime Simulation

public int OrangesRotting(int[][] grid) {
    int rows = grid.Length;
    int cols = grid[0].Length;
    int freshCount = 0;
    var queue = new Queue<(\int, int)>();

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) {
                queue.Enqueue((r, c));
            } else if (grid[r][c] == 1) {
                freshCount++;
            }
        }
    }

    if (freshCount == 0) return 0;

    int time = -1;
    int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, 
                                           new int[] { 0, -1 }, new int[] { -1, 0 } };

    while (queue.Count > 0) {
        int levelSize = queue.Count;
        time++;

        for (int i = 0; i < levelSize; i++) {
            var (r, c) = queue.Dequeue();

            foreach (var dir in directions) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    queue.Enqueue((nr, nc));
                    freshCount--;
                }
            }
        }
    }

    return freshCount == 0 ? time : -1;
}

Problem: Word Ladder (Hard)

Given: start word, end word, list of valid words. Find: Shortest sequence of words where each differs by one letter.

Word Ladder - BFS Solution

Model words as nodes; connect if one letter apart. BFS finds shortest path.

Word TransformationShortest Path

public int LadderLength(string beginWord, string endWord, 
                              IList<string> wordList) {
    var wordSet = new HashSet<string>(wordList);
    if (!wordSet.Contains(endWord)) return 0;

    var queue = new Queue<string>();
    queue.Enqueue(beginWord);
    var visited = new HashSet<string> { beginWord };
    int level = 1;

    while (queue.Count > 0) {
        int levelSize = queue.Count;
        
        for (int i = 0; i < levelSize; i++) {
            string word = queue.Dequeue();
            
            if (word == endWord) return level;

            for (int j = 0; j < word.Length; j++) {
                char[] chars = word.ToCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[j] = c;
                    string newWord = new string(chars);
                    
                    if (wordSet.Contains(newWord) && !visited.Contains(newWord)) {
                        visited.Add(newWord);
                        queue.Enqueue(newWord);
                    }
                }
            }
        }
        level++;
    }

    return 0;
}

⚠️

BFS Guarantees: BFS finds shortest path in unweighted graphs only. For weighted graphs, use Dijkstra. Always use a visited set to avoid revisiting nodes.

8.4

DFS - Depth-First Search

Explores graph deeply using recursion or stack. Essential for cycle detection, topological sorting, connected components, and graph analysis.

Algorithm Theory

DFS explores deeply: goes as far as possible along branch before backtracking. Uses recursion (call stack) or explicit stack. Better for detecting cycles and analyzing graph structure.

1. Recursive DFS

Recursive DFS

Clean, intuitive implementation using call stack. Perfect for understanding DFS logic.

RecursionExploration

Time

O(V+E)

Space

O(V) recursion

Visited

Boolean Array

public void DFSRecursive(AdjacencyListGraph graph, int vertex, 
                              bool[] visited) {
    visited[vertex] = true;
    Console.Write(vertex + " ");

    foreach (var (neighbor, _) in graph.GetNeighbors(vertex)) {
        if (!visited[neighbor]) {
            DFSRecursive(graph, neighbor, visited);
        }
    }
}

2. Iterative DFS (using Stack)

Iterative DFS with Explicit Stack

Avoid recursion depth limits with explicit stack. More control over traversal.

StackIterative

public List<int> DFSIterative(AdjacencyListGraph graph, int start, int vertices) {
    var result = new List<int>();
    bool[] visited = new bool[vertices];
    var stack = new Stack<int>();

    stack.Push(start);
    visited[start] = true;

    while (stack.Count > 0) {
        int u = stack.Pop();
        result.Add(u);

        foreach (var (v, _) in graph.GetNeighbors(u)) {
            if (!visited[v]) {
                visited[v] = true;
                stack.Push(v);
            }
        }
    }

    return result;
}

Cycle Detection in Directed Graphs (3-Color DFS)

Track vertex states: WHITE (unvisited), GRAY (visiting), BLACK (done). If we reach a GRAY vertex, cycle detected.

Cycle Detection - 3-Color DFS

WHITE=unvisited, GRAY=in-progress, BLACK=finished. Reach GRAY → cycle.

Cycle DetectionDirected Graphs

public bool HasCycleDirect(AdjacencyListGraph graph, int vertices) {
    int[] color = new int[vertices]; // 0=white, 1=gray, 2=black

    for (int i = 0; i < vertices; i++) {
        if (color[i] == 0 && DFSCycle(graph, i, color)) {
            return true;
        }
    }
    return false;
}

private bool DFSCycle(AdjacencyListGraph graph, int u, int[] color) {
    color[u] = 1; // Mark as GRAY (visiting)

    foreach (var (v, _) in graph.GetNeighbors(u)) {
        if (color[v] == 1) {
            return true; // Back edge found (GRAY vertex)
        }
        if (color[v] == 0 && DFSCycle(graph, v, color)) {
            return true;
        }
    }

    color[u] = 2; // Mark as BLACK (done)
    return false;
}

Cycle Detection in Undirected Graphs

If we reach a visited neighbor that's not our parent, cycle exists.

Cycle Detection - Undirected Graphs

If visited neighbor ≠ parent, cycle detected.

Cycle DetectionUndirected

public bool HasCycleUndirected(int[][] adj, int n) {
    bool[] visited = new bool[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i] && DFS(adj, i, -1, visited)) {
            return true;
        }
    }
    return false;
}

private bool DFS(int[][] adj, int u, int parent, bool[] visited) {
    visited[u] = true;

    foreach (int v in adj[u]) {
        if (v == parent) continue; // Skip parent edge
        if (visited[v]) return true; // Found cycle
        if (DFS(adj, v, u, visited)) return true;
    }
    return false;
}

Problem: Clone Graph (Medium)

Given: Node reference in connected undirected graph. Find: Deep copy of entire graph.

Clone Graph - DFS Solution

DFS traversal creating new nodes and mapping old→new with HashMap.

Graph CloningHashMap

public class Node {
    public int val;
    public List<Node> neighbors;

    public Node(int _val = 0) {
        val = _val;
        neighbors = new List<Node>();
    }
}

public Node CloneGraph(Node node) {
    if (node == null) return null;

    var map = new Dictionary<Node, Node>();
    DFS(node, map);
    return map[node];
}

private void DFS(Node node, Dictionary<Node, Node> map) {
    if (map.ContainsKey(node)) return;

    map[node] = new Node(node.val);

    foreach (Node neighbor in node.neighbors) {
        DFS(neighbor, map);
        map[node].neighbors.Add(map[neighbor]);
    }
}

Problem: Course Schedule I (Medium)

Given: Courses and prerequisites. Find: Can all courses be completed? (detect cycle in directed graph)

Course Schedule - Cycle Detection

If cycle exists in course prerequisites, impossible to complete all courses.

Cycle DetectionPrerequisites

public bool CanFinish(int numCourses, int[][] prerequisites) {
    var adj = new List<List<int>>();
    for (int i = 0; i < numCourses; i++)
        adj.Add(new List<int>());

    foreach (var pre in prerequisites)
        adj[pre[1]].Add(pre[0]);

    int[] color = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        if (color[i] == 0 && HasCycle(i, adj, color))
            return false;
    }
    return true;
}

private bool HasCycle(int u, List<List<int>> adj, int[] color) {
    color[u] = 1;
    foreach (int v in adj[u]) {
        if (color[v] == 1) return true;
        if (color[v] == 0 && HasCycle(v, adj, color)) return true;
    }
    color[u] = 2;
    return false;
}

Problem: Pacific Atlantic Water Flow (Hard)

Given: 2D elevation grid. Find: Cells where water flows to both Pacific (left/top) and Atlantic (right/bottom) oceans.

Pacific Atlantic Water Flow - DFS

Reverse logic: start from borders, DFS backwards on increasing elevations.

Grid DFSReverse Logic

public IList<IList<int>> PacificAtlantic(int[][] heights) {
    int rows = heights.Length;
    int cols = heights[0].Length;
    bool[][] pacific = new bool[rows][];
    bool[][] atlantic = new bool[rows][];
    
    for (int i = 0; i < rows; i++) {
        pacific[i] = new bool[cols];
        atlantic[i] = new bool[cols];
    }

    int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 },
                                           new int[] { 0, -1 }, new int[] { -1, 0 } };

    // Pacific borders: top and left
    for (int i = 0; i < rows; i++)
        DFS(heights, i, 0, pacific, directions);
    for (int j = 0; j < cols; j++)
        DFS(heights, 0, j, pacific, directions);

    // Atlantic borders: bottom and right
    for (int i = 0; i < rows; i++)
        DFS(heights, i, cols - 1, atlantic, directions);
    for (int j = 0; j < cols; j++)
        DFS(heights, rows - 1, j, atlantic, directions);

    var result = new List<IList<int>>();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (pacific[i][j] && atlantic[i][j])
                result.Add(new List<int> { i, j });
        }
    }
    return result;
}

private void DFS(int[][] heights, int r, int c, bool[][] visited, 
                  int[][] directions) {
    visited[r][c] = true;

    foreach (var dir in directions) {
        int nr = r + dir[0];
        int nc = c + dir[1];

        if (nr >= 0 && nr < heights.Length && nc >= 0 && nc < heights[0].Length &&
            !visited[nr][nc] && heights[nr][nc] >= heights[r][c]) {
            DFS(heights, nr, nc, visited, directions);
        }
    }
}

⚠️

Stack Overflow Risk: Deep recursion in large graphs can overflow the call stack. For graphs >1000 nodes, use iterative DFS with explicit stack or BFS instead.

8.5

Topological Sort

Orders vertices in a DAG such that for every directed edge u→v, u comes before v. Critical for dependency resolution, task scheduling, and build systems.

Theory: When & Why

Prerequisites: Only works on DAGs (no cycles). If cycle exists, impossible to topologically sort. Common applications: package dependencies, course prerequisites, build systems, compilation order.

1. Kahn's Algorithm (BFS-based)

Process vertices with in-degree 0 (no dependencies). Remove vertex, decrease in-degree of neighbors.

Kahn's Algorithm - Topological Sort

BFS-based approach using in-degrees. Process nodes with in-degree 0 first.

BFS-basedIn-degree

Time

O(V+E)

Space

O(V)

Detects

Cycles

public int[] TopologicalSortKahn(int numCourses, 
                                    int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<int>> adj = new List<List<int>>();
    
    for (int i = 0; i < numCourses; i++)
        adj.Add(new List<int>());

    foreach (var pre in prerequisites) {
        adj[pre[1]].Add(pre[0]);
        inDegree[pre[0]]++;
    }

    var queue = new Queue<int>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0)
            queue.Enqueue(i);

    List<int> result = new List<int>();

    while (queue.Count > 0) {
        int u = queue.Dequeue();
        result.Add(u);

        foreach (int v in adj[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0)
                queue.Enqueue(v);
        }
    }

    return result.Count == numCourses ? result.ToArray() : new int[0];
}

2. DFS-based Topological Sort

Use post-order DFS (add to result after visiting all descendants). Reverse result for topological order.

DFS-based Topological Sort

Post-order DFS: add vertex after recursion completes. Reverse final result.

DFSPost-order

public int[] TopologicalSortDFS(int numCourses, 
                                  int[][] prerequisites) {
    List<List<int>> adj = new List<List<int>>();
    for (int i = 0; i < numCourses; i++)
        adj.Add(new List<int>());

    foreach (var pre in prerequisites)
        adj[pre[1]].Add(pre[0]);

    int[] color = new int[numCourses];
    Stack<int> stack = new Stack<int>();

    for (int i = 0; i < numCourses; i++) {
        if (color[i] == 0) {
            if (!DFSTopoSort(i, adj, color, stack))
                return new int[0]; // Cycle detected
        }
    }

    int[] result = new int[numCourses];
    int idx = 0;
    while (stack.Count > 0)
        result[idx++] = stack.Pop();

    return result;
}

private bool DFSTopoSort(int u, List<List<int>> adj, 
                           int[] color, Stack<int> stack) {
    color[u] = 1; // GRAY

    foreach (int v in adj[u]) {
        if (color[v] == 1) return false; // Cycle
        if (color[v] == 0) {
            if (!DFSTopoSort(v, adj, color, stack))
                return false;
        }
    }

    color[u] = 2; // BLACK
    stack.Push(u);
    return true;
}

Problem: Course Schedule II (Medium)

Given: Number of courses and prerequisites. Find: Valid order to complete all courses, or [] if impossible.

Solution: Use Kahn's algorithm or DFS topological sort. Return courses in dependency order.

Problem: Alien Dictionary (Hard)

Given: List of words in alien language. Find: Character ordering (topological order of characters).

Alien Dictionary - Topological Sort

Compare adjacent words to find character order, then topologically sort characters.

Character OrderingKahn's Algorithm

public string AlienOrder(IList<string> words) {
    Dictionary<char, HashSet<char>> graph = new Dictionary<char, HashSet<char>>();
    Dictionary<char, int> inDegree = new Dictionary<char, int>();

    // Initialize all characters
    foreach (string word in words) {
        foreach (char c in word) {
            if (!graph.ContainsKey(c)) {
                graph[c] = new HashSet<char>();
                inDegree[c] = 0;
            }
        }
    }

    // Build graph
    for (int i = 0; i < words.Count - 1; i++) {
        string w1 = words[i];
        string w2 = words[i + 1];
        int minLen = Math.Min(w1.Length, w2.Length);

        for (int j = 0; j < minLen; j++) {
            if (w1[j] != w2[j]) {
                if (!graph[w1[j]].Contains(w2[j])) {
                    graph[w1[j]].Add(w2[j]);
                    inDegree[w2[j]]++;
                }
                break;
            }
        }
    }

    // Kahn's algorithm
    Queue<char> queue = new Queue<char>();
    foreach (var kvp in inDegree) {
        if (kvp.Value == 0)
            queue.Enqueue(kvp.Key);
    }

    string result = "";
    while (queue.Count > 0) {
        char c = queue.Dequeue();
        result += c;

        foreach (char neighbor in graph[c]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0)
                queue.Enqueue(neighbor);
        }
    }

    return result.Length == graph.Count ? result : "";
}

💡

Choose Between Kahn's & DFS: Kahn's detects cycles naturally (incomplete result). DFS requires explicit cycle detection. For interviews, Kahn's is typically simpler.

8.6

Shortest Path Algorithms

Find minimum distance/cost from source to all vertices. Dijkstra for non-negative weights, Bellman-Ford for negative weights.

1. Dijkstra's Algorithm (Non-negative Weights)

Greedy approach: Always process unvisited vertex with smallest distance. Works only with non-negative edge weights.

Dijkstra's Algorithm with PriorityQueue

Greedy: always pick minimum-distance unvisited vertex. Time: O((V+E)logV).

Shortest PathGreedyPriorityQueue

Time

O((V+E)logV)

Space

O(V)

Weights

Non-negative

Negative Cycles

Not handled

public int[] Dijkstra(List<(int, int)>[] graph, int source, int n) {
    int[] distance = new int[n];
    for (int i = 0; i < n; i++)
        distance[i] = int.MaxValue;
    distance[source] = 0;

    var pq = new PriorityQueue<(int, int), int>();
    pq.Enqueue((source, 0), 0);

    while (pq.Count > 0) {
        var (u, _) = pq.Dequeue();

        foreach (var (v, weight) in graph[u]) {
            if (distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
                pq.Enqueue((v, distance[v]), distance[v]);
            }
        }
    }

    return distance;
}

2. Bellman-Ford Algorithm (Handles Negative Weights)

Relaxes all edges V-1 times. Detects negative cycles. Slower but more general than Dijkstra.

Bellman-Ford Algorithm

Relax all edges V-1 times. O(VE) time. Detects negative cycles.

Shortest PathNegative WeightsCycle Detection

Time

O(VE)

Weights

Negative OK

Cycles

Detected

public long[] BellmanFord(int n, List<(int, int, long)> edges, int source) {
    long[] distance = new long[n];
    for (int i = 0; i < n; i++)
        distance[i] = long.MaxValue;
    distance[source] = 0;

    // Relax edges V-1 times
    for (int i = 0; i < n - 1; i++) {
        foreach (var (u, v, weight) in edges) {
            if (distance[u] != long.MaxValue && distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
            }
        }
    }

    // Check for negative cycle
    foreach (var (u, v, weight) in edges) {
        if (distance[u] != long.MaxValue && distance[u] + weight < distance[v]) {
            // Negative cycle detected
            return null;
        }
    }

    return distance;
}

Problem: Network Delay Time (Medium)

Given: Network with delays, find time for signal to reach all nodes from source. Return -1 if unreachable.

Network Delay Time - Dijkstra

Find shortest path to all nodes, return maximum distance.

DijkstraNetwork

public int NetworkDelayTime(int[][] times, int n, int k) {
    List<(\int, int)>[] graph = new List<(\int, int)>[n + 1];
    for (int i = 0; i <= n; i++)
        graph[i] = new List<(\int, int)>();

    foreach (var time in times)
        graph[time[0]].Add((time[1], time[2]));

    int[] distance = new int[n + 1];
    for (int i = 0; i <= n; i++)
        distance[i] = int.MaxValue;
    distance[k] = 0;

    var pq = new PriorityQueue<(int, int), int>();
    pq.Enqueue((k, 0), 0);

    while (pq.Count > 0) {
        var (u, _) = pq.Dequeue();

        foreach (var (v, weight) in graph[u]) {
            if (distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
                pq.Enqueue((v, distance[v]), distance[v]);
            }
        }
    }

    int maxTime = 0;
    for (int i = 1; i <= n; i++) {
        if (distance[i] == int.MaxValue) return -1;
        maxTime = Math.Max(maxTime, distance[i]);
    }

    return maxTime;
}

Problem: Cheapest Flights Within K Stops (Medium)

Given: Flights with cost, max K stops. Find: Minimum cost from source to destination.

Cheapest Flights - Bellman-Ford Variant

Relax edges K times (K stops constraint). Track distances over iterations.

Bellman-FordK-constraints

public int FindCheapestPrice(int n, int[][] flights, 
                                  int src, int dst, int k) {
    int[] distance = new int[n];
    for (int i = 0; i < n; i++)
        distance[i] = int.MaxValue;
    distance[src] = 0;

    // Relax edges k+1 times (at most k stops = k+1 edges)
    for (int i = 0; i <= k; i++) {
        int[] tmpDistance = (int[])distance.Clone();

        foreach (var flight in flights) {
            int u = flight[0];
            int v = flight[1];
            int price = flight[2];

            if (distance[u] != int.MaxValue && distance[u] + price < tmpDistance[v]) {
                tmpDistance[v] = distance[u] + price;
            }
        }

        distance = tmpDistance;
    }

    return distance[dst] == int.MaxValue ? -1 : distance[dst];
}

⚠️

Dijkstra vs Bellman-Ford: Use Dijkstra for non-negative weights (faster O(V log V)). Use Bellman-Ford only if graph has negative weights. Never use Dijkstra with negative edges!

8.7

Minimum Spanning Tree

Connect all vertices with minimum total edge weight. Two approaches: Kruskal's (edge-based) and Prim's (vertex-based).

1. Kruskal's Algorithm (with Union-Find)

Sort edges by weight, greedily add edge if it doesn't create cycle (check with Union-Find).

Kruskal's Algorithm - MST

Sort edges, greedily add non-cycle edges using Union-Find. O(E log E).

Kruskal'sUnion-FindEdge-based

Time

O(E log E)

Space

O(V)

Approach

Edge-based

public int KruskalMST(int n, List<(\int, int, int)> edges) {
    edges.Sort((\a, b) => a.Item3.CompareTo(b.Item3));

    var uf = new UnionFind(n);
    int mstCost = 0;
    int edgesAdded = 0;

    foreach (var (u, v, weight) in edges) {
        if (uf.Find(u) != uf.Find(v)) {
            uf.Union(u, v);
            mstCost += weight;
            edgesAdded++;
            if (edgesAdded == n - 1) break;
        }
    }

    return edgesAdded == n - 1 ? mstCost : -1;
}

2. Prim's Algorithm (Vertex-based)

Start from vertex, greedily add minimum-weight edge connecting tree to new vertex.

Prim's Algorithm - MST

Start vertex, greedily add minimum edge to new vertex. O(V² ) or O((V+E)logV) with PQ.

Prim'sVertex-basedGreedy

public int PrimMST(int n, List<(\int, int, int)>[] graph) {
    bool[] inMST = new bool[n];
    int[] minCost = new int[n];
    for (int i = 0; i < n; i++)
        minCost[i] = int.MaxValue;

    minCost[0] = 0;
    int mstCost = 0;

    for (int i = 0; i < n; i++) {
        // Find min cost vertex not in MST
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!inMST[j] && (u == -1 || minCost[j] < minCost[u]))
                u = j;
        }

        inMST[u] = true;
        mstCost += minCost[u];

        // Update min costs of neighbors
        foreach (var (v, weight) in graph[u]) {
            if (!inMST[v] && weight < minCost[v])
                minCost[v] = weight;
        }
    }

    return mstCost;
}

Problem: Min Cost to Connect Points (Medium)

Given: 2D points, cost = Manhattan distance. Find: Minimum cost to connect all points.

Min Cost Connect Points - Kruskal's

Build complete graph with Manhattan distances, find MST.

MSTKruskal's

public long MinCostConnectPoints(int[][] points) {
    int n = points.Length;
    List<(\int, int, long)> edges = new List<(\int, int, long)>();

    // Build complete graph
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long dist = Math.Abs(points[i][0] - points[j][0]) +
                        Math.Abs(points[i][1] - points[j][1]);
            edges.Add((i, j, dist));
        }
    }

    edges.Sort((\a, b) => a.Item3.CompareTo(b.Item3));

    var uf = new UnionFind(n);
    long cost = 0;
    int edgesAdded = 0;

    foreach (var (u, v, weight) in edges) {
        if (uf.Find(u) != uf.Find(v)) {
            uf.Union(u, v);
            cost += weight;
            edgesAdded++;
            if (edgesAdded == n - 1) break;
        }
    }

    return cost;
}

💡

Kruskal vs Prim: Use Kruskal for sparse graphs (fewer edges) and when edges are given as list. Use Prim for dense graphs and when adjacency list is available. Both find same MST cost.

8.8

Union-Find (Disjoint Set Union)

Efficiently track connected components and detect cycles. Critical for Kruskal's MST and many connectivity problems.

Core Operations

Find: Determine which set element belongs to (with path compression). Union: Merge two sets (with rank optimization).

Union-Find with Path Compression & Union by Rank

Optimized DSU: O(α(n)) amortized, nearly O(1) per operation.

Path CompressionUnion by RankOptimized

Find

O(α(n))

Union

O(α(n))

Space

O(n)

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // Find with path compression
    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]); // Path compression
        }
        return parent[x];
    }

    // Union by rank
    public bool Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);

        if (rootX == rootY) return false; // Already connected

        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }

    public bool Connected(int x, int y) => Find(x) == Find(y);
}

Problem: Number of Connected Components (Easy)

Given: N nodes, list of edges. Find: Number of connected components.

Connected Components - Union-Find

Union all edges, count remaining distinct roots.

Union-FindConnected Components

public int CountComponents(int n, int[][] edges) {
    var uf = new UnionFind(n);

    foreach (var edge in edges) {
        uf.Union(edge[0], edge[1]);
    }

    var roots = new HashSet<int>();
    for (int i = 0; i < n; i++) {
        roots.Add(uf.Find(i));
    }

    return roots.Count;
}

Problem: Redundant Connection (Medium)

Given: Tree with one extra edge causing a cycle. Find: The redundant edge.

Redundant Connection - Union-Find

When union fails (nodes already connected), that's the redundant edge.

Union-FindCycle Detection

public int[] FindRedundantConnection(int[][] edges) {
    var uf = new UnionFind(edges.Length + 1);

    foreach (var edge in edges) {
        if (!uf.Union(edge[0], edge[1])) {
            return edge; // Union failed = cycle detected
        }
    }

    return new int[0];
}

⚠️

Path Compression Critical: Always implement path compression in Find(). Without it, worst-case is O(n) per operation. With both optimizations (path compression + union by rank), average is nearly O(1).

8.9

Grid as Graph

2D grids are graphs where cells are vertices and adjacent cells are edges. Apply BFS/DFS directly to explore connected regions.

Grid Traversal Template

Grids have implicit edges (4-directional or 8-directional). Define directions array, check bounds, avoid revisiting.

Problem: Surrounded Regions (Medium)

Given: 2D board with 'X' and 'O'. Find: Replace 'O' surrounded by 'X' with 'X' (border 'O' not surrounded).

Surrounded Regions - Reverse DFS

Mark border-connected 'O' as safe, then replace remaining 'O' with 'X'.

Grid DFSReverse Logic

public void Solve(char[][] board) {
    int rows = board.Length;
    int cols = board[0].Length;

    // Mark border-connected 'O' as '#'
    for (int r = 0; r < rows; r++) {
        if (board[r][0] == 'O') DFS(board, r, 0);
        if (board[r][cols - 1] == 'O') DFS(board, r, cols - 1);
    }
    for (int c = 0; c < cols; c++) {
        if (board[0][c] == 'O') DFS(board, 0, c);
        if (board[rows - 1][c] == 'O') DFS(board, rows - 1, c);
    }

    // Replace remaining 'O' with 'X', restore '#' to 'O'
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (board[r][c] == 'O') board[r][c] = 'X';
            else if (board[r][c] == '#') board[r][c] = 'O';
        }
    }
}

private void DFS(char[][] board, int r, int c) {
    if (r < 0 || r >= board.Length || c < 0 || c >= board[0].Length || 
        board[r][c] != 'O') return;

    board[r][c] = '#';
    DFS(board, r + 1, c);
    DFS(board, r - 1, c);
    DFS(board, r, c + 1);
    DFS(board, r, c - 1);
}

Problem: 01 Matrix (Medium)

Given: Binary matrix. Find: Distance from each cell to nearest 0 (multi-source BFS).

01 Matrix - Multi-Source BFS

Initialize queue with all 0s, expand level-by-level to compute distances.

Multi-Source BFSDistance

public int[][] UpdateMatrix(int[][] mat) {
    int rows = mat.Length;
    int cols = mat[0].Length;
    var queue = new Queue<(\int, int)>();

    // Add all 0s to queue
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (mat[r][c] == 0)
                queue.Enqueue((r, c));
            else
                mat[r][c] = int.MaxValue;
        }
    }

    int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 },
                                           new int[] { 0, -1 }, new int[] { -1, 0 } };

    while (queue.Count > 0) {
        var (r, c) = queue.Dequeue();

        foreach (var dir in directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && 
                mat[nr][nc] > mat[r][c] + 1) {
                mat[nr][nc] = mat[r][c] + 1;
                queue.Enqueue((nr, nc));
            }
        }
    }

    return mat;
}

💡

Grid BFS Template: Always check bounds before recursing/enqueueing. Use direction arrays to avoid code repetition. Mark cells as visited in-place or with separate array.

8.10

Bipartite Graphs

A graph is bipartite if vertices can be colored with 2 colors such that no adjacent vertices share a color. Equivalently: no odd-length cycles.

Bipartite Check with BFS (2-Coloring)

Try to color graph with 2 colors (0 and 1). If any edge connects same-color vertices, not bipartite.

Bipartite Check - BFS 2-Coloring

Color vertices alternately, check if any edge connects same color.

BFS2-Coloring

Time

O(V+E)

Space

O(V)

public bool IsBipartite(int[][] graph) {
    int[] color = new int[graph.Length];
    for (int i = 0; i < graph.Length; i++)
        color[i] = -1;

    for (int i = 0; i < graph.Length; i++) {
        if (color[i] == -1) {
            if (!BFS(graph, i, color))
                return false;
        }
    }
    return true;
}

private bool BFS(int[][] graph, int start, int[] color) {
    var queue = new Queue<int>();
    queue.Enqueue(start);
    color[start] = 0;

    while (queue.Count > 0) {
        int u = queue.Dequeue();

        foreach (int v in graph[u]) {
            if (color[v] == -1) {
                color[v] = 1 - color[u]; // Opposite color
                queue.Enqueue(v);
            } else if (color[v] == color[u]) {
                return false; // Same color = not bipartite
            }
        }
    }
    return true;
}

💡

Bipartite Property: A connected graph is bipartite if and only if it contains no odd-length cycles. Disconnected graphs: check all components.

8.11

Interview Tips & Common Patterns

Problem Classification

Problem Type	Algorithm	Complexity	When to Use
Shortest path (unweighted)	BFS	O(V+E)	Unweighted graphs, level-order traversal
Shortest path (weighted)	Dijkstra or Bellman-Ford	O((V+E)logV) or O(VE)	Non-negative or negative weights
All pairs shortest path	Floyd-Warshall	O(V³)	Small dense graphs, negative weights OK
Connectivity/Components	DFS, BFS, or Union-Find	O(V+E)	Find connected components, check connectivity
Cycle detection	DFS (3-color) or Union-Find	O(V+E)	Directed: use 3-color DFS; Undirected: Union-Find
Topological sort	Kahn's or DFS	O(V+E)	DAG only, dependencies, build order
Minimum spanning tree	Kruskal's or Prim's	O(E log E) or O(V²)	Connect all vertices, minimize total weight

Graph Problem Checklist

Identify Graph Type: Directed/undirected? Weighted/unweighted? Cyclic/acyclic?

Choose Representation: Adjacency list (most common), matrix (dense), or edge list (sorting needed)

Select Algorithm: BFS (unweighted shortest path), DFS (connectivity), Dijkstra (weighted), Kruskal/Prim (MST)

Handle Edge Cases: Disconnected graphs, self-loops, cycles, isolated vertices

Implement Visited Tracking: Avoid infinite loops; use boolean array, set, or coloring

Common Pitfalls

Mistakes to Avoid

Using Dijkstra with negative weights (fails)

Forgetting to mark vertices as visited (infinite loops)

Assuming BFS finds shortest path in weighted graphs (wrong)

Applying topological sort to cyclic graphs (invalid)

Not handling disconnected components

Integer overflow in distance/cost calculations

Best Practices

Check graph type before selecting algorithm

Use visited array/set consistently

Validate input constraints (1 ≤ n ≤ 10⁵)

Test with disconnected/empty graphs

Use long for large distances/weights

Implement Union-Find with both optimizations

Time Complexity Reference

Algorithm	Time	Space	Notes
BFS	O(V+E)	O(V)	Queue-based, level-order
DFS	O(V+E)	O(V)	Stack or recursion-based
Dijkstra	O((V+E)logV)	O(V)	With binary heap/PriorityQueue
Bellman-Ford	O(VE)	O(V)	Handles negative weights
Floyd-Warshall	O(V³)	O(V²)	All-pairs shortest paths
Kruskal's (MST)	O(E log E)	O(V)	Sorting edges dominates
Prim's (MST)	O(V²) or O((V+E)logV)	O(V)	Depends on implementation
Union-Find (α(n))	O(α(n))	O(n)	Nearly O(1) per operation

Interview Tips

Tip 1

Clarify the Problem

Ask about graph type, constraints, whether result should be ordered, and if you need to find one solution or all solutions.

Tip 2

Start Simple

Implement BFS or DFS first. Many problems are variations of these traversals. Optimize only after basic solution works.

Tip 3

Test Thoroughly

Test with disconnected graphs, single node, empty graph, self-loops, and duplicate edges. Edge cases expose most implementation bugs.

Quick Reference: When to Use Each Algorithm

BFS: Shortest path in unweighted graphs, level-order traversal, finding connected components
DFS: Connectivity, topological sort (DFS version), cycle detection, path existence
Dijkstra: Single-source shortest path with non-negative weights
Bellman-Ford: Single-source shortest path with negative weights, detect negative cycles
Kruskal's: MST when edges are naturally available as a list, sparse graphs
Prim's: MST when adjacency list is given, dense graphs
Union-Find: Connected components, cycle detection in undirected graphs, checking connectivity
Topological Sort: DAG ordering, dependency resolution, compilation order

ℹ️

Final Thought: Graph problems are often variations of BFS/DFS. Master these two fundamentals, understand their properties, and you can solve 80% of graph problems. The remaining 20% add Dijkstra, topological sort, or Union-Find on top.