Ⅰ 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;
}
}
//希望對你有所幫助