include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

define MaxVex 100

typedef char VexType;
typedef int EdgeType;
typedef struct{
VexType node[MaxVex];
EdgeType edges[MaxVex][MaxVex];
int vexnum,edgenum;
}AdjMatrix;
//邻接矩阵定义

define MaxInt 32

//这里写kruskal算法
//这里存储边的结构体和我们建立图用的一样
//这里我就使用数组形式遍历，考试中写如果使用堆的话，每次找最小边耗费
int vexset[MaxVex];
int find(int i){
if(vexset[i]!=i) vexset[i]=find(vexset[i]);
return vexset[i];
}//并查集使用的find函数
typedef struct {
int v0;
int v1;
int weight;
}Edgeinfo;//为了建立图的辅助数据结构，也是kruskal用到的
bool cmp(Edgeinfo a,Edgeinfo b){
return a.weight<b.weight;
}
void MST_krukal(AdjMatrix G,Edgeinfo data[]){
//sort(Edgeinfo data[]);手写代码时
sort(data,data+G.edgenum-1,cmp);
//这里对所有边的信息按照权值大小排序
for(int i=1;i<=G.vexnum;i) vexset[i]=i;//初始化并查集
for(int i=0;i<G.edgenum-1;i){//遍历所有的边
int u0=data[i].v0,u1=data[i].v1;
if(find(u0)!=find(u1)){//如果两个点不连通
cout<<u0<<’-‘<<u1<<endl;
vexset[find(u1)]=find(u0);
}
}
}
//这样来看的话，kruskal算法代码非常短
//排序边数组，初始化并查集，遍历所有边
//判断两点是否联通，然后联通，最终得到一棵树
//主要的操作都在于并查集的操作上

//并查集这里注意
//find函数要熟练
//判断两个点是否联通，要使用find
//将两个点联通，是将一个点的根的根，设置为另一个点的根
//从树的角度来思考

void create(AdjMatrix &G,Edgeinfo data[],int n){
for(int i=1;i<=MaxVex-1;i){
for(int j=1;j<=MaxVex-1;j)
G.edges[i][j]=MaxInt;
}
for(int i=1;i<=G.vexnum;i) G.edges[i][i]=0;
for(int i=0;i<n;i){
G.edges[data[i].v0][data[i].v1]=data[i].weight;
G.edges[data[i].v1][data[i].v0]=data[i].weight;
}
}

int main(){
AdjMatrix G;
G.vexnum=7;
G.edgenum=12;
Edgeinfo data[]={{1,2,23},{1,7,36},{1,6,28},{2,7,1},{2,3,20},
{3,7,4},{3,4,15},{4,7,9},{5,4,3},{5,7,16},{5,6,17},{6,7,25}
};
AdjMatrix &M=G;
create(M,data,12);
// for(int i=1;i<=G.vexnum;i){
// for(int j=1;j<=G.vexnum;j)
// cout<<setw(3)<<G.edges[i][j]<<’ ‘;
// cout<<endl;
// }
//上述完成建图
MST_krukal(G,data);
}