Chapter 6 Graph

6.0.1 Undirected Graphs

Imagine a graph with as the following:

1 -- 0 -- 4
|
5 -- 6
|  / | \
| /  |   \
2 -- 3 -- 7

An adjacency list is created with an array of lists. Size of the array is equal to the number of vertices. Each entry represents the list of vertices adjacent to the \(i^{th}\) vertex. Each node maintains a list of all its adjacent edges, then, for each node, you could discover all its neighbors by traversing its adjacency list just once in linear time.

| 0 | -- 1 -- 4
| 1 | -- 0 -- 5
| 2 | -- 3 -- 5 -- 6
| 3 | -- 2 -- 6 -- 7
| 4 | -- 0
| 5 | -- 1 -- 2 -- 6
| 6 | -- 2 -- 3 -- 5 -- 7
| 7 | -- 3 -- 6

The adjacency information can also transform into matrix form with the convention followed here (for undirected graphs) is that each edge adds 1 to the appropriate cell in the matrix, and each loop adds 2. For each node, you have to traverse an entire row of length V in the matrix to discover all its outgoing edges.

0, 1, 0, 0, 1, 0, 0, 0
1, 0, 0, 0, 0, 1, 0, 0
0, 0, 0, 1, 0, 1, 1, 0
0, 0, 1, 0, 0, 0, 1, 1
1, 0, 0, 0, 0, 0, 0, 0
0, 1, 1, 0, 0, 0, 1, 0
0, 0, 1, 1, 0, 1, 0, 1
0, 0, 0, 1, 0, 0, 1, 0

In addition, a “visited” array that we’ll use to keep track of which vertices have been visited.

class Graph  {
    private int numOfVertices;   //No. of vertices
    private List<Integer> adj[]; //Adjacency List
    private boolean[] visited;   //visited mark for each vertex

    // Constructor
    public Graph(int num) {
        numOfVertices = num;
        adj = new LinkedList[v];
        for (int i=0; i<numOfVertices; ++i) {
            adj[i] = new LinkedList();
        }
    }
    ...
}
There is an alternative implementation to represent per node with a list of adjacent nodes. 
class Node {
    public int val;
    public List<Node> neighbors;
    private boolean visited;     //visited mark for the vertex

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
    ...
}

6.0.1.1 Graph Traversal

6.0.1.1.1 Depth First Traversal

A depth first traversal without labeling the visited node usually ends up in exponential time complexity. There will be many subproblems being reevaluated (which were visited in past). Thus, the time complexity is \(O(2^{h+1} - 1)\) (as a full binary tree)

If your graph is implemented as an adjacency matrix, then, for each node, you have to traverse an entire row of length V in the matrix to discover all its outgoing edges. So, the complexity of DFS is \(O(|V| * |V|) = O(|V|^2)\).

If your graph is implemented using adjacency lc-lists, wherein each node maintains a lc-list of all its adjacent edges, then, for each node, you could discover all its neighbors by traversing its adjacency lc-list just once in linear time. For a directed graph, the sum of the sizes of the adjacency lc-lists of all the nodes is E (total number of edges). So, the complexity of DFS is O(V) + O(E) = O(V + E). For an undirected graph, each edge will appear twice. Once in the adjacency lc-list of either end of the edge. So, the overall complexity will be \(O(|V|) + O (2\cdot |E|) = O(|V + E|)\).

6.0.1.1.1.1 Implementation Steps

dfs 1.3.1

void helper(int node, boolean visited[]) {
    // Mark the current node as visited and print it
    visited[node] = true;

    // Recur for all the vertices adjacent to this vertex
    for(Integer adjNode: adj[node]) {
        if (!visited[adjNode]) {
            helper(adjNode, visited);
        }
    }
}

// The function to do DFS traversal. It uses recursive DFSUtil()
void dfs(int root) {
    // Mark all the vertices as not visited(set as
    // false by default in java)
    boolean visited[] = new boolean[numOfVertices];

    helper(root, visited);
}
6.0.1.1.2 Bread First Traversal

For every single vertex in the graph, we will end up looking at its neighboring nodes only once (directed graph) or twice (undirected graph). The time complexity for both a directed and undirected graph is the sum of the vertices and their edges as represented by the graph in its adjacency lc-list representation, or \(O(|V| + |E|)\)

The power of using breadth-first search to traverse through a graph is that it can easily tell us the shortest way to get from one node to another.

6.0.1.1.2.1 Implementation Steps

bfs 1.3.2

class Graph  {
    private int numOfVertices;   // No. of vertices
    private LinkedList<Integer> adj[]; //Adjacency Lists

    ...

    void traversal(Integer root)  {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[numOfVertices];

        // Create a queue for BFS
        Queue<Integer> queue = new LinkedList<Integer>();

        // Mark the current node as visited and enqueue it
        visited[root] = true;
        queue.offer(root);

        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            Integer node = queue.poll();

            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it
            // visited and enqueue it
            for(Integer adjNode : adj[node]) {
                if (!visited[adjNode]) {
                    visited[adjNode] = true;
                    queue.offer(adjNode);
                }
            }
        }
    }
}

