Algorithms: Graph Algorithms

Algorithms: Graph Algorithms

Explore algorithms: graph algorithms code snippets and tutorials

Algorithms: Graph Algorithms

Kosaraju Strongly Connected Components in C#

Strongly connected components group vertices that can reach each other in both directions..

csharp 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using System;
// Kosaraju Strongly Connected Components in C#
//
// PURPOSE
// Strongly connected components group vertices that can reach each other in both directions.
//
// METHOD
// First perform iterative DFS to record finishing order. Traverse vertices in reverse
// finishing order using incoming edges, counting each newly discovered component.
//
// COMPLEXITY
// O(n squared) time for the dense matrix and O(n) auxiliary space.
//
// CONTRACT
// Flattened n by n directed 0/1 matrix. Returns number of components; empty graph returns
// zero.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C# / .NET 10: ReadOnlySpan<int> inputs, Span<int> outputs, primitive workspace arrays,
// Array.BinarySearch for LIS, and checked integer arithmetic. Invalid arguments and overflow
// throw exceptions.
//
// EXAMPLE
// Expected return: 2.
// Run: Use Program.cs in a net10.0 console project; dotnet run.
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

class Program {
    static void alg_require(bool valid) { if (!valid) throw new ArgumentException("invalid algorithm input"); }
    static int alg_size(int n) { alg_require(n>=0 && n<=4000000); return n; }

    static int scc_count(ReadOnlySpan<int> graph, int n) {
        checked {
            alg_require(((n >= 0) && (n <= 1000000)));
            alg_require((graph.Length == (n * n)));
            int[] seen = new int[alg_size((n + 1))];
            int[] stack = new int[alg_size((n + 1))];
            int[] next_vertex = new int[alg_size((n + 1))];
            int[] order = new int[alg_size((n + 1))];
            int source = 0;
            int top = 0;
            int finished = 0;
            int u = 0;
            int v = 0;
            int count = 0;
            while ((source < n)) {
                if ((seen[source] == 0)) {
                    stack[0] = source;
                    top = 1;
                    seen[source] = 1;
                    while ((top > 0)) {
                        u = stack[(top - 1)];
                        if ((next_vertex[u] == n)) {
                            order[finished] = u;
                            finished = (finished + 1);
                            top = (top - 1);
                        } else {
                            v = next_vertex[u];
                            next_vertex[u] = (next_vertex[u] + 1);
                            if (((graph[((u * n) + v)] != 0) && (seen[v] == 0))) {
                                seen[v] = 1;
                                stack[top] = v;
                                top = (top + 1);
                            }
                        }
                    }
                }
                source = (source + 1);
            }
            source = 0;
            while ((source < n)) {
                seen[source] = 0;
                source = (source + 1);
            }
            while ((finished > 0)) {
                finished = (finished - 1);
                source = order[finished];
                if ((seen[source] == 0)) {
                    count = (count + 1);
                    stack[0] = source;
                    top = 1;
                    seen[source] = 1;
                    while ((top > 0)) {
                        top = (top - 1);
                        u = stack[top];
                        v = 0;
                        while ((v < n)) {
                            if (((graph[((v * n) + u)] != 0) && (seen[v] == 0))) {
                                seen[v] = 1;
                                stack[top] = v;
                                top = (top + 1);
                            }
                            v = (v + 1);
                        }
                    }
                }
            }
            return count;
        }
    }

    static void Main() {
        int[] graph = new int[] {0, 1, 0, 1, 0, 1, 0, 0, 0};
        int n = 3;
        int result = scc_count(graph, n);
        Console.WriteLine(result);
    }
}
Nov 15, 2026 csharp
Algorithms: Graph Algorithms

Kosaraju Strongly Connected Components in PHP

Strongly connected components group vertices that can reach each other in both directions..

php 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
<?php
declare(strict_types=1);
// Kosaraju Strongly Connected Components in PHP
//
// PURPOSE
// Strongly connected components group vertices that can reach each other in both directions.
//
// METHOD
// First perform iterative DFS to record finishing order. Traverse vertices in reverse
// finishing order using incoming edges, counting each newly discovered component.
//
// COMPLEXITY
// O(n squared) time for the dense matrix and O(n) auxiliary space.
//
// CONTRACT
// Flattened n by n directed 0/1 matrix. Returns number of components; empty graph returns
// zero.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// PHP 8.1+ on a 64-bit runtime: packed arrays, strict scalar types, read-only inputs by
// value using copy-on-write, references only for outputs, and checked 32-bit arithmetic.
// Invalid input and overflow throw exceptions. PHP arrays have higher overhead than native
// packed buffers in C/Java.
//
// EXAMPLE
// Expected return: 2.
// Run: php example.php
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

