有点混乱的普里姆算法求最小生成树
#include"Graph.h"
//无向带权图
//#########(普里姆算法求最小生成树)#################
//返回最小权值邻接边的点的下标
int minKey(int key[], int mstSet[], Graph* G)//key数组是用来存最小边权值的数组
//mstSet 是在普里姆(Prim)算法中使用的一个辅助数组，全称可以理解为 "Minimum Spanning Tree Set"，即“最小生成树集合”
{
int min = INF;
int min_index = 0;//用于记录邻接最小权值边终点的下标
for (int i = 0; i < G->n; i++)
{
if (mstSet[i] == 0 && key[i] < min)
//如果该点没有被加入最小生成树集合并且存在边的话则将其边权值赋给min并且将其下标赋给min_index
{
min = key[i];
min_index = i;
}
}
return min_index;
}
//打印最小生成树
void PrintMST(int parent[], Graph* G)
{
printf("最小生成树构成：\n");
for (int i = 1; i < G->n; i++)//i要从1开始，因为第一个顶点没有前驱节点
{
printf("边<%c,%c>权为:%d\n", G->vertex[parent[i]], G->vertex[i], G->edges[parent[i]][i]);
}
}
//打印最小生成树
void PrintMST2(int parent[], Graph* G,int sequence[])
{
printf("最小生成树构成：\n");
for (int i = 0; i < G->n-1; i++)//这里是要小于n-1,因为sequence里有n-1个节点
{
printf("边<%c,%c>权为:%d\n", G->vertex[parent[sequence[i]]],G->vertex[sequence[i]],G->edges[parent[sequence[i]]][sequence[i]]);
}
}
//完整普里姆算法
void PrimMST(Graph* G)
{
int parent[MAX] = {0};//用于记录最小生成树的路径
int key[MAX];
int mstSet[MAX];
//先初始化好key数组和mstSet数组
for (int i = 0; i < G->n; i++)
{
key[i] = INF;
mstSet[i] =0;//均设为0表示均未被加入最小生成树集合
}
//一开始都做好了初始化，但为了能达到循环进行的目的要先对第一个点进行特殊处理
key[0] = 0;// 从顶点0开始构造最小生成树
parent[0] = -1;//因为最小生成树的第一个顶点没有父母节点
int sequence[MAX];//用于记录顺序
int j = 0;
int n = 0;//n用于计数
for (int i = 0; i < G->n-1; i++)
//i用于循环控制次数，条件为小于顶点数减一，因为每次处理都可简化为存父节点和找邻接最小边，而最小生成树是前n-1个顶点为父节点
{
int u = minKey(key, mstSet, G);//u用于存储邻接最小边点的下标
mstSet[u] = 1;//将该点标记为已加入最小生成树集中
n++;
if (u != 0)
{
sequence[j++] = u;
}
//找下一个邻接最小权值边的顶点，设好其前驱节点即 // 更新相邻顶点的key值和parent值
for (int i = 0; i < G->n; i++)
{
if (G->edges[u][i] && mstSet[i] == 0 && G->edges[u][i] < key[i])
//若边不是指向自身并且点没有被加入到最小生成树集合中并且存在边
{//则设好其父母结点并将边权值赋值给key[i]
parent[i] = u;
key[i] = G->edges[u][i];//赋值好所有相邻边的权值
}
}
}
//这部分用于判断哪个顶点不存在于sequence数组中，把它找出来，就是最后一个顶点。再加入到sequence中
int temp;
int flag = 0;
for (int i = 1; i < G->n; i++)
{
int n = 0;
for (int j = 0; j < G->n - 1; j++)
{
if (sequence[j] == i)
{
break;
}
else
{
n++;
}
if (n == G->n - 1)
{
temp = i;
flag = 1;
break;
}
}
if (flag == 1)
{
break;
}
}
sequence[j] = temp;
//把最小生成树的最后一个结点加入到顺序数组中
PrintMST2(parent, G,sequence);
}
int main(int argc, char* argv[])
{
Graph*G;
CreateGraph(G,7);
char V[8] = "ABCDEFG";
for (int i = 0; i < G->n; i++)
{
G->vertex[i] = V[i];//将顶点存进图中
}
G->edges[get_pos(G, 'A')][get_pos(G, 'B')] = 50;
G->edges[get_pos(G, 'B')][get_pos(G, 'A')] = 50;
G->edges[get_pos(G, 'B')][get_pos(G, 'D')] = 65;
G->edges[get_pos(G, 'D')][get_pos(G, 'B')] = 65;
G->edges[get_pos(G, 'A')][get_pos(G, 'C')] = 60;
G->edges[get_pos(G, 'C')][get_pos(G, 'A')] = 60;
G->edges[get_pos(G, 'C')][get_pos(G, 'D')] = 52;
G->edges[get_pos(G, 'D')][get_pos(G, 'C')] = 52;
G->edges[get_pos(G, 'D')][get_pos(G, 'G')] = 42;
G->edges[get_pos(G, 'G')][get_pos(G, 'D')] = 42;
G->edges[get_pos(G, 'C')][get_pos(G, 'G')] = 45;
G->edges[get_pos(G, 'G')][get_pos(G, 'C')] = 45;
G->edges[get_pos(G, 'B')][get_pos(G, 'E')] = 40;
G->edges[get_pos(G, 'E')][get_pos(G, 'B')] = 40;
G->edges[get_pos(G, 'D')][get_pos(G, 'E')] = 50;
G->edges[get_pos(G, 'E')][get_pos(G, 'D')] = 50;
G->edges[get_pos(G, 'D')][get_pos(G, 'F')] = 30;
G->edges[get_pos(G, 'F')][get_pos(G, 'D')] = 30;
G->edges[get_pos(G, 'E')][get_pos(G, 'F')] = 70;
G->edges[get_pos(G, 'F')][get_pos(G, 'E')] = 70;
PrintGraph(G);
PrimMST(G);
DestroyGraph(G);
return 0;
}