6.0.1.2 Union-Find (Disjoint Set Union)

Union-Find is a data structure that tracks a collection of elements partitioned into disjoint (non-overlapping) sets. It supports two core operations efficiently:

  • find(x): Which group does element x belong to? Returns the root (representative) of x’s set.
  • union(x, y): Merge the groups containing x and y into one group.

Core Intuition:

Think of it as managing friend circles. Everyone starts alone. When two people become friends, their circles merge. To check if two people are in the same circle, trace each person back to their circle’s “leader” (root).

Initial:  [0] [1] [2] [3] [4]   ← 5 separate groups

union(0,1): [0,1] [2] [3] [4]
union(1,2): [0,1,2] [3] [4]
union(3,4): [0,1,2] [3,4]

find(0) == find(2)?  YES → same group
find(0) == find(3)?  NO  → different groups

Internal Representation:

Each element stores a parent pointer. The root of a tree is its own parent.

After union(0,1), union(1,2):

parent: [1, 2, 2, 3, 4]
         ↑  ↑  ↑
         0→1→2 (root)

Tree structure:
    2
    |
    1
    |
    0
6.0.1.2.1 Basic Implementation
class UnionFind {
    int[] parent;

    UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // each element is its own root
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            return find(parent[x]);  // recurse up to root
        }
        return x;
    }

    void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootA] = rootB;  // attach one root under the other
        }
    }
}

Problem: Without optimizations, find() can degrade to O(n) on a chain:

union(0,1), union(1,2), union(2,3), union(3,4)

parent: [1, 2, 3, 4, 4]

Tree (chain):
0 → 1 → 2 → 3 → 4

find(0) must traverse 4 hops. With n elements: O(n) per operation.

6.0.1.2.2 Optimization 1: Path Compression

During find(), make every node on the path point directly to the root. Flattens the tree for future queries.

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // path compression: point directly to root
    }
    return parent[x];
}

Before and after find(0) with path compression:

Before:                After:
0 → 1 → 2 → 3 → 4    0 → 4
                       1 → 4
                       2 → 4
                       3 → 4

All future find() calls from 0, 1, 2, 3 take O(1).

6.0.1.2.3 Optimization 2: Union by Rank

Always attach the shorter tree under the taller tree. Keeps trees balanced.

class UnionFind {
    int[] parent;
    int[] rank;  // approximate height of the subtree

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

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // path compression
        }
        return parent[x];
    }

    boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;  // already in same set

        // attach smaller rank tree under larger rank tree
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootB] < rank[rootA]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;  // only grows when ranks are equal
        }
        return true;
    }
}

Why return boolean from union? Returning false when roots are equal means the two elements were already connected — useful for cycle detection.

6.0.1.2.4 Combined Complexity

With both path compression and union by rank:

  • Time: O(\(\alpha\)(n)) per operation, where \(\alpha\) is the inverse Ackermann function — effectively O(1) for all practical inputs
  • Space: O(n) for parent and rank arrays
6.0.1.2.5 When to Use Union-Find
Problem Pattern Example
Group elements by shared property Accounts Merge
Detect cycles in undirected graph Graph Valid Tree
Count connected components Number of Connected Components
Check if two elements are in same group Friend Circles

Key signal in problem statement: “Two X belong together if they share Y” — this is almost always Union-Find.

See: Graph Valid Tree, Number of Connected Components, Accounts Merge for Union-Find implementations.

6.0.1.3 Graph Cycle Detection in Undirected Graph

In an undirected graph, a cycle exists if during traversal we encounter a visited node that is not the parent of the current node. Since edges are bidirectional, we must track the parent to avoid false positives.

6.0.1.3.1 Approach 1: DFS with Parent Tracking

Key Insight:

When traversing from node A to node B in an undirected graph, B will list A as a neighbor. Without parent tracking, the algorithm would incorrectly detect a cycle when seeing A from B. By tracking the parent (the node we came from), we can distinguish between: - Parent edge: The edge we just traversed (not a cycle) - Back edge: An edge to a visited node that’s not the parent (indicates a cycle)

Algorithm:

  1. Build adjacency list with edges in both directions
  2. For each unvisited node, start DFS
  3. In DFS, for each neighbor:
    • Skip if it’s the parent
    • If visited and not parent → cycle detected
    • Otherwise, recursively visit with current node as parent

Example:

For graph with cycle:

0 - 1 - 2
    |   |
    4 - 3

DFS from node 0: - Visit 0 → Visit 1 (parent: 0) - Check 0: skip (parent) - Visit 2 (parent: 1) - Check 1: skip (parent) - Visit 3 (parent: 2) - Check 2: skip (parent) - Visit 4 (parent: 3) - Check 3: skip (parent) - Check 1: visited and not parent → Cycle detected!

