一个图的深度优先生成树和广度优先生成树唯一吗
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/26 03:56:59
一个图的深度优先生成树和广度优先生成树唯一吗
一个图的深度优先生成树和广度优先生成树唯一吗
一个图的深度优先生成树和广度优先生成树唯一吗
最小生成树:
#include<iostream>
using namespace std;
#define inf 99999;
template<class Type>
Type Prim(int n,Type **c){
Type lowcost[n],sum=0;
// int closest[n];
bool s[n];
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++){
Type min=inf;
int j=1;
for(int k=2;k<=n;k++)
if((lowcost[k]<min)&&(!s[k])){
min=lowcost[k];
j=k;
}
// cout<<j<<' '<<closest[j]<<endl;
sum+=lowcost[j];
s[j]=true;
for(int k=2;k<=n;k++){
if((c[j][k]<lowcost[k])&&(!s[k])){
lowcost[k]=c[j][k];
// closest[k]=j;
}
}
}
return sum;
}
int main(){
int T,n,m,**c;
cin>>T;
while(T--){
cin>>n>>m;
c=new int*[n+1];
for(int i=1;i<=n;i++){
c[i]=new int[n+1];
for(int j=1;j<=n;j++)
c[i][j]=inf;
}
while(m--){
int x,y,w;
cin>>x>>y>>w;
c[x][y]=w;
}
cout<<Prim(n,c)<<endl;
}
// system("pause");
return 0;
}