prim演算法的初步瞭解

摘要： 先隨意選一個點作為起點 將各個與起點之間連通的點之中權值最小的那個與點加入到最小生成樹中 繼續遍歷與最小生成樹中的點權值最小的點（未加入最小生成樹的點），將它加入最小生成樹中 重複第三個步驟直到所有的點加入到最小生成樹中 與kruskal相比的優點 ...

• 先隨意選一個點作為起點
• 將各個與起點之間連通的點之中權值最小的那個與點加入到最小生成樹中
• 繼續遍歷與最小生成樹中的點權值最小的點（未加入最小生成樹的點），將它加入最小生成樹中
• 重複第三個步驟直到所有的點加入到最小生成樹中

與kruskal相比的優點

不用判斷加入的點是否會形成連通圖

演算法步驟

1. 將各個點之間的距離以無向圖的形式存在鄰接矩陣中。
2. 用一個一維陣列儲存起始點到各個點的距離。
3. 用一個標記陣列儲存各個點加入最小生成樹的狀態。
4. 用一個數組記錄當前節點是哪個節點連過來的。
5. 所謂貪心，就是每次都找到權值最小的那條邊（u,v）的v加入到最小生成樹中，加進去之後對標記陣列進行修改，表示該點已經加入到最小生成樹中。對v中的距離陣列進行更新，這裡的更新不是把原陣列中的所有資料都替換到新加入的點到所有的點的距離，而是與原先的點到同一個點（未加入）進行比較。倘若比原來的小則更新陣列資料，同時對4中的來源陣列進行更新，用來記錄最小生成樹，大於等於就跳過。迴圈n次（節點個數）後得到結果。

程式碼

#include<stdio.h>
#define N 6
#define MAX 100000
int a[N][N],result[N][N];

int main()
{
int flag[100] = { 0 };
int neighbor[100],distance[100];
int u, v, l;
//對資料進行初始化
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
a[i][j] = MAX;
}
scanf("%d%d%d", &u, &v, &l);
while (l != -1)
{
a[u][v] = l;
a[v][u] = l;
scanf("%d%d%d", &u, &v, &l);
}
for (int i = 0; i < N; i++)
{
neighbor[i] = 0;
distance[i] = a[0][i];
}
flag[0] = 1;//以第0個點為起點
for (int i = 1; i < N; i++)
{
int min = MAX;
for (int j = 0; j < N; j++)
{
if (!flag[j] && min>distance[j])
{
min = distance[j];
v = j;
}
}//找到距離最短那條邊，並把v加進最小生成樹
if (min < MAX)
{
flag[v] = 1;
result[neighbor[v]][v] = distance[v];
result[v][neighbor[v]] = distance[v];
for (int j = 0; j < N; j++)
{
//更新distance陣列,將距離小的加進去
if (!flag[j] && a[v][j] < distance[j])
{
distance[j] = a[v][j];
neighbor[j] = v;//更新來源
}

}
}
else break;
}
//將結果輸出
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf("%d ",result[i][j]);
putchar(10);//換行
}
return 0;
}
複製程式碼

測試資料

0 1 5
0 2 6
0 3 4
1 2 1
1 3 2
2 3 2
2 4 5
2 5 3
3 5 4
4 5 4
-1 -1 -1
複製程式碼