Time Complexity: O(V + E)

Java Implementation:

boolean hasCycle(List<List<Integer>> graph, int n) {
    boolean[] visited = new boolean[n];

    // Check all components
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, graph, visited)) {
                return true; // Cycle found
            }
        }
    }
    return false;
}

boolean dfs(int node, int parent, List<List<Integer>> graph, boolean[] visited) {
    visited[node] = true;

    for (int neighbor : graph.get(node)) {
        if (neighbor == parent) continue; // Skip parent

        if (visited[neighbor]) return true; // Cycle found

        if (dfs(neighbor, node, graph, visited)) {
            return true;
        }
    }
    return false;
}
6.0.1.3.2 Approach 2: Union-Find (Disjoint Set)

Key Insight:

Process edges one by one. For each edge connecting two nodes: - If they’re already in the same component → adding this edge creates a cycle - Otherwise, union them into one component

Algorithm:

  1. Initialize Union-Find with each node as its own parent
  2. For each edge [u, v]:
    • Find root of u and root of v
    • If same root → cycle detected
    • Otherwise, union the two sets

Example:

For edges [[0,1], [1,2], [2,3], [3,4], [4,1]]:

Process [0,1]: Union(0,1) ✓ Parent: [1,1,2,3,4]
Process [1,2]: Union(1,2) ✓ Parent: [1,2,2,3,4]
Process [2,3]: Union(2,3) ✓ Parent: [1,2,3,3,4]
Process [3,4]: Union(3,4) ✓ Parent: [1,2,3,4,4]
Process [4,1]: Find(4)=4, Find(1)=2
               Union(4,2) - wait, need to trace...
               Actually: Find(4)→3→2, Find(1)→2
               Same root! → Cycle detected!

Time Complexity: O(E · α(V)) ≈ O(E) where α is the inverse Ackermann function

Java Implementation:

boolean hasCycle(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);

    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return true; // Cycle detected
        }
    }
    return false;
}

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 rootA = find(a), rootB = find(b);
        if (rootA == rootB) return false; // Same set = cycle

        if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
        else if (rank[rootB] < rank[rootA]) parent[rootB] = rootA;
        else { parent[rootB] = rootA; rank[rootA]++; }
        return true;
    }
}

6.0.2 Directed Acyclic Graph

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles. This means: - All edges point in a direction (directed) - If you follow edges, you can never return to a node you’ve already visited - There exists at least one topological ordering of its vertices

DAGs are commonly used to represent dependencies: task scheduling, build systems, course prerequisites, etc.

6.0.2.1 Topological Sorting

Topological sorting is a linear ordering of vertices in a DAG such that for every directed edge \([u,v]\), vertex u comes before v in the ordering. This ordering respects all dependency constraints in the graph.

See: Course Schedule, Course Schedule II for topological sorting implementations (both DFS and BFS/Kahn’s algorithm).

6.0.2.1.1 Depth First Traversal

In DFS implementation of Topological Sort we focused on sink vertices, i.e, vertices with zero out-going edges, and then at last had to reverse the order in which we got the (which we did by using a stack, which is a Last In First Out data structure). A DAG has to have at least one sink vertex which is the vertex which has no outbound edges. In DFS we print the nodes as we see them, which means when we print a node, it has just been discovered but not yet processed, which means it is in the Visiting state. So DFS gives the order in which the nodes enter the Visiting state and not the Visited state. For topological sorting we need to have the order in which the nodes are completely processed, i.e, the order in which the nodes are marked as Visited. Because when a node is marked Visited then all of its child node have already been processed, so they would be towards the right of the child nodes in the topological sort, as it should be.

For example, in the given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’.

5 -> 0 <- 4
|         |
v         v
2 -> 3 -> 1

In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. The final sequence is [5, 4, 2, 3, 1, 0]

6.0.2.1.1.1 Implementation Steps

topological 1.3.3, dfs 1.3.1

void helper(Integer v, boolean[] visited, Stack stack) {
    visited[v] = true;

    // Recur for all the vertices adjacent to this
    // vertex
    Iterator<Integer> it = adj[v].iterator();
    while (it.hasNext()) {
        Integer adjNode = it.next();

        if (!visited[adjNode])  {
            helper(adjNode, visited, stack);
        }
    }

    // Push current vertex to stack which stores result
    stack.push(new Integer(v));
}

List<Integer> topologicalSort(Graph graph) {
    Stack<Integer> stack = new Stack<>();
    List<Integer> result = new ArrayList<>();

    // Call the recursive helper function to store
    // Topological Sort starting from all vertices
    // one by one
    for (int i = 0; i < numOfVertices; i++) {
        if (visited[i] == false)  {
            helper(i, visited, stack);
        }
    }

    //Now the stack contains the topological sorting of the graph
    for (Integer vertex : stack) {
        result.add(stack.pop());
    }

    return result
}
6.0.2.1.2 Bread First Traversal

