PRim算法是有關(guān)圖的最小生成樹的算法。1957年由美國(guó)計(jì)算機(jī)科學(xué)家羅伯特·普里姆（Robert C. Prim）獨(dú)立發(fā)現(xiàn)。

百度百科：Prim算法。

維基百科：Prim's Algorithm。

參考鏈接：Prim算法的C語(yǔ)言程序。

程序說明：圖存儲(chǔ)在二維數(shù)組中，即鄰接矩陣中。使用s集合和vs集合輔助Prim算法的過程，開始時(shí)將指定的開始結(jié)點(diǎn)放入s集合中，其他剩余的結(jié)點(diǎn)放入vs集合中，從s集合到vs集合的邊中找出一個(gè)代價(jià)最小的邊，然后將相關(guān)的結(jié)點(diǎn)從vs集合取出放入s集合，指定所有結(jié)點(diǎn)都在s集合為止。

需要說明的是，該程序使用了三重循環(huán)，其計(jì)算速度相當(dāng)?shù)穆梢哉f是不可用的。

C語(yǔ)言程序：

/* Prim算法的C語(yǔ)言程序 */#include <stdio.h>#define MAX_INT (int)((unsigned)(-1) >> 1)#define MIN(x, y) ((x)>(y))?(y):(x)#define TRUE 1#define FALSE 0#define  N 6struct item {    int s;    int v;    int cost;} closedge[N];int pc = 0;int a[N+1][N+1];int s_set[N+1], s_count;int vs_set[N+1], vs_count;void createMatrix();void init(int s);void prim();int main(void){    int i, j, s;    createMatrix();    for(i=1; i<=N; i++) {        for(j=1; j<=N; j++)            printf("%4d", a[i][j]);        printf("/n");    }    printf("start node:");    scanf("%d", &s);    if(s>=1 && s<=N) {        init(s);    } else {        printf("input error!/n");        return -1;    }    prim();    printf("result:/n");    for(i=0; i<pc; i++) {        printf("%4d%4d %4d/n", closedge[i].s, closedge[i].v, closedge[i].cost);    }    return 0;}void prim(){    int i, j, minval, pi, pj;    for(;;) {        if(vs_count == 0)            return;        minval=MAX_INT;        for(i=1; i<=N; i++) {            if(s_set[i]) {                for(j=1; j<=N; j++) {                    if(i!=j && vs_set[j]) {                        if(a[i][j] != -1 && a[i][j] < minval) {                            minval = a[i][j];                            pi = i;                            pj = j;                        }                    }                }            }        }        s_set[pj] = TRUE;        s_count++;        vs_set[pj] = FALSE;        vs_count--;        closedge[pc].s = pi;        closedge[pc].v = pj;        closedge[pc].cost = minval;        pc++;    }}//創(chuàng)建鄰接矩陣void createMatrix(){    int i, j;    for(i=1; i<=N; i++)        for(j=1; j<=N; j++)            if(i==j)                a[i][j] = 0;            else                a[i][j] = -1;    FILE *fp;    fp = fopen("/home/lin/workdir/TYUT/algorithm/p1.txt", "r");    for(;;) {        int val;        fscanf(fp, "%d%d%d", &i, &j, &val);        if(i == -1)            break;        a[i][j] = val;        a[j][i] = val;    }    fclose(fp);}void init(int s){    int i;    for(i=1; i<=N; i++) {        s_set[i] = FALSE;        vs_set[i] = TRUE;    }    s_set[s] = TRUE;    s_count = 1;    vs_set[s] = FALSE;    vs_count = N-1;}輸入文件數(shù)據(jù)：
1 2 61 3 11 4 52 3 52 5 33 4 53 5 63 6 4 4 6 25 6 6-1 -1 -1
程序運(yùn)行結(jié)果：
   0   6   1   5  -1  -1   6   0   5  -1   3  -1   1   5   0   5   6   4   5  -1   5   0  -1   2  -1   3   6  -1   0   6  -1  -1   4   2   6   0start node:1result:   1   3    1   3   6    4   6   4    2   3   2    5   2   5    3輸入的圖：
輸出的圖：