# 求图 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
        将 u 加入 T		 

        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