In BFS implementation of the Topological sort we do the opposite: We look for for edges with no inbound edges (). And consequently in BFS implementation we don’t have to reverse the order in which we get the vertices, since we get the vertices in order of the topological ordering. We use First-In-First-Out data structure Queue in this implementation. We just search for the vertices with zero indegrees and put them in the queue till we have processed all the vertices of the graph. Polling vertices from the queue one by one give the topological sort of the graph. Lastly check if the result set does not contain all the vertices that means there is at least one cycle in the graph. That is because the indegree of those vertices participating in the loop could not be made 0 by decrementing.

in-degree, out-degree
in-degree, out-degree
6.0.2.1.2.1 Implementation Steps

topological 1.3.3, bfs 1.3.2

public List topological_sort_bfs(int[][] graph) {
    List<Integer> result = new ArrayList<>();
    int[] indegree = new int[numOfVertices];

    // compute the indegree of all the vertices in the graph
    // For edge (0,1), indegree[1]++;
    for (int i = 0; i < numOfVertices; i++) {
        for(Integer vertex : adj[i]) {
            indegree[vertex]++;
        }
    }

    Queue<Integer> queue = new LinkedList<>();

    // initialize the queue with all the vertices with no inbound edges
    for (int i = 0; i < numOfVertices; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    while (!queue.isEmpty()) {
        Integer vertex = queue.poll();
        result.add(vertex);

        // now disconnect vertex from the graph
        // and decrease the indegree of the other end of the edge by 1
        for (Integer adjVertex : adj[vertex]) {
            indegree[adjVertex]--;
            if (indegree[adjVertex] == 0) {
                queue.offer(adjVertex);
            }
        }
    }

    // check if the graph had a cycle / loop
    if (result.size() != numOfVertices) {
        return new ArrayList<Integer>();
    }
    return result;
}

6.0.2.2 Graph Cycle Detection in DAG

In a directed graph, cycle detection is more complex because we must distinguish between: - Cross edges: Edges to already-visited nodes in different branches (not a cycle) - Back edges: Edges to nodes currently in the recursion stack (indicates a cycle)

6.0.2.2.1 Approach 1: DFS with Three-State Coloring

Key Insight:

Use three states to track node status: - White (0): Unvisited node - Gray (1): Currently in recursion stack (visiting) - Black (2): Fully processed (visited)

If we encounter a gray node during DFS, we’ve found a back edge → cycle detected.

Algorithm:

  1. Initialize all nodes as white (0)
  2. For each white node, start DFS
  3. In DFS:
    • If node is gray → back edge → cycle detected
    • If node is black → already processed → return safe
    • Mark node as gray (in current path)
    • Recursively visit all neighbors
    • Mark node as black (finished processing)

Example:

For graph with cycle:

0 → 1 → 2
↑       ↓
└───────3

DFS from node 0:

State: [W, W, W, W]

Visit 0: mark gray
State: [G, W, W, W]
  Visit 1: mark gray
  State: [G, G, W, W]
    Visit 2: mark gray
    State: [G, G, G, W]
      Visit 3: mark gray
      State: [G, G, G, G]
        Check 0: GRAY! → Cycle detected!

Time Complexity: O(V + E)

Java Implementation:

boolean hasCycle(List<List<Integer>> graph, int n) {
    int[] state = new int[n]; // 0: white, 1: gray, 2: black

    for (int i = 0; i < n; i++) {
        if (state[i] == 0 && dfs(i, graph, state)) {
            return true; // Cycle found
        }
    }
    return false;
}

boolean dfs(int node, List<List<Integer>> graph, int[] state) {
    if (state[node] == 1) return true;  // Gray = back edge = cycle
    if (state[node] == 2) return false; // Black = already safe

    state[node] = 1; // Mark as gray (visiting)

    for (int neighbor : graph.get(node)) {
        if (dfs(neighbor, graph, state)) {
            return true;
        }
    }

    state[node] = 2; // Mark as black (visited)
    return false;
}
6.0.2.2.2 Approach 2: DFS with Recursion Stack

Key Insight:

Use two sets instead of three states: - visited: Nodes that are fully processed - recursionStack: Nodes currently in the recursion path

If we encounter a node in recursionStack, we’ve found a cycle.

Algorithm:

  1. Create visited and recursionStack sets
  2. For each unvisited node, start DFS
  3. In DFS:
    • If node in recursionStack → cycle detected
    • If node in visited → already safe
    • Add node to recursionStack
    • Recursively visit all neighbors
    • Remove from recursionStack, add to visited

Example:

Same graph as above:

Visit 0: recursionStack={0}
  Visit 1: recursionStack={0,1}
    Visit 2: recursionStack={0,1,2}
      Visit 3: recursionStack={0,1,2,3}
        Check 0: IN RECURSION STACK! → Cycle detected!

Time Complexity: O(V + E)

Java Implementation:

boolean hasCycle(List<List<Integer>> graph, int n) {
    Set<Integer> visited = new HashSet<>();
    Set<Integer> recursionStack = new HashSet<>();

    for (int i = 0; i < n; i++) {
        if (!visited.contains(i) && dfs(i, graph, visited, recursionStack)) {
            return true;
        }
    }
    return false;
}

boolean dfs(int node, List<List<Integer>> graph, Set<Integer> visited, Set<Integer> recursionStack) {
    if (recursionStack.contains(node)) return true;  // Cycle found
    if (visited.contains(node)) return false;        // Already safe

    recursionStack.add(node); // Add to current path

    for (int neighbor : graph.get(node)) {
        if (dfs(neighbor, graph, visited, recursionStack)) {
            return true;
        }
    }

    recursionStack.remove(node); // Remove from current path
    visited.add(node);           // Mark as fully processed
    return false;
}
6.0.2.2.3 Approach 3: Kahn’s Algorithm (BFS Topological Sort)

Key Insight:

Use BFS with indegree tracking. In a DAG, we can process all nodes in topological order. If we can’t process all nodes, a cycle exists (nodes in a cycle never reach indegree 0).

Algorithm:

  1. Calculate indegree for all nodes
  2. Enqueue all zero-indegree nodes
  3. While queue not empty:
    • Dequeue node and increment processed count
    • Decrease indegree of neighbors
    • Enqueue neighbors that reach zero indegree
  4. If processed count \(\\ne\) total nodes → cycle exists

Example:

For graph with cycle:

0 → 1 → 2
↑       ↓
└───────3

Indegrees: [1, 1, 1, 1] (all nodes have indegree 1)

No zero-indegree nodes to start! Queue remains empty → processed = 0 → Cycle detected!

For acyclic graph:

0 → 1 → 2
    ↓
    3

Indegrees: [0, 1, 1, 1] - Start: queue = [0] - Process 0: queue = [1], processed = 1 - Process 1: queue = [2, 3], processed = 2 - Process 2: queue = [3], processed = 3 - Process 3: queue = [], processed = 4 - All nodes processed → No cycle!

Time Complexity: O(V + E)

Java Implementation:

boolean hasCycle(List<List<Integer>> graph, int n) {
    int[] indegree = new int[n];

    // Calculate indegrees
    for (int i = 0; i < n; i++) {
        for (int neighbor : graph.get(i)) {
            indegree[neighbor]++;
        }
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    int processed = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        processed++;

        for (int neighbor : graph.get(node)) {
            if (--indegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }

    return processed != n; // Cycle exists if not all nodes processed
}

Comparison of DAG Cycle Detection Approaches:

Approach State Tracking Cycle Detection Space Best For
3-State DFS int[] state Gray node found O(V) Compact state representation
RecStack DFS Two Sets Node in recursion stack O(V) Clear separation of states
Kahn’s BFS Indegree array Not all nodes processed O(V+E) Need topological sort anyway

All three approaches have O(V + E) time complexity and are equally correct. Choose based on: - 3-State DFS: Most memory-efficient (single array) - RecStack DFS: Most intuitive for understanding recursion paths - Kahn’s BFS: Produces topological order as a bonus

6.0.3 Weighted Graphs

A weighted graph is a graph where each edge has an associated numerical value (weight/cost). Weights can represent: - Distance between cities - Cost of travel - Time required for a task - Network bandwidth or latency

Weighted graphs can be either directed or undirected. Most weighted graph algorithms work on both types (an undirected edge is simply two directed edges with the same weight in opposite directions).

Representation:

Adjacency List with weights:
| 0 | -- (1,4) -- (2,1)
| 1 | -- (0,4) -- (2,2) -- (3,5)
| 2 | -- (0,1) -- (1,2) -- (3,8)
| 3 | -- (1,5) -- (2,8)

Adjacency Matrix with weights:
     0   1   2   3
0 [  0   4   1   ∞ ]
1 [  4   0   2   5 ]
2 [  1   2   0   8 ]
3 [  ∞   5   8   0 ]

Common Java Representation:

// Edge class for weighted graphs
class Edge {
    int to;      // destination vertex
    int weight;  // edge weight

    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

// Graph as adjacency list
List<Edge>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
    graph[i] = new ArrayList<>();
}

// Add directed edge from u to v with weight
graph[u].add(new Edge(v, weight));

// For undirected graphs, add both directions:
graph[u].add(new Edge(v, weight));
graph[v].add(new Edge(u, weight));

6.0.3.1 Shortest Path Algorithms

Shortest path algorithms find the path with minimum total weight between vertices. Unlike unweighted BFS (which finds shortest path by edge count), weighted graphs require specialized algorithms.

6.0.3.1.1 Dijkstra’s Algorithm

Purpose: Find shortest path from a single source to all other vertices in graphs with non-negative edge weights.

Key Insight:

Greedily select the unvisited node with the smallest known distance, then update distances to its neighbors. This works because: - We always process nodes in order of increasing distance from source - Once a node is processed, we’ve found its shortest path (no negative weights means no future path can be shorter)

Algorithm:

  1. Initialize distances: dist[source] = 0, all others = \(\infty\)
  2. Use a min-heap (priority queue) to track (distance, node) pairs
  3. Start with source node in the heap
  4. While heap not empty:
    • Extract node with minimum distance
    • If already visited, skip (optimization)
    • Mark as visited
    • For each neighbor:
      • Calculate new distance: dist[node] + edge_weight
      • If new distance < current distance to neighbor:
        • Update distance
        • Add neighbor to heap

Example:

Find shortest paths from source vertex 0:

Graph (edge weights shown in parentheses):

        1 ------(5)------ 3
       /|                 |
     (4)|                 |
     /  |                 |
    0   |(2)             (8)
     \  |                 |
     (1)|                 |
       \|                 |
        2 ------(8)------ 4

Edges with weights:
0→1 (4)    1→2 (2)    2→4 (8)
0→2 (1)    1→3 (5)    3→4 (8)

Step-by-step execution:

Initial: dist = [0, ∞, ∞, ∞, ∞]
         heap = [(0, vertex:0)]

Extract (0, vertex:0):
  - Visit neighbors: 1 with weight (4), 2 with weight (1)
  - Update: dist[1] = 0+4 = 4, dist[2] = 0+1 = 1
  - dist = [0, 4, 1, ∞, ∞]
  - heap = [(1, vertex:2), (4, vertex:1)]

Extract (1, vertex:2):
  - Visit neighbors: 1 with weight (2), 4 with weight (8)
  - Update: dist[1] = min(4, 1+2) = 3, dist[4] = 1+8 = 9
  - dist = [0, 3, 1, ∞, 9]
  - heap = [(3, vertex:1), (4, vertex:1), (9, vertex:4)]

Extract (3, vertex:1):
  - Visit neighbors: 3 with weight (5)
  - Update: dist[3] = 3+5 = 8
  - dist = [0, 3, 1, 8, 9]
  - heap = [(4, vertex:1), (8, vertex:3), (9, vertex:4)]

Extract (4, vertex:1):
  - Already processed (visited), skip

Extract (8, vertex:3):
  - Visit neighbors: 4 with weight (8)
  - Update: dist[4] = min(9, 8+8) = 9 (no change)
  - dist = [0, 3, 1, 8, 9]
  - heap = [(9, vertex:4)]

Extract (9, vertex:4):
  - No unvisited neighbors
  - All vertices processed

Final shortest distances from vertex 0:
  To vertex 0: 0
  To vertex 1: 3 (path: 0→2→1)
  To vertex 2: 1 (path: 0→2)
  To vertex 3: 8 (path: 0→2→1→3)
  To vertex 4: 9 (path: 0→2→4)

Time Complexity: - With binary heap: \(O((V + E) \log V)\) - With Fibonacci heap: \(O(E + V \log V)\) (theoretical, rarely used in practice)

Space Complexity: \(O(V + E)\) for graph storage + \(O(V)\) for distance array and heap

Java Implementation:

int[] dijkstra(List<Edge>[] graph, int source) {
    int n = graph.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    // Min-heap: (distance, node)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, source});

    boolean[] visited = new boolean[n];

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0];
        int node = curr[1];

        if (visited[node]) continue; // Skip if already processed
        visited[node] = true;

        for (Edge edge : graph[node]) {
            int newDist = dist[node] + edge.weight;
            if (newDist < dist[edge.to]) {
                dist[edge.to] = newDist;
                pq.offer(new int[]{newDist, edge.to});
            }
        }
    }

    return dist;
}

When to Use: - Non-negative edge weights only - Single-source shortest path - Need actual shortest distances (not just path existence)

Limitations: - Cannot handle negative weights (greedy approach breaks down) - More complex than BFS for unweighted graphs

6.0.3.1.2 Bellman-Ford Algorithm

Purpose: Find shortest path from a single source to all other vertices, works with negative edge weights, and can detect negative cycles.

Key Insight:

Relax all edges repeatedly. After \(V-1\) iterations, all shortest paths are found (since any simple path has at most \(V-1\) edges). A \(V^{th}\) iteration that still updates distances indicates a negative cycle.

Algorithm:

  1. Initialize distances: dist[source] = 0, all others = \(\infty\)
  2. Repeat \(V-1\) times:
    • For each edge \((u, v, weight)\):
      • If dist[u] + weight < dist[v]:
        • Update dist[v] = dist[u] + weight
  3. Check for negative cycles:
    • For each edge \((u, v, weight)\):
      • If dist[u] + weight < dist[v]: negative cycle detected

Example:

Find shortest paths from node 0 with negative edge:

Graph:
    1 --5-- 3
   /|
  4 |
 /  -2
0   |
 \  1
  1 |
   \|
    2

Iteration 0: dist = [0, ∞, ∞, ∞]
Iteration 1: dist = [0, 4, 1, ∞]
Iteration 2: dist = [0, 2, 1, 7]  (updated: 1←2 via edge 2→1 with -2)
Iteration 3: dist = [0, 2, 1, 7]  (no changes)

Time Complexity: \(O(V \cdot E)\) - much slower than Dijkstra’s

Space Complexity: \(O(V)\) for distance array

Java Implementation:

int[] bellmanFord(int n, int[][] edges, int source) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    // Relax all edges V-1 times
    for (int i = 0; i < n - 1; i++) {
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];

            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // Check for negative cycles
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
            throw new IllegalArgumentException("Graph contains negative cycle");
        }
    }

    return dist;
}

