Prim算法

留言

中文一般译作普里姆算法

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆(Robert C. Prim,1921年出生于美国德州)独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法.

有些类似迪杰克斯拉算法



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//来源：严蔚敏 吴伟民《数据结构(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};
        }
    }
}

文章目录