Graph Algorithms

Graphs are one of the most important and unifying structures in computer science. They model relationships — and most real-world and computational problems are fundamentally about relationships.

A graph consists of:

• Vertices (nodes) -> entities
• Edges -> relationships between entities

This article seeks to document how to write different graph algorithms in Jai.

Prim's Algorithm

A graph is a collection of nodes (vertices) connected by edges. Each edge can have a weight — a cost associated with traversing that connection. Think of cities connected by roads, where the weight represents distance or travel time. A spanning tree of a connected graph is a subset of edges that:

• Connects all vertices (spans the entire graph)
• Contains no cycles (it's a tree)
• Uses exactly V - 1 edges for a graph with V vertices

A Minimum Spanning Tree (MST) is a spanning tree where the total sum of edge weights is as small as possible. Real-world applications include:

• Network design (laying cable, fiber, or pipes at minimum cost)
• Cluster analysis in machine learning
• Approximation algorithms for the Traveling Salesman Problem
• Circuit board routing
• Image segmentation

Algorithm Procedure

Prim's Algorithm builds the MST by growing it one edge at a time from a starting vertex. At each step, it greedily picks the cheapest edge that connects a vertex already in the MST to a vertex not yet in the MST. Here is the algorithm step by step:

• Start with any vertex. Mark it as "in the MST."
• Look at all edges crossing the boundary between "in MST" vertices and "not in MST" vertices.
• Pick the edge with the minimum weight.
• Add that edge and its new vertex to the MST.
• Repeat steps 2–4 until all vertices are in the MST.

Time Complexity: O(V^2) with an adjacency matrix, or O(E log V) with a priority queue.

#import "Basic";

// Represents the result of Prim's algorithm.
// Each entry in 'parent' says which vertex is the parent of vertex i in the MST.
// Each entry in 'key' stores the minimum edge weight to connect vertex i.
MST_Result :: struct {
    parent: [] int;   // parent[i] = parent of vertex i in the MST
    key:    [] float; // key[i]    = weight of edge connecting i to its parent
    total_cost: float;
}

// Find the vertex with the minimum key value that is not yet in the MST.
min_key_vertex :: (key: [] float, in_mst: [] bool) -> int {
    min_val := 999999.0;
    min_idx := -1;

    for i: 0..key.count - 1 {
        if !in_mst[i] && key[i] < min_val {
            min_val = key[i];
            min_idx = i;
        }
    }

    return min_idx;
}

// Prim's Algorithm.
// graph: a V x V adjacency matrix where graph[i][j] is the edge weight between i and j.
//        A value of 0 means no edge.
// V:     number of vertices
prim_mst :: (graph: [][] float, V: int) -> MST_Result {
    // key[i] = minimum weight to connect vertex i to the growing MST
    key := NewArray(V, float);

    // parent[i] = which MST vertex connects to vertex i
    parent := NewArray(V, int);

    // in_mst[i] = true if vertex i is already part of the MST
    in_mst := NewArray(V, bool);

    // Initialize: all keys are infinity, no vertex is in MST
    for i: 0..V - 1 {
        key[i]    = 999999.0; // represents "infinity"
        parent[i] = -1;
        in_mst[i] = false;
    }

    // Start from vertex 0. Its key is 0 so it gets picked first.
    key[0] = 0.0;

    // We need to pick V vertices total
    for step: 0..V - 1 {
        // Pick the vertex not yet in MST with the smallest key
        u := min_key_vertex(key, in_mst);
        in_mst[u] = true;

        // Update keys of adjacent vertices of u
        for v: 0..V - 1 {
            edge_weight := graph[u][v];

            // Only consider: edges that exist (non-zero),
            //                vertices not yet in MST,
            //                and only if this edge is cheaper than what we know
            if edge_weight > 0 && !in_mst[v] && edge_weight < key[v] {
                key[v]    = edge_weight;
                parent[v] = u;
            }
        }
    }

    // Compute total MST cost (skip vertex 0, it has no parent)
    total := 0.0;
    for i: 1..V - 1 {
        total += key[i];
    }

    result: MST_Result;
    result.parent     = parent;
    result.key        = key;
    result.total_cost = total;
    return result;
}

// Print the MST edges and total cost.
print_mst :: (result: MST_Result) {
    print("Edge      Weight\n");
    print("------------------\n");
    for i: 1..result.parent.count - 1 {
        print("% -- %    %\n", result.parent[i], i, result.key[i]);
    }
    print("\nTotal MST cost: %\n", result.total_cost);
}

main :: () {
    // Example graph with 5 vertices.
    // This is an adjacency matrix: graph[i][j] = weight of edge between i and j.
    // 0 means no edge between those two vertices.
    //
    //       0    1    2    3    4
    //   0 [ 0,   2,   0,   6,   0 ]
    //   1 [ 2,   0,   3,   8,   5 ]
    //   2 [ 0,   3,   0,   0,   7 ]
    //   3 [ 6,   8,   0,   0,   9 ]
    //   4 [ 0,   5,   7,   9,   0 ]

    V :: 5;

    // Build the adjacency matrix as a dynamic 2D array
    graph: [V][V] float;

    graph[0][1] = 2;  graph[1][0] = 2;
    graph[0][3] = 6;  graph[3][0] = 6;
    graph[1][2] = 3;  graph[2][1] = 3;
    graph[1][3] = 8;  graph[3][1] = 8;
    graph[1][4] = 5;  graph[4][1] = 5;
    graph[2][4] = 7;  graph[4][2] = 7;
    graph[3][4] = 9;  graph[4][3] = 9;

    // Convert to slice-of-slices for the function
    rows: [V] [] float;
    for i: 0..V-1 {
        rows[i].data  = *graph[i][0];
        rows[i].count = V;
    }

    graph_view: [] [] float;
    graph_view.data  = *rows[0];
    graph_view.count = V;

    result := prim_mst(graph_view, V);
    print_mst(result);
}

Expected Output

Edge      Weight
------------------
0 -- 1    2
1 -- 2    3
0 -- 3    6
1 -- 4    5

Total MST cost: 16

Step-by-Step Walkthrough

Using the graph from the example above:

    (2)       (3)
0 ------- 1 ------- 2
|         |         |
(6)      (8)       (7)
|         |         |
3 ------- 4 --------+
    (9)       (5)
            1 -- 4

Step	Vertex Added	Via Edge	Edge Weight	Notes
1	0	(start)	0	Starting vertex
2	1	0 → 1	2	Cheapest edge from {0}
3	2	1 → 2	3	Cheapest edge from {0,1}
4	4	1 → 4	5	Cheaper than 2→4 (7)
5	3	0 → 3	6	Cheaper than 1→3 (8) or 4→3 (9)

Total Cost: 2 + 3 + 5 + 6 = 16

---

Implementation Notes

Why the adjacency matrix? The adjacency matrix is the simplest representation to start with. For a graph with V vertices, it's a V × V grid where matrix[i][j] stores the weight of the edge from i to j. Checking whether an edge exists is O(1). The downside is it uses O(V²) memory even for sparse graphs.

The min_key_vertex function In the simple O(V²) implementation, finding the next vertex to add requires scanning all vertices to find the one with the smallest key that isn't yet in the MST. This linear scan is why the overall algorithm is O(V²). For large sparse graphs, replacing this with a priority queue (min-heap) brings the complexity down to O(E log V).

The key array Each key[v] represents the weight of the cheapest edge we've found so far that could connect vertex v to the MST. When we add a new vertex u to the MST, we check all of u's neighbors — if we find a cheaper connection to any of them, we update their key and record u as their parent.

Why does this produce a correct MST? Prim's algorithm is an instance of the greedy algorithm strategy. At each step it picks the globally cheapest edge crossing the MST boundary. It can be proven correct via the Cut Property: for any cut of the graph (a partition of vertices into two sets), the minimum weight edge crossing that cut must belong to some MST.

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].