When to Use: - Graph has negative edge weights - Need to detect negative cycles - Graph is small (due to slower performance)

Comparison with Dijkstra’s:

Feature Dijkstra’s Bellman-Ford
Negative weights ❌ No ✅ Yes
Negative cycle detection ❌ No ✅ Yes
Time complexity \(O((V+E) \log V)\) \(O(V \cdot E)\)
Implementation Priority queue Simple nested loops
Best for Dense graphs, non-negative weights Negative weights, small graphs
6.0.3.1.3 Floyd-Warshall Algorithm

Purpose: Find shortest paths between all pairs of vertices. Works with negative weights but not negative cycles.

Key Insight:

Use dynamic programming with intermediate vertices. For each pair of vertices \((i, j)\), consider whether going through vertex \(k\) provides a shorter path than the direct path.

Algorithm:

  1. Initialize distance matrix:
    • dist[i][j] = weight if edge exists
    • dist[i][i] = 0 for all vertices
    • dist[i][j] = ∞ otherwise
  2. For each intermediate vertex \(k\) from 0 to \(V-1\):
    • For each source vertex \(i\):
      • For each destination vertex \(j\):
        • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Example:

Graph:
0 --1--> 2
|        ^
3        |
|        2
v        |
1 -------+

Initial matrix:
     0   1   2
