prim 算法 最小生成樹

#include <iostream>

using namespace std;

int const M = 65536;

void prim(int graph[][4],int n){

int* adjnode = new int[n]; 

int* lowcost = new int[n];

//所有已選節點中到每一個節點最短權的節點數組,例如[0,0,2,2,0,2]，表示到下一個節點最近的點

adjnode[0] = 0;

//

lowcost[0] = 0;

//初始化，讀取第一行資料，即第一個節點到各節點權

for(int i=1;i!=n;i++){

lowcost[i] = graph[0][i];

//初始化所有資料都是第一個節點

adjnode[i] = 0;

}

for(int i=1;i!=n;i++){

int minIndex = 0;

int min = M;

for(int j=1;j!=n;j++){

if(lowcost[j]!=0&&min>lowcost[j]){

//在已知點集合的所有邊中最小權

min = lowcost[j];

//和已知節點構成最小權的節點

minIndex = j;

}

}

cout<<"節點："<<adjnode[minIndex]<<","<<minIndex<<endl;

//給lowcost指派0表示這個點已經被選取過,避開已選節點

//可以了解成按列排除

lowcost[minIndex] = 0;

for(int j=0;j!=n;j++){

//選擇已選節點到未選節點最小距離的點

if(lowcost[j]!=0&&graph[minIndex][j]<lowcost[j]){

lowcost[j] = graph[minIndex][j];

adjnode[j] = minIndex;

}

}

}

}

int main(){

int graph[4][4] = {{1,2,3,4},{M,M,M,M},{M,M,M,M},{M,M,M,M}};

prim(graph,4);

return 0;

}