function alg_require(bool $valid): void { if (!$valid) throw new InvalidArgumentException("invalid algorithm input"); }
function alg_checked(int|float $v): int { if ($v < -2147483648 || $v > 2147483647 || floor($v) != $v) throw new OverflowException("32-bit result overflow"); return (int)$v; }
function alg_add(int $a,int $b): int { return alg_checked($a+$b); }
function alg_sub(int $a,int $b): int { return alg_checked($a-$b); }
function alg_mul(int $a,int $b): int { return alg_checked($a*$b); }
function alg_size(int $n): int { alg_require($n>=0 && $n<=4000000); return $n; }

function scc_count(array $graph, int $n): int {
    alg_require(array_is_list($graph));
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($graph) == alg_mul($n, $n)));
    $seen = array_fill(0, alg_size(alg_add($n, 1)), 0);
    $stack = array_fill(0, alg_size(alg_add($n, 1)), 0);
    $next_vertex = array_fill(0, alg_size(alg_add($n, 1)), 0);
    $order = array_fill(0, alg_size(alg_add($n, 1)), 0);
    $source = 0;
    $top = 0;
    $finished = 0;
    $u = 0;
    $v = 0;
    $count = 0;
    while (($source < $n)) {
        if (($seen[$source] == 0)) {
            $stack[0] = $source;
            $top = 1;
            $seen[$source] = 1;
            while (($top > 0)) {
                $u = $stack[alg_sub($top, 1)];
                if (($next_vertex[$u] == $n)) {
                    $order[$finished] = $u;
                    $finished = alg_add($finished, 1);
                    $top = alg_sub($top, 1);
                } else {
                    $v = $next_vertex[$u];
                    $next_vertex[$u] = alg_add($next_vertex[$u], 1);
                    if ((($graph[alg_add(alg_mul($u, $n), $v)] != 0) && ($seen[$v] == 0))) {
                        $seen[$v] = 1;
                        $stack[$top] = $v;
                        $top = alg_add($top, 1);
                    }
                }
            }
        }
        $source = alg_add($source, 1);
    }
    $source = 0;
    while (($source < $n)) {
        $seen[$source] = 0;
        $source = alg_add($source, 1);
    }
    while (($finished > 0)) {
        $finished = alg_sub($finished, 1);
        $source = $order[$finished];
        if (($seen[$source] == 0)) {
            $count = alg_add($count, 1);
            $stack[0] = $source;
            $top = 1;
            $seen[$source] = 1;
            while (($top > 0)) {
                $top = alg_sub($top, 1);
                $u = $stack[$top];
                $v = 0;
                while (($v < $n)) {
                    if ((($graph[alg_add(alg_mul($v, $n), $u)] != 0) && ($seen[$v] == 0))) {
                        $seen[$v] = 1;
                        $stack[$top] = $v;
                        $top = alg_add($top, 1);
                    }
                    $v = alg_add($v, 1);
                }
            }
        }
    }
    return $count;
}

$graph = [0, 1, 0, 1, 0, 1, 0, 0, 0];
$n = 3;
$result = scc_count($graph, $n);
echo $result, PHP_EOL;
Nov 15, 2026 PHP
Algorithms: Graph Algorithms

Kruskal Minimum Spanning Tree in Java

Kruskal adds edges in ascending weight order whenever they join different components..

java 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// Kruskal Minimum Spanning Tree in Java
//
// PURPOSE
// Kruskal adds edges in ascending weight order whenever they join different components.
//
// METHOD
// Sort edge indices by weight using a stable bottom-up merge. Use union by size and path
// halving to accept edges joining different roots. Stop after n-1 accepted edges.
//
// COMPLEXITY
// O(E log E + V) time and O(V+E) auxiliary space.
//
// CONTRACT
// n>=1, parallel edge arrays have m entries and valid vertex IDs. Weights nonnegative; total
// fits signed 32-bit. Returns -1 for a disconnected graph.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// Java 17+: primitive int arrays, Arrays.binarySearch for LIS, and Math exact arithmetic.
// Invalid input throws IllegalArgumentException; arithmetic overflow throws
// ArithmeticException.
//
// EXAMPLE
// Expected return: 6.
// Run: javac AlgorithmExample.java && java AlgorithmExample
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

class AlgorithmExample {
    static void alg_require(boolean valid) { if (!valid) throw new IllegalArgumentException("invalid algorithm input"); }
    static int alg_size(int n) { alg_require(n>=0 && n<=4000000); return n; }

