文章目录
1、用prim算法求最小生成树
绿色线会标记选过的边
从v1当作起始点开始，可选择:
(v1,v2)权值为6
（v1,v3）权值为3
（v1，v4）权值为1
从中选择边（v1，v4），最小权值为1
从v1和v4中选连接边，可选择的边有：
（v1，v2）权值为6
（v1,v3）权值为3
（v4，v3）权值为2
（v4，v5）权值为10
从中选择权值最小为2的边，（v4，v3）
v1，v4，v3已经被标记不能相互连接，避免产生回路，从v1、v4、v3中可选择的边有：
（v1，v2）权值为6
（v4，v5）权值为10
（v3，v2）权值为2
从中选择权值最小为2的边，（v3，v2）
从v1,v4,v3,v2中可选择的边有：
（v2，v9）权值为1
（v4，v5）权值为10
从中选择权值最小1的边，（v2，v9）
从v1，v4，v3，v2，v9中可选边有：
（v4，v5）权值为10
（v9，v5）权值为 6
（v9，v6）权值为 4
（v9，v7）权值为 3
（v9，v8）权值为 2
从中选择权值最小2的边，（v9，v8）
从v1，v4，v3，v2，v9，v8中可选边有：
（v4，v5）权值为10
（v9，v5）权值为 6
（v9，v6）权值为 4
（v9，v7）权值为 3
（v8，v7）权值为 3
从中有两条权值为3的边，任选一条（v8，v7）
从v1，v4，v3，v2，v9，v8，v7中可选边有：
（v4，v5）权值为10
（v9，v5）权值为 6
（v9，v6）权值为 4
（v7，v6）权值为 4
从两条权值为4的边，任选一条（v7，v6）
从v1，v4，v3，v2，v9，v8，v7，v6中可选边有：
（v4，v5）权值为10
（v9，v5）权值为 6
（v6，v5）权值为 2
选择最小权值为2的边（v6，v5）
v1，v4，v3，v2，v9，v8，v7，v6，v5所有点被标记
最小生成树找到，总权值为17
C语言Prim算法实现
#include<stdio.h>
#define M 1000//M表示无穷用1000代替
//判断标记点的函数，避免产生回路
int Is(int arr[9], int flag)
{
int i = 0;
for (i = 0; i < 9; i++)
{
if (arr[i] == flag)
return 0;
}
return 1;
}
int main()
{
//把上图权值对应值写成邻接阵
int map[9][9] =
{
{M,6,3,1,M,M,M,M,M},
{6,M,2,M,M,M,M,M,1},
{3,2,M,2,M,M,M,M,M},
{1,M,2,M,10,M,M,M,M},
{M,M,M,10,M,2,M,M,6},
{M,M,M,M,2,M,4,M,4},
{M,M,M,M,M,4,M,3,3},
{M,M,M,M,M,M,3,M,2},
{M,1,M,M,6,4,3,2,M}
};
//存放被标记的点
int arr[9] = { 1 };//设置初始点为V1，只有V1被标记
//记录标记个数
int count = 1;
//存放权值总和
int s = 0;
//循环变量
int i = 0;
//记录最小权下标
int index = 0;
//记录最小权
int min = M;
//记录点
int doc = 1;
//循环部分：
while (1)
{
min = M;
for (i = 0; i < count; i++)
{
int j = 0;
int c = arr[i] - 1;
for (j = 0; j < 9; j++)
{
if (map[c][j] <= min && Is(arr, j + 1))
{
doc = c + 1;
min = map[c][j];
index = j;
}
}
}
s += min;
arr[count++] = index + 1;
//打印
printf("V%d --> V%d ", doc, index + 1);
//所有点被标记，跳出循环
if (count == 9)
break;
}
printf("\n总权值为：%d\n", s);
return 0;
}
运行结果:
2、用Prim-Alternate算法求最小生成树
Prim-Alternate算法是Prim算法的优化
Prim-Alternate算法是只找当前标记点和上一个标记点的邻边
被标记的点不能互相相连
3、C语言Prim-Alternate算法实现
//Prim-Alternate算法
#include<stdio.h>
#define M 1000//M表示无穷用1000代替
//判断标记点的函数，避免产生回路
int Is(int arr[9], int flag)
{
int i = 0;
for (i = 0; i < 9; i++)
{
if (arr[i] == flag)
return 0;
}
return 1;
}
int main()
{
//把上图权值对应值写成邻接阵
int map[9][9] =
{
{M,6,3,1,M,M,M,M,M},
{6,M,2,M,M,M,M,M,1},
{3,2,M,2,M,M,M,M,M},
{1,M,2,M,10,M,M,M,M},
{M,M,M,10,M,2,M,M,6},
{M,M,M,M,2,M,4,M,4},
{M,M,M,M,M,4,M,3,3},
{M,M,M,M,M,M,3,M,2},
{M,1,M,M,6,4,3,2,M}
};
//存放被标记的点
int arr[9] = { 1 };//设置初始点为V1，V1被标记
//记录标记个数
int count = 1;
//存放权值总和
int s = 0;
//循环变量
int i = 0;
//记录最小权下标
int index = 0;
//记录最小权
int min = M;
//记录点
int doc = 1;
int c = 0;
//循环部分：
while(1)
{
min = M;
//每次循环只找两个标记点相邻的边
for(i=count-2;i< count ;i++)
{
int j = 0;
if (count == 1)
c = arr[0] - 1;
else
c = arr[i] - 1;
for (j = 0; j < 9; j++)
{
if (map[c][j] <= min && Is(arr, j + 1))
{
doc = c+1;
min = map[c][j];
index = j;
}
}
}
s += min;
arr[count++] = index + 1;
//打印
printf("V%d --> V%d ",doc , index + 1);
//所有点被标记，跳出循环
if (count == 9)
break;
}
printf("\n总权值为：%d\n", s);
return 0;
}
运行结果：
