中学生女生卫衣:帮忙加一个最小生成树的注释

//建立一个带权的无向图，生成它的邻接矩阵，按普里姆算法求其最小生成树。
#include<iostream>
#include<fstream>
#include<set>
using namespace std;
#define MAX 100
struct Edge
{
short s;
short e;
short w;
Edge(int a=0, int b=0, int c=0) {s=a; e=b; w=c; }
};

Edge E[MAX*MAX];
int n, e, father[MAX], point[MAX];
bool input(int a[][MAX])
{
e=0; //边数初始化为0
cout<<"请输入节点的个数: ";
cin>>n;
cout<<"n="<<n<<endl;
cout<<"请输入邻接矩阵: "<<endl;
for(int i=0 ; i<n ; i++)
{
for(int j=0 ; j<n ; j++)
{
cin>>a[i][j];
if( a[i][j]>0 )
E[e].s=i,E[e].e=j,E[e].w=a[i][j],
e++;
}
}
return true;
}

void prim(int a[][MAX],int n)
{
bool used[MAX];
int i,j;
int sum=0; //记录总权值
for(i=0;i<n;i++)
used[i]=false;
used[0]=true;
for(int z=1;z<n;z++) //最小生成树只需要有n-1条边
{
int minpre,minpoint,min=1<<30;
for(i=0;i<n;i++)
{
if(used[i]==false) continue;
for(j=0 ; j<n ; j++)
{
if( a[i][j]>0 && a[i][j]<min && used[j]==0)
min=a[i][j],
minpoint=j,
minpre=i;
}
}
used[minpoint]=true;
sum+=min;
cout<<"生成树的第"<<z<<"条边: "<<minpre<<"->"<<minpoint<<",权值

为"<<min<<endl;
}
cout<<"最小生成树结束，权值为:"<<sum<<endl<<endl;
}

int GetFather(int a)
{
if(father[a] != a)
father[a] = GetFather(father[a]);
return father[a];
}

void MergeSets(int a, int b) { father[a] = b; }

void InitSet() //初始化并查集，Kruskal的森林
{
int i;
for(i=0;i<n;++i)
father[i] = i;
}

void Kruskal()
{
int i, j;
int dis = 0;
i = 0;
j = 1;
while(j<n)
{
int fa = GetFather(E[i].s),
fb = GetFather(E[i].e);

if(fa != fb)
{
MergeSets(fa, fb);
cout<<"生成树的第"<<j<<"条边: "<<E[i].s<<"->"<<E[i].e<<",权值

为"<<E[i].w<<endl;
dis += E[i].w;
++j;
}
if(i++ == e) { printf("Error occurd!");return;}
}
cout<<"最小生成树结束，权值为:"<<dis<<endl<<endl;
}

void GenHeap(int i, int j)
// Quick Sort
{
int left = i, right = j;
Edge pivot = E[left]; //取一个分界点
if(left < right)
{
while(left < right)
{
while(left < right && E[right].w >= pivot.w) --right;
if(left < right)
E[left++] = E[right];
while(left < right && E[left].w < pivot.w) ++left;
if(left < right)
E[right--] = E[left];
}
E[left] = pivot;

GenHeap(i, left-1);
GenHeap(left+1, j);
}
return;
}

int main()
{
int a[MAX][MAX];
input(a);
cout<<"prim算法生成最小树如下："<<endl;
prim(a,n);
InitSet();
GenHeap(0, e-1); //排序，产生一个堆
cout<<"Kruskal算法生成最小树如下："<<endl;
Kruskal();
return 1;
}