Bellman Ford Algorithm

Bellman-Ford finds the shortest path from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, it handles negative edge weights correctly. It works by repeatedly "relaxing" every edge — checking if going through that edge gives a shorter path than what's currently known. The algorithm runs in O(V * E) time, where V is the number of vertices and E is the number of edges. It also detects negative-weight cycles: if after V-1 relaxation passes you can still relax an edge, a negative cycle exists.

#import "Basic";

// Represents a directed edge from 'src' to 'dst' with a given weight.
Edge :: struct {
    src    : int;
    dst    : int;
    weight : int;
}

// Returns the shortest distances from 'source' to all vertices.
// Returns an empty array if a negative cycle is detected.
bellman_ford :: (num_vertices: int, edges: []Edge, source: int) -> [..]int, bool {
    INF :: 1_000_000_000;

    // Step 1: Initialize all distances to infinity, source to 0.
    dist: [..]int;
    for 0..num_vertices-1  array_add(*dist, INF);
    dist[source] = 0;

    // Step 2: Relax all edges (num_vertices - 1) times.
    for pass: 1..num_vertices-1 {
        for edge: edges {
            if dist[edge.src] != INF && dist[edge.src] + edge.weight < dist[edge.dst] {
                dist[edge.dst] = dist[edge.src] + edge.weight;
            }
        }
    }

    // Step 3: Check for negative-weight cycles.
    // If we can still relax an edge, a negative cycle exists.
    for edge: edges {
        if dist[edge.src] != INF && dist[edge.src] + edge.weight < dist[edge.dst] {
            print("Negative cycle detected!\n");
            empty: [..]int;
            return empty, false;
        }
    }

    return dist, true;
}

main :: () {
    // Graph with 5 vertices (0..4)
    edges: [..]Edge;
    array_add(*edges, .{src=0, dst=1, weight= 6});
    array_add(*edges, .{src=0, dst=2, weight= 7});
    array_add(*edges, .{src=1, dst=3, weight= 5});
    array_add(*edges, .{src=2, dst=3, weight=-3});
    array_add(*edges, .{src=3, dst=4, weight= 9});

    dist, ok := bellman_ford(5, edges, source=0);

    if ok {
        for i: 0..dist.count-1 {
            print("Distance from 0 to %: %\n", i, dist[i]);
        }
    }
}

Expected output:

Distance from 0 to 0: 0
Distance from 0 to 1: 6
Distance from 0 to 2: 7
Distance from 0 to 3: 4
Distance from 0 to 4: 13

Implementation Notes

• This implementation uses INF :: 1_000_000_000 because adding to a constant such as S64_MAX would overflow. A large sentinel value like one billion works cleanly for typical graph problems.
• The INF guard (dist[edge.src] != INF). Without this check, an unreachable vertex (still at INF) could produce integer overflow when you compute INF + weight. This guard ensures we only try to relax edges from vertices we've actually reached.
• Relaxation loop runs V-1 times. The longest possible shortest path without a cycle visits at most V-1 edges. So after V-1 passes, all shortest paths are guaranteed to be found — if no negative cycle exists.
• Negative cycle detection. The final loop is a V-th pass. Any edge that can still be relaxed after V-1 rounds must be part of a negative cycle (because a path through it would need to loop around indefinitely to keep decreasing).

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