# グラフgの最小全域木を求める
# T: 最小全域木に含まれるノードの集合
prim(g):
    s ← 0                # 適当な始点を決める

    for v ← 0 to g.N - 1:
        dist[v] ← INF
        parent[v] ← NIL  # 親がない状態

    dist[s] ← 0

    while True:
        u ← NIL
        minv ← INF
        # find minimum
        for v ← 0 to g.N - 1:
            if vがTに含まれる: continue
            if dist[v] < minv:
                u ← v;
                minv ← dist[v]

        if u = NIL: break
        T にuを含める		 

        for v ← 0 to g.N - 1:
            if g.weight[u][v] = INF: continue
            if vがTに含まれる: continue
            if dis[v] > weight[u][v]:
                dist[v] ← weight[u][v]
                parent[v] ← u