0 [  0   3   1 ]
1 [  ∞   0   2 ]
2 [  ∞   ∞   0 ]

k=0: Consider paths through vertex 0
     0   1   2
0 [  0   3   1 ]
1 [  ∞   0   2 ]
2 [  ∞   ∞   0 ]

k=1: Consider paths through vertex 1
     0   1   2
0 [  0   3   1 ]
1 [  ∞   0   2 ]
2 [  ∞   ∞   0 ]

k=2: Consider paths through vertex 2
     0   1   2
0 [  0   3   1 ]
1 [  ∞   0   2 ]
2 [  ∞   ∞   0 ]

Final: All-pairs shortest distances

Time Complexity: \(O(V^3)\) - three nested loops

Space Complexity: \(O(V^2)\) for distance matrix

Java Implementation:

int[][] floydWarshall(int n, int[][] edges) {
    int[][] dist = new int[n][n];

    // Initialize
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // Avoid overflow
        dist[i][i] = 0;
    }

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];
        dist[u][v] = weight;
    }

    // Floyd-Warshall
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    return dist;
}

When to Use: - Need shortest paths between all pairs of vertices - Graph is small (\(V \le 400\) typically) - Simple implementation needed

Comparison of Shortest Path Algorithms:

Algorithm Use Case Negative Weights Time Space
BFS Unweighted, single-source N/A \(O(V+E)\) \(O(V)\)
Dijkstra’s Weighted, single-source ❌ No \(O((V+E) \log V)\) \(O(V)\)
Bellman-Ford Single-source, negative weights ✅ Yes \(O(V \cdot E)\) \(O(V)\)
Floyd-Warshall All-pairs ✅ Yes (no cycles) \(O(V^3)\) \(O(V^2)\)

