普里姆算法求最小生成樹

    #include "iostream"

    using namespace std;


const int num = 9; //節點個數  
#define Infinity 65535;  
//本例中以節點0作為生成樹的起始節點  
void MinSpanTree_Prime(int graphic[num][num]){  
    int lowcost[num]; //記錄從節點num到生成樹的最短距離，如果為0則表示該節點已在生成樹中  
    int adjvex[num]; //記錄相關節點，如:adjvex[1] = 5表示最小生成樹中節點1和5有路徑相連  
    int sum = 0; // 記錄最小生成樹邊權重之和  
    memset(adjvex, 0, sizeof(adjvex));  
    //選取0節點作為生成樹的起點  
    for (int i = 0; i < num; i++)  
        lowcost[i] = graphic[0][i];  

    for (int i = 1; i < num; i++){  
        int min = Infinity;  
        int index;  
        for (int j = 1; j < num; j++){  
            if (lowcost[j] != 0 && lowcost[j] < min){  
                index = j;  
                min = lowcost[j];  
            }  
        }  
        sum += min;  
        lowcost[index] = 0; //將當前節點放入生成樹中  
        cout << adjvex[index] << " -> " << index << endl;  
        //修正其他節點到生成樹的最短距離  
        for (int j = 1; j < num; j++){  
            if (lowcost[j] != 0 && graphic[index][j] < lowcost[j]){  
                lowcost[j] = graphic[index][j];  
                adjvex[j] = index;  
            }  
        }  
    }  
    cout << "sum = " << sum << endl;  
}  

int main(){  
    int graphic[num][num];  
    for (int i = 0; i < num; i++)  
    for (int j = 0; j < num; j++){  
        if (i == j)  
            graphic[i][j] = 0;  
        else  
            graphic[i][j] = Infinity;  
    }  
    graphic[0][1] = 1;  
    graphic[0][2] = 5;  
    graphic[1][0] = 1;  
    graphic[1][2] = 3;  
    graphic[1][3] = 7;  
    graphic[1][4] = 5;  
    graphic[2][0] = 5;  
    graphic[2][1] = 3;  
    graphic[2][4] = 1;  
    graphic[2][5] = 7;  
    graphic[3][1] = 7;  
    graphic[3][4] = 2;  
    graphic[3][6] = 3;  
    graphic[4][1] = 5;  
    graphic[4][2] = 1;  
    graphic[4][3] = 2;  
    graphic[4][5] = 3;  
    graphic[4][6] = 6;  
    graphic[4][7] = 9;  
    graphic[5][2] = 7;  
    graphic[5][4] = 3;  
    graphic[5][7] = 5;  
    graphic[6][3] = 3;  
    graphic[6][4] = 6;  
    graphic[6][7] = 2;  
    graphic[6][8] = 7;  
    graphic[7][4] = 9;  
    graphic[7][5] = 5;  
    graphic[7][6] = 2;  
    graphic[7][8] = 4;  
    graphic[8][6] = 7;  
    graphic[8][7] = 4;  

    MinSpanTree_Prime(graphic);  

    return 0;  
}  </pre>