Prim算法是典型的贪心算法

• 第一步：任选1个结点，作为子图G’的第一个结点。
• 第二步：找出与G’相连、且不会与G’构成回路，且权值最小的边，并将该边及相邻结点收入G’。该步骤不断重复

一、伪码前的基本设定

1、图的存储方式：邻接矩阵edge

edge[i][j] = w 表示i与j之间有一条权重为w的边

2、如何存储G’？

设定一个TE数组，该数组存储着所有收入树中的边。
TE[i]: 被收入树的第i个边
head(TE[i]): 边TE[i]的起点
tail(TE[i]): 边TE[i]的终点
cost(TE[i]): 边TE[i]的权重

3、如何每次找到不会形成回路、且权值最小的边？

设定数组closedge,
closedge[i]表示序号为i的顶点。
Vex(closedge[i])表示i号顶点的所有邻接点中，在G’中且边的权重最小的点。
Lowcost(closedge[i])表示i该边的长度

当i被收入G’中后：
Vex(closedge[i]) = -1
Lowcost(closedge[i]) = 0

这样，通过遍历closedge数组，就可以找出未被收入G’且距离最小的点。

closedge表如何更新？当v被收入G’中后，与v相邻的点需要被更新

伪码：

算法Prim()
/*构造最小生成树的Prim算法*/
Prim 1.[以顶点1为初始顶点，初始化数组closedge]
    FOR i = 1 TO n DO{
        Lowcost(closedge[i]) = egde[1][i]. 
        Vex(closedge[i]) = 1.
    }
    Vex(closedge[1]) = -1.
    count = 1//count用于对G'中节点数量进行计数
Prim 2.[构造图的最小支撑树]
    FOR i = 2 TO n DO{ // 每次循环均能收录一个结点
        min = max.
        v = 0.//待选中的点
        FOR j = 1 TO n DO{ //遍历寻找权值最小的边
            IF( Vex(closedge[j] ≠ -1) AND Lowcost(closedge[j]) < min>) THEN{
                v = j.
                min = Lowcost(closedge[j]).
            }
        }
    }
    IF v == 0 THEN
    RETURN.//说明图不连通，无法建立树


    //v是已经选中的点，现在需要把它收入G'中
    head(TE[count]) = Vex(closedge[v]).
    tail(TE[count]) = v.
    cost(TE[count]) = Lowcost(closedge[v]).
    count = count + 1.

    //将v标记为已收入状态。
    Lowcost(closedge[v]) = 0.
    Vex(closedge[v]) = -1.

    //当v被收入后，与v相邻的点的值也需要被更新。
    FOR j = 1 TO n DO{
        IF(Vex(closedge[j]≠-1 AND edge[v][j] < Lowcost(closedge[j])))
        THEN {
            Lowcost(closedge[j]) = edge[v][j].
            Vex(closedge[j]) = v.
        }
    }