普林姆算法
各語言程序代码 > C语言代码

//来源：严蔚敏 吴伟民《数据结构(C语言版)》

void MiniSpanTree_PRIM (MGraph G, VertexType u) {
    /*  用普利姆算法從第u個頂點出發構造網G 的最小生成樹T,輸出T的各條邊。
        記錄從頂點集U到V-U的代價最小的邊的輔助數組定義：
        struct
        {
            VertexType adjvex;
            VRtype lowcost;
        }closedge[MAX_VERTEX_NUM];
    */
    
    k = LocateVex(G, u);
    for (j = 0 ; j < G.vexnum; j++) {           //輔助數組初始化
        if (j != k)
            closedge[j] = {u, G.arcs[k][j].adj}; //{adjvex, lowcost}
    }
    closedge[k].lowcost = 0;                 //初始，U={u}
    for (i = 1; i < G.vexnum ; i++) {           //選擇其餘G.vexnum -1 個頂點
        k = minimum(closedge);              //求出T的下個結點：第k結點
        //  此时 closedge[k].lowcost = MIN{ closedge[Vi].lowcost|closedge[Vi].lowcost>0,Vi∈V-U}
        printf(closedge[k].adjvex, G.vexs[k]);    //輸出生成樹的邊
        closedge[k].lowcost = 0;             //第k條邊併入U集
        for (j = 0; j < G.vexnum; j++) {
        
            //新頂點併入U後重新選擇最小邊
            if (G.arcs[k][j].adj < closedge[j].lowcost && closedge[j].lowcost!=0) 
                closedge[j] = {G.vex[k], G.arcs[k][j].adj};
        }
    }
}
//来源： 浙大-陈越 《数据结构》

#define ERROR -1
Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{
    /* 返回未被收录顶点中dist最小者 */
    
    Vertex MinV, V;
    WeightType MinDist = INFINITY;

    for (V=0; V<Graph->Nv; V++) {
        if ( dist[V]!=0 && dist[V]<MinDist) {
            /* 若V未被收录，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在，返回-1作为标记 */
}

int Prim( MGraph Graph, LGraph MST )
{ /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
    WeightType dist[MaxVertexNum], TotalWeight;
    Vertex parent[MaxVertexNum], V, W;
    int VCount;
    Edge E;

    /* 初始化。默认初始点下标是0 */
       for (V=0; V<Graph->Nv; V++) {
        /* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */
           dist[V] = Graph->G[0][V];
           parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */
    }
    TotalWeight = 0; /* .

    ..........初始化权重和     */
    VCount = 0;      /* 初始化收录的顶点数 */
    /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
    MST = CreateGraph(Graph->Nv);
    E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */

    /* 将初始点0收录进MST */
    dist[0] = 0;
    VCount ++;
    parent[0] = -1; /* 当前树根是0 */

    while (1) {
        V = FindMinDist( Graph, dist );
        /* V = 未被收录顶点中dist最小者 */
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;   /* 算法结束 */

        /* 将V及相应的边<parent[V], V>收录进MST */
        E->V1 = parent[V];
        E->V2 = V;
        E->Weight = dist[V];
        InsertEdge( MST, E );
        TotalWeight += dist[V];
        dist[V] = 0;
        VCount++;

        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
            /* 若W是V的邻接点并且未被收录 */
                if ( Graph->G[V][W] < dist[W] ) {
                /* 若收录V使得dist[W]变小 */
                    dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                    parent[W] = V; /* 更新树 */
                }
            }
    } /* while结束*/
    if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
       TotalWeight = ERROR;
    return TotalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */
}