Graph Algorithms

Kruskal's Algorithm

Kruskal’s Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) of a connected, weighted, undirected graph. It was developed by Joseph Kruskal in 1956.

Given a graph with weighted edges where all vertices are connected, it finds a subset of edges that:

• connects all vertices
• has no cycles
• Has the minimum possible total edge weight

This subset is called a Minimum Spanning Tree.

Algorithm Procedure

• Sort all edges in increasing order of weight.
• Start with an empty graph (no edges).
• Go through the sorted edges one by one:
• If adding the edge does not create a cycle, add it.
• If it does create a cycle → skip it.
• Stop when you have V − 1 edges (where V = number of vertices).

#import "Basic";

Edge :: struct {
    src    : int;
    dst    : int;
    weight : int;
}

// Union-Find (Disjoint Set Union) data structure.
// 'parent' and 'rank' are parallel dynamic arrays indexed by node ID.
UnionFind :: struct {
    parent : [..] int;
    rank   : [..] int;
}

init_union_find :: (uf: *UnionFind, n: int) {
    for i : 0..n-1 {
        array_add(*uf.parent, i);  // each node is its own parent
        array_add(*uf.rank, 0);
    }
}

// Walk up the parent chain until we reach the root.
// Path compression: flatten the tree so every visited node
// points directly to the root on future calls.
find :: (uf: *UnionFind, x: int) -> int {
    if uf.parent[x] != x {
        uf.parent[x] = find(uf, uf.parent[x]);
    }
    return uf.parent[x];
}

// Union by rank: attach the smaller tree under the larger tree's root.
// Returns false if both nodes share the same root (would form a cycle).
union_find :: (uf: *UnionFind, a: int, b: int) -> bool {
    root_a := find(uf, a);
    root_b := find(uf, b);

    if root_a == root_b return false;  // already connected, skip

    if uf.rank[root_a] < uf.rank[root_b] {
        uf.parent[root_a] = root_b;
    } else if uf.rank[root_a] > uf.rank[root_b] {
        uf.parent[root_b] = root_a;
    } else {
        uf.parent[root_b] = root_a;
        uf.rank[root_a] += 1;
    }
    return true;
}

bubble_sort :: (array:[] $T, $comparison: (T, T) -> bool) {

    sorted := false;

    while !sorted {
        i := 0;
        j := 1;
        sorted = true;
        while j < array.count {
            if comparison(array[j], array[i]) {
                array[j], array[i] = array[i], array[j];
                sorted = false;
            }
            i += 1;
            j += 1;
        }
    }
}

kruskal :: (num_nodes: int, edges: [] Edge) -> [..] Edge {
    // Sort all edges from cheapest to most expensive.
    bubble_sort(edges, (a: Edge, b: Edge) -> bool {
        return a.weight < b.weight;
    });

    uf: UnionFind;
    init_union_find(*uf, num_nodes);

    mst: [..] Edge;

    for edge : edges {
        // An MST for N nodes needs exactly N-1 edges.
        if mst.count == num_nodes - 1  break;

        // Only add the edge if its endpoints are in different components.
        // union() returns false when they are already connected (cycle).
        if union_find(*uf, edge.src, edge.dst) {
            array_add(*mst, edge);
        }
    }

    return mst;
}

main :: () {
    // Graph with 5 nodes (0..4) and 7 edges:
    //
    //   0 --1-- 1
    //   |  \ /  |
    //   4   X   2
    //   |  / \  |
    //   3 --9-- 4
    //
    edges := Edge.[
        .{0, 1, 1},
        .{0, 3, 4},
        .{1, 2, 2},
        .{1, 3, 5},
        .{1, 4, 8},
        .{2, 4, 3},
        .{3, 4, 9},
    ];

    mst := kruskal(5, edges);

    total_weight := 0;
    print("Minimum Spanning Tree edges:\n");
    for edge : mst {
        print("  % -- % : weight %\n", edge.src, edge.dst, edge.weight);
        total_weight += edge.weight;
    }
    print("Total MST weight: %\n", total_weight);
}

Edge Representation

Each Edge is a flat struct holding src, dst, and weight. Because Jai structs are plain value types (no hidden overhead), the array of edges is a contiguous block of memory — cache-friendly for the sort that follows.

Union-Find (Disjoint Set Union)

The algorithm needs to answer one question efficiently: "Are these two nodes already connected?" Union-Find answers this in near-O(1) time with two optimizations:

• Path Compression (find): When traversing the parent chain to find the root, every node along the path is rewired to point directly at the root. Future lookups on those nodes become a single-step O(1) dereference.

