沉浸式写代码|最小生成数Prim算法|C语言实现
如果哪个地方有问题，请指出哈！！
我的代码：
//最小生成树和最短路径有个小区别：
//前者是通过整个图的最短距离，所以下面没有给出起点和终点
//后者是给定任意两点求最短距离，并不需要经过整个图
//下面敲敲Prim算法，跟dijsktra算法很像很像，但是在更新dist数组的时候，对象不一样了
//并且针对的是无向图，待会有一个点我之前一直犯错，今天找出来了~~
#include<stdio.h>
#define INF 10000000//假装是无穷大哈
#define MAX_SIZE 11//数组容量
int sum;//距离之和 全局变量默认初始化为0
int dist[MAX_SIZE];//距离数组
int visited[MAX_SIZE];//访问数组 最小生成树集合
int get = 1;
struct Graph
{
int vertex[MAX_SIZE];
int arc[MAX_SIZE][MAX_SIZE];
int vertexnum, arcnum;
};
void GraphCreate(struct Graph* graph)//邻接矩阵存储图更方便实现Prim算法哈
{
for (int i = 1; i <= graph->vertexnum; i++)//初始化
{
for (int j = 1; j <= graph->vertexnum; j++)
{
graph->arc[i][j] = graph->arc[j][i] = INF;//无向图！
}
dist[i] = INF;
visited[i] = 0;//顺便在这里一块初始化啦！！
}
int a = 0, b = 0, w = 0;
for (int i = 1; i <= graph->arcnum; i++)
{
printf("请输入有边依附的两个顶点编号以及权重：\n");
scanf("%d%d%d", &a, &b, &w);
graph->arc[a][b] = graph->arc[b][a] = w;//这里写一半会有大问题！！待会给大家演示一下！！
}
}
void Prim(struct Graph* graph)
{
visited[1] = 1;//从顶点1开始遍历，先定义以及访问了
for (int i = 1; i <= graph->vertexnum; i++)
{
dist[i] = graph->arc[1][i];
}
for (int i = 1; i < graph->vertexnum; i++)//在除源点外的顶点去找最小值，所以循环n-1次~~
{
int min = INF;
int pos = -1;//是不是跟dijsktra很像！？
for (int j = 1; j <= graph->vertexnum; j++)
{
if (!visited[j] && dist[j] < min)
{
min = dist[j];
pos = j;
}
}
if (pos == -1)
{
printf("找不到了，退退退！！！\n");
get = 0;
return;
}
visited[pos] = 1;//找到了 差点放错了~~
sum += dist[pos];
for (int j = 1; j <= graph->vertexnum; j++)
{
if (!visited[j] && graph->arc[pos][j] < dist[j])
{
dist[j] = graph->arc[pos][j];
//这里就是我说的对象不一样，我觉得dijsktra在更新数组的时候像是折线跟直线去比较长短
//但这里是一个集合，一个圈圈，所以距离并不用加上前一个结点到当前结点的那段距离
}
}
}
if (get)
printf("最短距离为：%d\n", sum);
else
printf("失败\n");
}
int main()
{
struct Graph graph;
printf("请输入顶点个数和边的个数：\n");
scanf("%d%d", &graph.vertexnum, &graph.arcnum);
GraphCreate(&graph);
Prim(&graph);
return 0;
}
测试用例：
6 9
1 2 34
1 3 46
1 6 19
2 5 12
3 6 25
3 4 17
4 6 25
4 5 38
5 6 26
答案：99
