Ⅰ c语言 数据结构编程 图状结构的应用
#include <iostream>
#include <fstream>
using namespace std;
class edgeset{
public:
int from;//边起始点
int end;//边终止点
int w;//边的权值
};//定义一个类用来存放图的边的信息（kruskal算法中用到）
//==============prim算法=============================
void prim(int a[11][11],int (&path)[11][11]){
cout<<"运用prim算法"<<endl;
int i,j,k;
int mini,minj,min,sum=0;
a[0][0]=-1;
cout<<"通道铺设情况：(0-10分别对应点a-k)"<<endl;
for(k=1;k<11;k++){
min=100;
for(i=0;i<11;i++){
for(j=0;j<11;j++){
if(a[i][i]+a[j][j]==-1 && a[i][j]>0 && a[i][j]<min){
min=a[i][j];
mini=i;
minj=j;
}
}
}
if(a[mini][mini]==-1){
cout<<"("<<mini<<","<<minj<<")";
path[mini][minj]=a[mini][minj];
path[minj][mini]=a[mini][minj];
a[minj][minj]=-1;
}
else{
cout<<"("<<mini<<","<<minj<<")";
path[mini][minj]=a[mini][minj];
a[mini][mini]=-1;
path[minj][mini]=a[mini][minj];
}
sum=sum+min;
}
cout<<endl;
cout<<"建设费用为:"<<sum<<endl;
//=============最小生成树的邻接矩阵输出==============
cout<<"最小生成树对应的邻接矩阵为："<<endl;
for(int x=0;x<11;x++){
for(int y=0;y<11;y++){
cout<<path[x][y]<<" ";
}
cout<<endl;
}
}
//===================================================
//===========kruskal算法=============================
void kruskal(int a[11][11],int(&kpath)[11][11]){
cout<<"运用kruskal算法"<<endl;
int i,j,k,d;
int num=0;
edgeset edge[18];
//将邻接矩阵中权值大于1的边对应的点及权值存到一个边类
for(i=0;i<11;i++){
for(j=i+1;j<11;j++){
if(!a[i][j]==0){
edge[num].from=i;
edge[num].end=j;
edge[num].w=a[i][j];
num++;
}
}
}
edgeset tmp;
//===================================================
//=======将边按权值大小排序==========================
for(i=1;i<18;i++){
for(j=0;j<18-i;j++){
if(edge[j].w>edge[j+1].w){
tmp=edge[j];
edge[j]=edge[j+1];
edge[j+1]=tmp;
}
}
}
//===================================================
int m1,m2;
edgeset c[11];
int s[11][11];
for(i=0;i<11;i++)
for(j=0;j<11;j++){
if(i==j)
s[i][j]=1;
else
s[i][j]=0;
}
k=1;
d=0;
int sum=0;
cout<<"通道铺设情况：(0-10分别对应点a-k)"<<endl;
while(k<11){
for(i=0;i<11;i++){
if(s[i][edge[d].from]==1)
m1=i;
if(s[i][edge[d].end]==1)
m2=i;
}
if(m1!=m2){
c[k-1]=edge[d];
cout<<"("<<c[k-1].from<<","<<c[k-1].end<<")";
kpath[c[k-1].from][c[k-1].end]=c[k-1].w;
kpath[c[k-1].end][c[k-1].from]=c[k-1].w;
sum=sum+c[k-1].w;
k++;
for(j=0;j<11;j++){
if(s[m2][j]!=0){
s[m1][j]=s[m2][j];
s[m2][j]=0;
}
}
}
d++;
}
cout<<endl;
cout<<"建设费用为："<<sum<<endl;
//=============最小生成树的邻接矩阵输出==============
cout<<"最小生成树对应的邻接矩阵为："<<endl;
for(int x=0;x<11;x++){
for(int y=0;y<11;y++){
cout<<kpath[x][y]<<" ";
}
cout<<endl;
}
}
void main(){
int h,z;
int a[11][11];
int path[11][11]={0};
//==============数据读入（图的邻接矩阵）=============
ifstream in("picture.txt");
for(h=0;h<11;h++){
for(z=0;z<11;z++){
in>>a[h][z];
}
}
//===================================================
cout<<"图的邻接矩阵："<<endl;
for(int i=0;i<11;i++){
for(int j=0;j<11;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
int kpath[11][11]={0};
int b[11][11];
ifstream in2("picture.txt");
for(h=0;h<11;h++){
for(z=0;z<11;z++){
in2>>b[h][z];
}
}
int ch;
cout<<"请选择算法(1:prim算法/2:kruskal算法):";
cin>>ch;
cout<<endl;
switch(ch){
case 1:prim(a,path);//调用prim算法函数
break;
case 2:kruskal(b,kpath);
break;
}
}
//希望对你有所帮助