    static int kruskal(int[] from_vertex, int[] to_vertex, int[] weight, int n) {
        java.util.Objects.requireNonNull(from_vertex, "from_vertex");
        java.util.Objects.requireNonNull(to_vertex, "to_vertex");
        java.util.Objects.requireNonNull(weight, "weight");
        int m = from_vertex.length;
        alg_require(((n >= 0) && (n <= 1000000)));
        alg_require(((m >= 0) && (m <= 1000000)));
        alg_require((from_vertex.length == m));
        alg_require((to_vertex.length == m));
        alg_require((weight.length == m));
        alg_require((n >= 1));
        for (int alg_i = 0; alg_i < from_vertex.length; alg_i++) {
            int alg_value = from_vertex[alg_i];
            alg_require(((alg_value >= 0) && (alg_value < n)));
        }
        for (int alg_i = 0; alg_i < to_vertex.length; alg_i++) {
            int alg_value = to_vertex[alg_i];
            alg_require(((alg_value >= 0) && (alg_value < n)));
        }
        int[] order = new int[alg_size(Math.addExact(m, 1))];
        int[] buffer = new int[alg_size(Math.addExact(m, 1))];
        int[] parent = new int[alg_size(n)];
        int[] size = new int[alg_size(n)];
        int i = 0;
        int j = 0;
        int k = 0;
        int width = 1;
        int left = 0;
        int mid = 0;
        int right = 0;
        int edge = 0;
        int u = 0;
        int v = 0;
        int temp = 0;
        int accepted = 0;
        int total = 0;
        while ((i < m)) {
            order[i] = i;
            i = Math.addExact(i, 1);
        }
        while ((width < m)) {
            left = 0;
            while ((left < m)) {
                mid = Math.min(Math.addExact(left, width), m);
                right = Math.min(Math.addExact(left, Math.multiplyExact(2, width)), m);
                i = left;
                j = mid;
                k = left;
                while ((k < right)) {
                    if (((i < mid) && ((j >= right) || (weight[order[i]] <= weight[order[j]])))) {
                        buffer[k] = order[i];
                        i = Math.addExact(i, 1);
                    } else {
                        buffer[k] = order[j];
                        j = Math.addExact(j, 1);
                    }
                    k = Math.addExact(k, 1);
                }
                left = Math.addExact(left, Math.multiplyExact(2, width));
            }
            i = 0;
            while ((i < m)) {
                order[i] = buffer[i];
                i = Math.addExact(i, 1);
            }
            width = Math.multiplyExact(width, 2);
        }
        i = 0;
        while ((i < n)) {
            parent[i] = i;
            size[i] = 1;
            i = Math.addExact(i, 1);
        }
        while (((edge < m) && (accepted < Math.subtractExact(n, 1)))) {
            u = from_vertex[order[edge]];
            v = to_vertex[order[edge]];
            while ((parent[u] != u)) {
                parent[u] = parent[parent[u]];
                u = parent[u];
            }
            while ((parent[v] != v)) {
                parent[v] = parent[parent[v]];
                v = parent[v];
            }
            if ((u != v)) {
                if ((size[u] < size[v])) {
                    temp = u;
                    u = v;
                    v = temp;
                }
                parent[v] = u;
                size[u] = Math.addExact(size[u], size[v]);
                accepted = Math.addExact(accepted, 1);
                total = Math.addExact(total, weight[order[edge]]);
            }
            edge = Math.addExact(edge, 1);
        }
        if ((accepted != Math.subtractExact(n, 1))) {
            return Math.negateExact(1);
        }
        return total;
    }

    public static void main(String[] args) {
        int[] from_vertex = new int[] {0, 1, 0};
        int[] to_vertex = new int[] {1, 2, 2};
        int[] weight = new int[] {4, 2, 10};
        int n = 3;
        int result = kruskal(from_vertex, to_vertex, weight, n);
        System.out.println(result);
    }
}
Nov 15, 2026 Java
Algorithms: Graph Algorithms

Kruskal Minimum Spanning Tree in JavaScript

Kruskal adds edges in ascending weight order whenever they join different components..

