最小生成树算法实验报告(共6页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
最小生成树算法
问题描述
设G=(V,d Prim(RCW CT[],int n);
//检查输入的边序号是否越界,若越界则重输
void Check(int n, int& i, int& j);
};

// 杨松
#include""
//构造函数,初始化图的邻接矩阵与边集数组
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
adjMList::adjMList(RCW GE[],int n,int e)
{int i,j;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(i==j) GA[i][j]=0;
else GA[i][j]=MaxValue;
for(i=0;i<e;i++) GE[i].weight=0;
numE=0;
}
//输出边集数组中的每条边
void adjMList::OutputEdgeSet(RCW ge[],int e)
{int i,k=0;
cout<<"{";
for(i=0; i<=e-2; i++)
if(ge[i].weight>0){k++;
cout<<'('<<ge[i].row<<','<<ge[i].col;
cout<<','<<ge[i].weight<<") ";
if(k%5==0) cout<<endl;}
if(e>0&&ge[i].weight>0) {
cout<<'('<<ge[e-1].row<<','<<ge[e-1].col;
cout<<','<<ge[e-1].weight<<')';}
cout<<'}'<<endl;
}
//建立无向带权图的邻接矩阵
void adjMList::CreateMatrix(int n,int &e,RCW r[])
{int i,j,k=0,w;
cout<<"依次输入无向带权图的每条边的起点和终点"<<endl;
cout<<"序号及权值!直到输入权值为0的边为止!"<<endl;
do {i=r[k].row;j=r[k].col;w=r[k].weight;
//cin>>i>>j>>w;
Check(n,i,j);
if(k==e-1) break;
GA[i][j]=GA[j][i]=w;k++;
}while(1);
numE=e=k;
cout<<"邻接矩阵:\n";
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
cout<<setw(4)<<GA[i][j];
cout<<endl;}
}
//检查输入的边序