• Union by Rank (union): Each set tracks a rank (an approximate height of its tree). When merging two sets, the shallower tree is attached under the deeper tree's root, keeping the overall tree height from ballooning.

Together these give an amortized inverse-Ackermann time complexity, which is effectively constant for any practical input size.

Sorting

Edges are sorted by weight ascending using a polymorphic bubble_sort.

Greedy Selection Loop

The main loop iterates through the sorted edge list and for each edge calls union(). If the two endpoints were already in the same connected component, union() returns false and the edge is skipped — adding it would create a cycle. If they were in different components, union() merges the components and returns true, and the edge is appended to the MST. The loop terminates early once exactly N - 1 edges have been collected, which is the exact count a spanning tree on N nodes requires.

Expected Output for the Sample Graph

Minimum Spanning Tree edges:
  0 -- 1 : weight 1
  1 -- 2 : weight 2
  2 -- 4 : weight 3
  0 -- 3 : weight 4
Total MST weight: 10

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a weighted graph where all edge weights are non-negative. It works by maintaining a priority queue of nodes to visit, always processing the node with the smallest known distance first. The time complexity is O((V + E) log V) with a binary heap priority queue, where V is the number of vertices and E is the number of edges.

Graph Representation

We represent the graph as an adjacency list: each node stores a dynamic array of its neighbors and the weights of the edges connecting them. This is memory-efficient for sparse graphs and fast for iterating neighbors.

// An edge connects 'to' with a given 'weight'
Edge :: struct {
    to:     int;
    weight: int;
}

// A node holds all its outgoing edges
Node :: struct {
    edges: [..] Edge;
}

// The graph is just an array of nodes
Graph :: struct {
    nodes: [..] Node;
}

// Create a graph with 'num_nodes' nodes
graph_create :: (num_nodes: int) -> Graph {
    g: Graph;
    for 0..num_nodes - 1 {
        node: Node;
        array_add(*g.nodes, node);
    }
    return g;
}

// Add a directed edge from 'from' to 'to' with the given weight
graph_add_edge :: (g: *Graph, from: int, to: int, weight: int) {
    edge := Edge.{to = to, weight = weight};
    array_add(*g.nodes[from].edges, edge);
}

Priority Queue

Dijkstra's algorithm needs a priority queue to efficiently retrieve the unvisited node with the smallest tentative distance. We implement a simple min-heap using a dynamic array.

// An entry in the priority queue: which node and its current best distance
PQ_Entry :: struct {
    node:     int;
    distance: int;
}

// Priority queue (min-heap) — smallest distance at index 0
PQ :: struct {
    data: [..] PQ_Entry;
}

// Swap two entries
pq_swap :: (pq: *PQ, a: int, b: int) {
    pq.data[a], pq.data[b] = pq.data[b], pq.data[a];
}

// Sift an entry up to restore heap order
pq_sift_up :: (pq: *PQ, i: int) {
    while i > 0 {
        parent := (i - 1) / 2;
        if pq.data[i].distance < pq.data[parent].distance {
            pq_swap(pq, i, parent);
            i = parent;
        } else {
            break;
        }
    }
}

// Sift an entry down to restore heap order
pq_sift_down :: (pq: *PQ, i: int) {
    n := pq.data.count;
    while true {
        smallest := i;
        left  := 2 * i + 1;
        right := 2 * i + 2;

        if left < n && pq.data[left].distance < pq.data[smallest].distance {
            smallest = left;
        }
        if right < n && pq.data[right].distance < pq.data[smallest].distance {
            smallest = right;
        }
        if smallest == i  break;

        pq_swap(pq, i, smallest);
        i = smallest;
    }
}

// Push a new entry onto the heap
pq_push :: (pq: *PQ, node: int, dist: int) {
    array_add(*pq.data, .{node = node, distance = dist});
    pq_sift_up(pq, pq.data.count - 1);
}

// Pop the minimum-distance entry off the heap
pq_pop :: (pq: *PQ) -> PQ_Entry {
    top := pq.data[0];
    last := pq.data.count - 1;
    pq.data[0] = pq.data[last];
    pq.data.count -= 1;  // shrink without freeing memory
    if pq.data.count > 0  pq_sift_down(pq, 0);
    return top;
}

Dijkstra Procedure Implementation

This function returns the array of shortest distances from 'start' to every node. Unreachable nodes have distance S64_MAX (treated as infinity).