javascript 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
"use strict";
// Kruskal Minimum Spanning Tree in JavaScript
//
// PURPOSE
// Kruskal adds edges in ascending weight order whenever they join different components.
//
// METHOD
// Sort edge indices by weight using a stable bottom-up merge. Use union by size and path
// halving to accept edges joining different roots. Stop after n-1 accepted edges.
//
// COMPLEXITY
// O(E log E + V) time and O(V+E) auxiliary space.
//
// CONTRACT
// n>=1, parallel edge arrays have m entries and valid vertex IDs. Weights nonnegative; total
// fits signed 32-bit. Returns -1 for a disconnected graph.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// Node.js 18+: Int32Array inputs and workspaces provide compact integer storage. Automatic
// lengths and checked arithmetic reject values outside signed 32-bit. Invalid inputs or
// overflow throw RangeError.
//
// EXAMPLE
// Expected return: 6.
// Run: node example.js
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

function alg_require(valid) { if (!valid) throw new RangeError("invalid algorithm input"); }
function alg_checked(v) { if (!Number.isInteger(v) || v < -2147483648 || v > 2147483647) throw new RangeError("32-bit result overflow"); return v; }
function alg_add(a,b) { return alg_checked(a+b); }
function alg_sub(a,b) { return alg_checked(a-b); }
function alg_mul(a,b) { return alg_checked(a*b); }
function alg_size(n) { alg_require(Number.isInteger(n) && n>=0 && n<=4000000); return n; }

function kruskal(from_vertex, to_vertex, weight, n) {
    alg_require(from_vertex instanceof Int32Array);
    alg_require(to_vertex instanceof Int32Array);
    alg_require(weight instanceof Int32Array);
    alg_require(Number.isInteger(n) && n >= -2147483648 && n <= 2147483647);
    let m = from_vertex.length;
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((m >= 0) && (m <= 1000000)));
    alg_require((from_vertex.length == m));
    alg_require((to_vertex.length == m));
    alg_require((weight.length == m));
    alg_require((n >= 1));
    for (let alg_i = 0; alg_i < from_vertex.length; alg_i++) {
        let alg_value = from_vertex[alg_i];
        alg_require(((alg_value >= 0) && (alg_value < n)));
    }
    for (let alg_i = 0; alg_i < to_vertex.length; alg_i++) {
        let alg_value = to_vertex[alg_i];
        alg_require(((alg_value >= 0) && (alg_value < n)));
    }
    let order = new Int32Array(alg_size(alg_add(m, 1)));
    let buffer = new Int32Array(alg_size(alg_add(m, 1)));
    let parent = new Int32Array(alg_size(n));
    let size = new Int32Array(alg_size(n));
    let i = 0;
    let j = 0;
    let k = 0;
    let width = 1;
    let left = 0;
    let mid = 0;
    let right = 0;
    let edge = 0;
    let u = 0;
    let v = 0;
    let temp = 0;
    let accepted = 0;
    let total = 0;
    while ((i < m)) {
        order[i] = i;
        i = alg_add(i, 1);
    }
    while ((width < m)) {
        left = 0;
        while ((left < m)) {
            mid = Math.min(alg_add(left, width), m);
            right = Math.min(alg_add(left, alg_mul(2, width)), m);
            i = left;
            j = mid;
            k = left;
            while ((k < right)) {
                if (((i < mid) && ((j >= right) || (weight[order[i]] <= weight[order[j]])))) {
                    buffer[k] = order[i];
                    i = alg_add(i, 1);
                } else {
                    buffer[k] = order[j];
                    j = alg_add(j, 1);
                }
                k = alg_add(k, 1);
            }
            left = alg_add(left, alg_mul(2, width));
        }
        i = 0;
        while ((i < m)) {
            order[i] = buffer[i];
            i = alg_add(i, 1);
        }
        width = alg_mul(width, 2);
    }
    i = 0;
    while ((i < n)) {
        parent[i] = i;
        size[i] = 1;
        i = alg_add(i, 1);
    }
    while (((edge < m) && (accepted < alg_sub(n, 1)))) {
        u = from_vertex[order[edge]];
        v = to_vertex[order[edge]];
        while ((parent[u] != u)) {
            parent[u] = parent[parent[u]];
            u = parent[u];
        }
        while ((parent[v] != v)) {
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        if ((u != v)) {
            if ((size[u] < size[v])) {
                temp = u;
                u = v;
                v = temp;
            }
            parent[v] = u;
            size[u] = alg_add(size[u], size[v]);
            accepted = alg_add(accepted, 1);
            total = alg_add(total, weight[order[edge]]);
        }
        edge = alg_add(edge, 1);
    }
    if ((accepted != alg_sub(n, 1))) {
        return alg_sub(0, 1);
    }
    return total;
}

let from_vertex = new Int32Array([0, 1, 0]);
let to_vertex = new Int32Array([1, 2, 2]);
let weight = new Int32Array([4, 2, 10]);
let n = 3;
let result = kruskal(from_vertex, to_vertex, weight, n);
console.log(result);
Nov 15, 2026 javascript
Algorithms: Graph Algorithms

