一，prim算法邏輯
1.理解：克魯斯卡爾算法關注的是邊，普里姆算法關注的是點
把圖中每個頂點比作孤島，點亮一座孤島就可以解鎖附近的孤島
每次解鎖的點都是離自身最近的點
?2.普里姆算法流程
a.采用鄰接矩陣表示，考慮要查找最小值，初始化不存在的邊的值為INF
b.準備工作
cost邊的權值數組，保存到該條邊的權值
mark標記已訪問的點
visit從哪個頂點訪問過來的
c.執行操作
任意找到一個激活點，更新三個數組
從cost數組找到權值最小的頂點，激活該頂點
在邊集數組中保存visit和當前節點的編號，以及權值
重復c操作
二，代碼實現
1.頭文件中的接口
//
// Created by 27893 on 2025/8/1.
//#ifndef PRIM_H
#define PRIM_H
#include "common.h"
#include "../MatrixGraph/MatrixGraph.h"int primMGraph(MGraph*graph,int startV,EdgeSet*result);
#endif //PRIM_H
//
// Created by 27893 on 2025/8/1.
//#ifndef COMON_H
#define COMON_H
typedef struct {int begin;int end;int weight;
}EdgeSet;
#endif //COMON_H
2.將頭文件中的接口一一實現
//
// Created by 27893 on 2025/8/1.
//#include <stdio.h>
#include <stdlib.h>
#include "Prim.h"int primMGraph(MGraph *graph, int startV, EdgeSet *result) {int*cost=malloc(sizeof(int)*graph->nodeNum);int*mark=malloc(sizeof(int)*graph->nodeNum);int*visit=malloc(sizeof(int)*graph->nodeNum);if (cost==NULL||mark==NULL||visit==NULL) {return 0;}int sum=0;//初始化激活startvfor (int i=0;i<graph->nodeNum;i++) {cost[i]=graph->edges[startV][i];mark[i]=0;if (graph->edges[startV][i]<INF) {visit[i]=startV;}else {visit[i]=i;}}mark[startV]=1;for (int i=0;i<graph->nodeNum-1;i++) {//1.在cost找到最小值int k=0,mini=INF;for (int j=0;j<graph->nodeNum;j++) {if (mark[j]==0&&cost[j]<mini) {mini=cost[j];k=j;}}//2.更新邊集數組result[i].begin=visit[k];result[i].end=k;result[i].weight=mini;mark[k]=1;sum+=mini;//3.更新cost數組for (int j=0;j<graph->nodeNum;j++) {if (mark[j]==0&&graph->edges[k][j]<cost[j]) {cost[j]=graph->edges[k][j];visit[j]=k;}}}free(cost);free(mark);free(visit);return sum;
}
3，測試是否有bug
//
// Created by 27893 on 2025/7/31.
//
#include <stdio.h>
#include <stdlib.h>#include "Kruskal.h"
#include "Prim.h"void setupMGraph01(MGraph *graph, int edgeValue) {const char *names[] = {"A", "B", "C", "D", "E", "F", "G"};initMGraph(graph, names, 7, 0, edgeValue);addMGraph(graph, 0, 1, 12);addMGraph(graph, 0, 5, 16);addMGraph(graph, 0, 6, 14);addMGraph(graph, 1, 2, 10);addMGraph(graph, 1, 5, 7);addMGraph(graph, 2, 3, 3);addMGraph(graph, 2, 4, 5);addMGraph(graph, 2, 5, 6);addMGraph(graph, 3, 4, 4);addMGraph(graph, 4, 5, 2);addMGraph(graph, 4, 6, 8);addMGraph(graph, 5, 6, 9);
}
void test01() {MGraph graph;EdgeSet*edges;int num;EdgeSet*result;int sumweight;setupMGraph01(&graph,0);edges=malloc(sizeof(EdgeSet)*graph.edgeNum);num=initEdgeSet(&graph,edges);printf("edges num:%d\n",num);sortEdgeSet(edges,num);result=malloc(sizeof(EdgeSet)*graph.nodeNum-1);sumweight=kruskalMGraph(&graph,edges,num,result);printf("sumweight:%d\n",sumweight);for (int i=0;i<graph.nodeNum-1;i++) {printf("edges[%d]:%s----%d----%s\n",i+1,graph.vex[result[i].begin].show,result[i].weight,graph.vex[result[i].end].show);}
}
void test02() {MGraph graph;setupMGraph01(&graph,INF);EdgeSet*result;result=malloc(sizeof(EdgeSet)*(graph.nodeNum-1));int sum=primMGraph(&graph,0,result);printf("sumWeight:%d\n",sum);for (int i=0;i<graph.nodeNum-1;i++) {printf("edges[%d]:%s----%d----%s\n",i+1,graph.vex[result[i].begin].show,result[i].weight,graph.vex[result[i].end].show);}
}
int main() {test01();test02();return 0;
}
)
