沉浸式寫代碼|最小生成數(shù)Prim算法|C語言實現(xiàn)
如果哪個地方有問題，請指出哈！！
我的代碼：
//最小生成樹和最短路徑有個小區(qū)別：
//前者是通過整個圖的最短距離，所以下面沒有給出起點和終點
//后者是給定任意兩點求最短距離，并不需要經(jīng)過整個圖
//下面敲敲Prim算法，跟dijsktra算法很像很像，但是在更新dist數(shù)組的時候，對象不一樣了
//并且針對的是無向圖，待會有一個點我之前一直犯錯，今天找出來了~~
#include<stdio.h>
#define INF 10000000//假裝是無窮大哈
#define MAX_SIZE 11//數(shù)組容量
int sum;//距離之和 全局變量默認初始化為0
int dist[MAX_SIZE];//距離數(shù)組
int visited[MAX_SIZE];//訪問數(shù)組 最小生成樹集合
int get = 1;
struct Graph
{
int vertex[MAX_SIZE];
int arc[MAX_SIZE][MAX_SIZE];
int vertexnum, arcnum;
};
void GraphCreate(struct Graph* graph)//鄰接矩陣存儲圖更方便實現(xiàn)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("請輸入有邊依附的兩個頂點編號以及權(quán)重：\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++)//在除源點外的頂點去找最小值，所以循環(huán)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在更新數(shù)組的時候像是折線跟直線去比較長短
//但這里是一個集合，一個圈圈，所以距離并不用加上前一個結(jié)點到當前結(jié)點的那段距離
}
}
}
if (get)
printf("最短距離為：%d\n", sum);
else
printf("失敗\n");
}
int main()
{
struct Graph graph;
printf("請輸入頂點個數(shù)和邊的個數(shù)：\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