dijkstra :: (g: *Graph, start: int) -> [] int {

    INF :: 0x7FFF_FFFF;   // large sentinel value for "infinity"
    n := g.nodes.count;

    // dist[i] = best known distance from start to node i
    dist := NewArray(n, int);
    for i : 0..n - 1  dist[i] = INF;
    dist[start] = 0;

    // visited[i] = true once node i's shortest distance is finalised
    visited := NewArray(n, bool);
    for i : 0..n - 1  visited[i] = false;

    // Initialise the priority queue with the starting node
    pq: PQ;
    pq_push(*pq, start, 0);

    while pq.data.count > 0 {
        // Always process the node with the smallest current distance
        entry := pq_pop(*pq);
        u := entry.node;

        // Skip if we already found the best path to u
        if visited[u]  continue;
        visited[u] = true;

        // Relax all outgoing edges from u
        for edge : g.nodes[u].edges {
            v := edge.to;
            new_dist := dist[u] + edge.weight;

            if new_dist < dist[v] {
                dist[v] = new_dist;
                pq_push(*pq, v, new_dist);
            }
        }
    }

    return dist;
}

Example Usage

Below is a complete main() that builds a small weighted graph, runs Dijkstra from node 0, and prints the results.

main :: () {

    //  Graph layout:
    //
    //       2       3
    //  0 -------> 1 -------> 3
    //  |          |          ^
    //  |  6       | 1        | 1
    //  +------->  2 ---------+

    g := graph_create(4);  // 4 nodes: 0, 1, 2, 3

    graph_add_edge(*g, 0, 1, 2);  // 0 -> 1, cost 2
    graph_add_edge(*g, 0, 2, 6);  // 0 -> 2, cost 6
    graph_add_edge(*g, 1, 2, 1);  // 1 -> 2, cost 1
    graph_add_edge(*g, 1, 3, 3);  // 1 -> 3, cost 3
    graph_add_edge(*g, 2, 3, 1);  // 2 -> 3, cost 1

    dist := dijkstra(*g, 0);

    print("Shortest distances from node 0:\n");
    for i : 0..dist.count - 1 {
        print("  Node % -> %\n", i, dist[i]);
    }
    // Expected output:
    //   Node 0 -> 0
    //   Node 1 -> 2
    //   Node 2 -> 3   (via 0->1->2, cost 2+1=3, not 0->2 cost 6)
    //   Node 3 -> 4   (via 0->1->2->3, cost 2+1+1=4)
}

Let's trace through what happens when we call dijkstra(*g, 0):

• Start: dist = [0, INF, INF, INF]. Push (node=0, dist=0) onto the heap.
• Pop (0, 0). Mark node 0 visited. Relax edges: dist[1] = 2, dist[2] = 6. Push both.
• Pop (1, 2). Mark node 1 visited. Relax: dist[2] = min(6, 2+1) = 3. dist[3] = 5. Push updated entries.
• Pop (2, 3). Mark node 2 visited. Relax: dist[3] = min(5, 3+1) = 4. Push (3, 4).
• Pop (3, 4). Mark node 3 visited. No outgoing edges. Done.
• Final distances: [0, 2, 3, 4].

Graph Coloring Algorithm

Graph coloring assigns colors to each vertex in a graph such that no two adjacent vertices share the same color. This has practical applications in compiler register allocation, scheduling problems, and map coloring. This implementation uses a greedy graph coloring algorithm with an adjacency list represented as a dynamic array of dynamic arrays. Each vertex has a list of neighbors it is connected to.

#import "Basic";

// The graph is represented as an adjacency list.
// adjacency_list[i] is a dynamic array of ints listing
// all vertices that vertex i is connected to.
Graph :: struct {
    num_vertices    : int;
    adjacency_list  : [..] [..] int;  // array of dynamic arrays
}

// Add an undirected edge between vertex u and vertex v.
add_edge :: (g: *Graph, u: int, v: int) {
    array_add(*g.adjacency_list[u], v);
    array_add(*g.adjacency_list[v], u);
}

// Initialize a graph with a given number of vertices.
make_graph :: (num_vertices: int) -> Graph {
    g : Graph;
    g.num_vertices = num_vertices;

    // Reserve one neighbor-list slot per vertex
    for i: 0..num_vertices - 1 {
        neighbor_list : [..] int;
        array_add(*g.adjacency_list, neighbor_list);
    }
    return g;
}

// Greedy graph coloring algorithm.
// Returns a dynamic array where result[i] is the color assigned to vertex i.
// Colors are integers starting from 0.
graph_color :: (g: *Graph) -> [..] int {
    num_vertices := g.num_vertices;

    // Initialize every vertex's color to -1 (uncolored)
    colors : [..] int;
    for i: 0..num_vertices - 1 {
        array_add(*colors, -1);
    }

    // Color the first vertex with color 0
    colors[0] = 0;

    // Assign colors to the remaining vertices one by one
    for vertex: 1..num_vertices - 1 {

        // Track which colors are already used by this vertex's neighbors.
        // neighbor_has_color[c] = true means a neighbor is using color c.
        neighbor_has_color : [..] bool;
        for c: 0..num_vertices - 1 {
            array_add(*neighbor_has_color, false);
        }

        // Mark colors used by all neighbors of this vertex
        for neighbor: g.adjacency_list[vertex] {
            neighbor_color := colors[neighbor];
            if neighbor_color != -1 {
                neighbor_has_color[neighbor_color] = true;
            }
        }

        // Assign the smallest color not used by any neighbor
        chosen_color := 0;
        while chosen_color < num_vertices && neighbor_has_color[chosen_color] {
            chosen_color += 1;
        }
        colors[vertex] = chosen_color;

        array_free(neighbor_has_color);
    }

    return colors;
}

// Print the graph's adjacency list for debugging
print_graph :: (g: *Graph) {
    print("Graph adjacency list:\n");
    for vertex: 0..g.num_vertices - 1 {
        print("  Vertex %: ", vertex);
        for neighbor: g.adjacency_list[vertex] {
            print("% ", neighbor);
        }
        print("\n");
    }
}

// Print the coloring result
print_coloring :: (colors: [..] int) {
    print("Vertex coloring:\n");
    for color, vertex: colors {
        print("  Vertex % -> Color %\n", vertex, color);
    }
}

// Count the total number of distinct colors used
count_colors :: (colors: [..] int) -> int {
    max_color := -1;
    for color: colors {
        if color > max_color  max_color = color;
    }
    return max_color + 1;
}

main :: () {
    // Build a simple example graph:
    //
    //   0 --- 1
    //   |   / |
    //   |  /  |
    //   | /   |
    //   2 --- 3
    //
    // This is a cycle of 4 nodes with a diagonal (0-1-2-3-0 + edge 1-2).
    // It requires 3 colors because of the triangle formed by 0, 1, 2.

    g := make_graph(4);
    add_edge(*g, 0, 1);
    add_edge(*g, 0, 2);
    add_edge(*g, 1, 2);
    add_edge(*g, 1, 3);
    add_edge(*g, 2, 3);

    print_graph(*g);
    print("\n");

    colors := graph_color(*g);
    print_coloring(colors);

    total := count_colors(colors);
    print("\nTotal colors used: %\n", total);

    // Clean up
    array_free(colors);
    for i: 0..g.num_vertices - 1 {
        array_free(g.adjacency_list[i]);
    }
    array_free(g.adjacency_list);
}

Expected Output

Graph adjacency list:
  Vertex 0: 1 2
  Vertex 1: 0 2 3
  Vertex 2: 0 1 3
  Vertex 3: 1 2

Vertex coloring:
  Vertex 0 -> Color 0
  Vertex 1 -> Color 1
  Vertex 2 -> Color 2
  Vertex 3 -> Color 0

Total colors used: 3

Expected Output Explained

The greedy algorithm works through the vertices in order (0, 1, 2, ...):

• Vertex 0 gets Color 0 (it's first, nothing to conflict with).
• Vertex 1 is adjacent to 0 (Color 0), so it gets Color 1.
• Vertex 2 is adjacent to 0 (Color 0) and 1 (Color 1), so it gets Color 2.
• Vertex 3 is adjacent to 1 (Color 1) and 2 (Color 2). Color 0 is free, so it gets Color 0.

Note that greedy coloring does not guarantee the globally minimum number of colors (the chromatic number). The result can depend on vertex ordering. For optimal coloring, you'd need a more complex backtracking algorithm, but greedy is fast and works well in practice.

Notes on this Code

• Graph :: struct { ... } — defining a named struct as a constant
• [..] [..] int — a dynamic array of dynamic arrays (the adjacency list)
• array_add(*g.adjacency_list, neighbor_list) — adding to a dynamic array via pointer
• for neighbor: g.adjacency_list[vertex] — iterating directly over a dynamic array
• array_free(...) — explicit memory cleanup (no garbage collector!)
• g.num_vertices - 1 used in for vertex: 1..num_vertices - 1 — ranges are inclusive on both ends
• defer could be used here to ensure array_free is called, but was kept explicit for clarity