（prim算法题型一）求最小生成树的权值和、路径、边值的最小和最大值。
比较优秀的矩阵类型prim算法：
#include "stdio.h"
#include "string.h"
#define N 500
#define INT 10000
bool vis[N];
int dis[N];
int a[N][N];
int main(){
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
int i,j,temp,k;
memset(vis,0,sizeof(vis));
for(i=1;
i<=n;
++i){
for(j=1;
j<=n;
++j){
scanf("%d", &a[i][j]);
}
}
for(i=1;
i<=n;
++i){
dis[i]=INT;
}
dis[1]=0;
for(i=1;
i<=n;
++i){
temp=INT;
k=0;
for(j=1;
j<=n;
++j){
if(!vis[j]&&dis[j]
k=j;
}
}
vis[k]=1;
for(j=1;
j<=n;
++j){
if(!vis[j]&&dis[j]>a[k][j]){
dis[j]=a[k][j];
}
}
}
int max=0;
for(i=1;
i<=n;
++i){
if(max
}
printf("%d\n",max);
}
return 0;
}
/*
2
3
0 990 692
990 0 179
692 179 0
*/
1.输出最小生成树个边权值累加和
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
#include
#include
#define MaxInt 0x3f3f3f3f
#define N 110
//创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问
int map[N][N],low[N],visited[N];
int n;
int prim()
{
int i,j,pos,min,result=0;
memset(visited,0,sizeof(visited));
//从某点开始，分别标记和记录该点
visited[1]=1;
pos=1;
//第一次给low数组赋值
for(i=1;
i<=n;
i++)
if(i!=pos) low[i]=map[pos][i];
//再运行n-1次
for(i=1;
i
//找出最小权值并记录位置
min=MaxInt;
for(j=1;
j<=n;
j++)
if(visited[j]==0&&min>low[j])
{
min=low[j];
pos=j;
}
//最小权值累加
result+=min;
//标记该点
visited[pos]=1;
//更新权值
for(j=1;
j<=n;
j++)
if(visited[j]==0&&low[j]>map[pos][j])
low[j]=map[pos][j];
}
return result;
}
int main()
{
int i,v,j,ans;
while(scanf("%d",&n)!=EOF)
{
//所有权值初始化为最大
memset(map,MaxInt,sizeof(map));
for(i=1;
i<=n;
i++)
for(j=1;
j<=n;
j++)
{
scanf("%d",&v);
map[i][j]=map[i][j]=v;
}
ans=prim();
printf("%d\n",ans);
}
return 0;
}
2、求出最小生成树中边的最大值。
1
3
0 990 692
990 0 179
692 179 0
692
#include
#define MAX 505
#define inf 999999
int c[MAX][MAX];
int n;
void prim()
{
int lowcost[MAX ];
int closest[MAX ];
bool s[MAX ];
s[1]=true;
for(int i=2;
i<=n;
i++)
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
for(int i=1;
i<=n;
i++)
{
int min=inf;
int j=i;
for(int k=2;
k<=n;
k++)
if((lowcost[k]
min=lowcost[k];
j=k;
}
//cout<
s[j]=true;
for(int k=2;
k<=n;
k++)
{
if((c[j][k]
lowcost[k]=c[j][k];
closest[k]=j;
}
}
}
//最小生成树的边值已经放大lowcost数组中了。遍历一下就可以得到最大最小值。
int result=-1;
for(int i=2;
i<=n;
i++)
{
if(result
}
printf("%d\n",result);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;
i<=n;
i++)
{
for(intj=1;
j<=n;
j++)
{
scanf("%d",&c[i][j]);
}
}
prim();
}
return 0;
}
【（prim算法题型一）求最小生成树的权值和、路径、边值的最小和最大值。】
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法