6.0.3.2 Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of edges that: 1. Connects all vertices (spanning tree) 2. Has no cycles (tree property) 3. Has minimum total edge weight

Properties: - An MST has exactly \(V - 1\) edges - Removing any edge disconnects the tree - Adding any edge creates a cycle - MSTs are not unique if edges have equal weights

Applications: - Network design (minimize cable length) - Clustering algorithms - Approximation for Traveling Salesman Problem

6.0.3.2.1 Prim’s Algorithm

Purpose: Build MST by greedily adding the minimum weight edge that connects a visited vertex to an unvisited vertex.

Key Insight:

Start from any vertex and grow the tree by repeatedly adding the cheapest edge that expands the tree to a new vertex. Similar to Dijkstra’s but focuses on edge weights instead of path distances.

Algorithm:

  1. Start with arbitrary vertex, mark as visited
  2. Use min-heap to track edges from visited vertices
  3. While heap not empty and not all vertices visited:
    • Extract minimum weight edge
    • If destination already visited, skip
    • Add edge to MST
    • Mark destination as visited
    • Add all edges from destination to heap

Example:

Graph:
    1
   /|\
  4 2 5
 /  |  \
0   |   3
 \  1   |
  1 |   8
   \|   |
    2---4

Step-by-step:
Start: vertex 0, MST = []
Heap: [(1,0→2), (4,0→1)]

