Agri-Net(prim算法,最小生成树问题)
Agri-Net(prim算法,最小生成树问题)
1944864971 发表于2年前
Agri-Net(prim算法,最小生成树问题)
  • 发表于 2年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

看图便知道:

 

来来上代码:
 
 
 
 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;


int main()
{
int n;
while(~scanf("%d",&n))
{
int tu[n+1][n+1];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&tu[i][j]);
int V[n+1];//存放生成的节点
for(int i=1; i<=n; i++)
V[i]=tu[1][i];//先初始化,别急,后面的会变的
bool op[n+1];//标记此节点是否访问过
memset(op,true,sizeof(op));
int sum=0;
op[1]=false;
for(int i=1; i<n; i++)//n-1条边
{
int j=0,k;




/*for(j=1; j<=n; j++)
cout<<V[j]<<" ";
cout<< "~~~~";
for(j=1; j<=n; j++)
cout<<op[j]<<" ";
cout<<endl;*/

 

 

int min=0x3f3f3f3f;
int flag=0;
for(int j=1; j<=n; j++)
if( op[j]&&V[j]<min)//找节点中权值最小的并且是没有找过的
{
min=V[j];
flag=j;//记录下来
}


/*system("pause");
cout<<"min="<<min<<" flag="<<flag<<endl;*/



op[flag]=false;//此节点已经访问过
sum+=min;//加起来


/*for(j=1; j<=n; j++)
cout<<V[j]<<" ";
cout<< "~~~~";
for(j=1; j<=n; j++)
cout<<op[j]<<" ";
cout<<endl;*/



for(j=1; j<=n; j++)
if(op[j]&&tu[flag][j]<V[j])//在刚才找的节点后面继续找此节点后面权值的最小的节点

{
V[j]=tu[flag][j];//放到最生成树的节点中
k=j;
}




/*system("pause");

cout<<endl;
cout<< "V[k]="<< V[k]<<endl;
}*/



printf("%d\n",sum);
}
return 0;
}

/*
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
 
*/
 
 
/*

6
0 6 1 5 7 5
6 0 5 10 3 9
1 5 0 5 6 4
5 10 5 0 8 2
7 3 6 8 0 6
5 9 4 2 6 0

 
*/
 
 
 
 
 
 
 
 
 
 
 
 
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: