Prim
算法的时间为:O(V lgV +E lgV )=O(E lgV )。
➢ 从渐进意义上看,Kruskal和Prim算法具有相同的运行时间。
代码
/*
*二维数组graph[V][V]记录图
*通过维护一维数组key[V],其含义为:
*当前MST到第i个点的所有边中,权重最小为key[i]。
*每次加入一维数组key[V]中值最小的点
*/
#include<limits.h>
#include<stdbool.h>
#include<stdio.h>
#define V 5
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX;
int min_index;
for (int v = 0; v < V; v++) {
//printf("%d ", key[v]);
if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}
}
//printf("
");
return min_index;
}
void printMST(int parent[], int graph[V][V]) {
printf("Edge Weight
");
for (int i = 1; i < V; i++) {
printf("%d -> %d %d
", parent[i], i, graph[i][parent[i]]);
}
}
void primMST(int graph[V][V]) {
int parent[V]; //MST中的边:parent[i]-->i
int key[V]; //最小切割
bool mstSet[V]; //点是否在MST中
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0; //0节点为MST根
parent[0] = -1;
/*-----核心结构-----*/
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
//加入新点
mstSet[u] = true;
//维护数组key[]
for (int v = 0; v < V; v++) {
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
/*---------------*/
printMST(parent, graph);
}
int main() {
//一个栗子
int graph[V][V] = { {0,2,0,6,0},
{2,0,3,8,5},
{0,3,0,0,7},
{6,8,0,0,9},
{0,5,7,9,0} };
primMST(graph);
return 0;
}