Pick (1,0→2): MST = [(0,2,1)], visited = {0,2}
Heap: [(1,2→1), (4,0→1), (8,2→4)]

Pick (1,2→1): MST = [(0,2,1), (2,1,1)], visited = {0,1,2}
Heap: [(2,1→2), (4,0→1), (5,1→3), (8,2→4)]

Pick (2,1→2): Skip (2 already visited)
Heap: [(4,0→1), (5,1→3), (8,2→4)]

Pick (4,0→1): Skip (1 already visited)
Heap: [(5,1→3), (8,2→4)]

Pick (5,1→3): MST = [(0,2,1), (2,1,1), (1,3,5)], visited = {0,1,2,3}
Heap: [(8,2→4), (8,3→4)]

Pick (8,2→4): MST = [(0,2,1), (2,1,1), (1,3,5), (2,4,8)]

Total MST weight: 1 + 1 + 5 + 8 = 15

Time Complexity: \(O((V + E) \log V)\) with binary heap

Space Complexity: \(O(V + E)\)

Java Implementation:

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

int primMST(List<Edge>[] graph) {
    int n = graph.length;
    boolean[] visited = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // (weight, to)

    int mstWeight = 0;
    int edgesUsed = 0;

    // Start from vertex 0
    visited[0] = true;
    for (Edge e : graph[0]) {
        pq.offer(new int[]{e.weight, e.to});
    }

    while (!pq.isEmpty() && edgesUsed < n - 1) {
        int[] curr = pq.poll();
        int weight = curr[0];
        int to = curr[1];

        if (visited[to]) continue; // Skip if already in MST

        visited[to] = true;
        mstWeight += weight;
        edgesUsed++;

        for (Edge e : graph[to]) {
            if (!visited[e.to]) {
                pq.offer(new int[]{e.weight, e.to});
            }
        }
    }

    return edgesUsed == n - 1 ? mstWeight : -1; // -1 if graph not connected
}
6.0.3.2.2 Kruskal’s Algorithm

Purpose: Build MST by sorting all edges by weight and greedily adding edges that don’t create cycles.

Key Insight:

Process edges in ascending weight order. Use Union-Find to efficiently detect if adding an edge would create a cycle. If not, add it to the MST.

Algorithm:

  1. Sort all edges by weight (ascending)
  2. Initialize Union-Find with each vertex as its own set
  3. For each edge \((u, v, weight)\) in sorted order:
    • If \(u\) and \(v\) are in different sets (no cycle):
      • Add edge to MST
      • Union the sets
    • Stop when MST has \(V - 1\) edges

Example:

Graph edges (sorted by weight):
(0,2,1), (1,2,1), (0,1,4), (1,3,5), (2,4,8), (3,4,8)

Process (0,2,1): Union(0,2) ✓ MST = [(0,2,1)]
Process (1,2,1): Union(1,2) ✓ MST = [(0,2,1), (1,2,1)]
Process (0,1,4): Skip (0,1 already connected via 2)
Process (1,3,5): Union(1,3) ✓ MST = [(0,2,1), (1,2,1), (1,3,5)]
Process (2,4,8): Union(2,4) ✓ MST = [(0,2,1), (1,2,1), (1,3,5), (2,4,8)]

Total MST weight: 1 + 1 + 5 + 8 = 15

Time Complexity: \(O(E \log E)\) for sorting + \(O(E \cdot \alpha(V))\) for Union-Find \(\approx O(E \log E)\)

Space Complexity: \(O(V)\) for Union-Find

Java Implementation:

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 rootA = find(a), rootB = find(b);
        if (rootA == rootB) return false;

        if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
        else if (rank[rootB] < rank[rootA]) parent[rootB] = rootA;
        else { parent[rootB] = rootA; rank[rootA]++; }
        return true;
    }
}

int kruskalMST(int n, int[][] edges) {
    // Sort edges by weight
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);

    UnionFind uf = new UnionFind(n);
    int mstWeight = 0;
    int edgesUsed = 0;

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        if (uf.union(u, v)) {
            mstWeight += weight;
            edgesUsed++;
            if (edgesUsed == n - 1) break; // MST complete
        }
    }

    return edgesUsed == n - 1 ? mstWeight : -1; // -1 if graph not connected
}

Prim’s vs Kruskal’s:

Feature Prim’s Kruskal’s
Approach Grow tree from vertex Add edges in weight order
Data structure Priority queue Union-Find
Time complexity \(O((V+E) \log V)\) \(O(E \log E)\)
Best for Dense graphs (\(E \approx V^2\)) Sparse graphs (\(E \approx V\))
Edge sorting Not required Required
Parallelization Harder Easier

When to Use: - Prim’s: Dense graphs, need to build tree incrementally - Kruskal’s: Sparse graphs, already have sorted edges, easier to implement