Kruskal Minimum Spanning Tree in Python

Kruskal adds edges in ascending weight order whenever they join different components..

python 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
from bisect import bisect_left

# Kruskal Minimum Spanning Tree in Python
#
# PURPOSE
# Kruskal adds edges in ascending weight order whenever they join different components.
#
# METHOD
# Sort edge indices by weight using a stable bottom-up merge. Use union by size and path
# halving to accept edges joining different roots. Stop after n-1 accepted edges.
#
# COMPLEXITY
# O(E log E + V) time and O(V+E) auxiliary space.
#
# CONTRACT
# n>=1, parallel edge arrays have m entries and valid vertex IDs. Weights nonnegative; total
# fits signed 32-bit. Returns -1 for a disconnected graph.
# Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
# counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
# Sorted order, correct tree topology, and caller-owned data-structure invariants are
# preconditions; checking them on every query would change query complexity.
# Scalar and shape checks are included. Value-range checks are included where needed to
# prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
# workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
# uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
# partly updated after arithmetic failure. These are single-threaded, in-memory
# implementations.
#
# LANGUAGE DETAILS
# Python 3.9+: automatic lengths, native lists, arbitrary-precision arithmetic, and
# bisect_left for LIS. Invalid scalar/shape inputs raise ValueError. Integer element types
# and sorted/tree invariants remain caller preconditions.
#
# EXAMPLE
# Expected return: 6.
# Run: python example.py
# Tests for this exact source artifact run before publication. The accompanying source
# archive includes unit cases, runtime results, and source hashes.

def alg_require(condition):
    if not condition:
        raise ValueError("invalid algorithm input; see contract")
def alg_size(n):
    alg_require(0 <= n <= 4000000)
    return n

def kruskal(from_vertex: list[int], to_vertex: list[int], weight: list[int], n: int) -> int:
    alg_require(isinstance(from_vertex, (list, tuple)) and len(from_vertex) <= 1000000)
    alg_require(isinstance(to_vertex, (list, tuple)) and len(to_vertex) <= 1000000)
    alg_require(isinstance(weight, (list, tuple)) and len(weight) <= 1000000)
    alg_require(type(n) is int and -2147483648 <= n <= 2147483647)
    m: int = len(from_vertex)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(m >= 0 and m <= 1000000)
    alg_require(len(from_vertex) == m)
    alg_require(len(to_vertex) == m)
    alg_require(len(weight) == m)
    alg_require(n >= 1)
    for value in from_vertex:
        alg_require(value >= 0 and value < n)
    for value in to_vertex:
        alg_require(value >= 0 and value < n)
    order: list[int] = [0] * alg_size(m + 1)
    buffer: list[int] = [0] * alg_size(m + 1)
    parent: list[int] = [0] * alg_size(n)
    size: list[int] = [0] * alg_size(n)
    i: int = 0
    j: int = 0
    k: int = 0
    width: int = 1
    left: int = 0
    mid: int = 0
    right: int = 0
    edge: int = 0
    u: int = 0
    v: int = 0
    temp: int = 0
    accepted: int = 0
    total: int = 0
    while i < m:
        order[i] = i
        i += 1
    while width < m:
        left = 0
        while left < m:
            mid = min(left + width, m)
            right = min(left + 2 * width, m)
            i = left
            j = mid
            k = left
            while k < right:
                if i < mid and (j >= right or weight[order[i]] <= weight[order[j]]):
                    buffer[k] = order[i]
                    i += 1
                else:
                    buffer[k] = order[j]
                    j += 1
                k += 1
            left += 2 * width
        i = 0
        while i < m:
            order[i] = buffer[i]
            i += 1
        width *= 2
    i = 0
    while i < n:
        parent[i] = i
        size[i] = 1
        i += 1
    while edge < m and accepted < n - 1:
        u = from_vertex[order[edge]]
        v = to_vertex[order[edge]]
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        while parent[v] != v:
            parent[v] = parent[parent[v]]
            v = parent[v]
        if u != v:
            if size[u] < size[v]:
                temp = u
                u = v
                v = temp
            parent[v] = u
            size[u] += size[v]
            accepted += 1
            total += weight[order[edge]]
        edge += 1
    if accepted != n - 1:
        return -1
    return total

from_vertex = [0, 1, 0]
to_vertex = [1, 2, 2]
weight = [4, 2, 10]
n = 3
result = kruskal(from_vertex, to_vertex, weight, n)
print(result)
Nov 15, 2026 python