Implementation - Network Segmentation

Here is Stoer-Wagner minimum cut:

function stoerWagner(n, adj, weight):
    minCut = infinity
    vertices = [0, 1, 2, ..., n-1]

    while vertices.length > 1:
        // Maximum adjacency ordering
        added = array of size n, all false
        order = empty list
        key = array of size n, all 0

        for i from 1 to vertices.length:
            // Find vertex with max key not yet added
            maxKey = -infinity
            maxV = -1
            for v in vertices:
                if not added[v] and key[v] > maxKey:
                    maxKey = key[v]
                    maxV = v

            added[maxV] = true
            order.append(maxV)

            // Update keys
            for u in vertices:
                if not added[u]:
                    key[u] = key[u] + weight[maxV][u]

        // Last two vertices in ordering
        s = order[order.length - 2]
        t = order[order.length - 1]

        // Cut of the phase
        cutValue = key[t]
        minCut = min(minCut, cutValue)

        // Merge s and t
        mergeVertices(s, t, vertices, weight)

    return minCut

Time: $O(V^3)$ or $O(VE \log V)$ with heap. Space: $O(V^2)$.