题目描述
根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。（假设：输入数据的最小生成树唯一。）
输入
顶点数n
n个顶点
边数m
m条边信息,格式为：顶点1 顶点2 权值
Prim算法的起点v
输出
输出最小生成树的权值之和
对两种算法，按树的生长顺序，输出边信息(Kruskal中边顶点按数组序号升序输出)
样例输入
6
v1 v2 v3 v4 v5 v6
10
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v3 v4 5
v3 v5 6
v3 v6 4
v4 v6 2
v5 v6 6
v1
样例输出
15
prim:
v1 v3 1
v3 v6 4
v6 v4 2
v3 v2 5
v2 v5 3
kruskal:
v1 v3 1
v4 v6 2
v2 v5 3
v3 v6 4
v2 v3 5
普里姆算法更新lowcost数组的值
#include<iostream> using namespace std; struct{ string adjvex; int lowcost; }closedge[100]; class MGraph { public: int graph[100][100],graph1[100][100]; int n,len; //n 是节点个数 len是边的数 int visited[100],low[100]; string *q;//存节点 string start; int startpos; MGraph(){}; void SetMGraph() { int i,j; cin>>n; for(i=0;i<100;i++) for(j=0;j<100;j++) { graph[i][j]=10000; //将每个权值置为最大 graph1[i][j]=10000; } q=new string[n]; for(i=0;i<n;i++) cin>>q[i]; cin>>len; for(i=1;i<=len;i++) { string ch1,ch2; int weight; cin>>ch1>>ch2>>weight; int loc1,loc2; for(j=0;j<n;j++) { if(q[j]==ch1) loc1=j; if(q[j]==ch2) loc2=j; } graph1[loc1][loc2]=graph[loc1][loc2]=weight; graph1[loc1][loc2]=graph[loc2][loc1]=weight;//无向图 } cin>>start; for(i=0;i<n;i++) if(q[i]==start) startpos=i; } void prim() { int i,j; for(i=1;i<=n;i++) visited[i]=0; visited[startpos]=1; int min; for(i=0;i<n;i++) { min=99999; for(j=0;j<n;j++) { if(graph[i][j]<min) { min=graph[i][j]; closedge[i].adjvex=q[j]; closedge[i].lowcost=min; } } } string s3; string *e1,*e2; int *w3; e1=new string[100]; e2=new string[100]; w3=new int[100]; int index,k=0; for(i=0;i<n;i++) { min=99999; for(j=0;j<n;j++) { if(!visited[j]) continue; else { if(min>closedge[j].lowcost) { min=closedge[j].lowcost; s3=closedge[j].adjvex; index=j; } } } e1[k]=q[index];e2[k]=s3,w3[k++]=min; for(int g=0;g<n;g++) { if(q[g]==s3) { visited[g]=1; // graph[index][g]=99999; // graph[g][index]=99999; break; } } for(int g=0;g<n;g++) { min=99999; for(int m=0;m<n;m++) { if(min>graph[g][m] && visited[m]==0) { min=graph[g][m]; closedge[g].adjvex=q[m]; closedge[g].lowcost=min; } } } } int weight=0; for(i=0;i<k-1;i++) { weight+=w3[i]; } cout<<weight<<endl; cout<<"prim:"<<endl; for(i=0;i<k-1;i++) cout<<e1[i]<<" "<<e2[i]<<" "<<w3[i]<<endl; } void kruskal() { cout<<"kruskal:"<<endl; int *uni=new int[n]; for(int i=0;i<n;i++) { uni[i]=i; } for(int i=0;i<n-1;i++) { int min=99999;int x,y; for(int j=0;j<n;j++) { for(int l=0;l<n;l++) { if(j==l) continue; if(uni[j]==uni[l]) continue; else { if(min>graph1[j][l]) { min=graph1[j][l]; x=j;y=l; } } } } graph1[x][y]=10000;graph1[y][x]=10000; if(x>y) int k;k=x;x=y;y=k; for(int i=0;i<n;i++) { if(uni[i]==uni[y]&&i!=y) uni[i]=uni[x]; } uni[y]=uni[x]; cout<<q[x]<<" "<<q[y]<<" "<<min<<endl; } } void show() { int i,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) cout<<graph[i][j]<<" "; cout<<endl; } } }; int main() { MGraph m,M; m.SetMGraph(); m.prim(); m.kruskal(); }