克鲁斯卡尔-最小生成树

最小生成树实际意义在于解决一张图里面，把所有顶点用最短路径全部连接

第三次人工智能浪潮

看了杨澜的节目，才继续坚持写，人工智能需要好的算法，是先人们几辈的积累和爆发

我们要抓住这个时代。

克鲁斯卡尔算法，最小生成树，插边，适合边少，稀疏

借助两个数组，一个(se[]) 用来存放已经按照权值从小到大排完序的表

一个(set[])用来存放顶点属于哪一个集合，刚开始初始化所有顶点独占一个集合

每次插入一个se里面内容值，根据顶点更新set

还是这张图片

/*
克鲁斯卡尔算法
*/
void Kruskal(Graph my_map)
{side se[MAX_SIZE];//存储边的信息int my_set[MAX_SIZE],k=0,number=0;//边数int temp,j;/*按照升序排列边*/for(int i=0;i<my_map->vexnum;i++){for(int j=i+1;j<my_map->vexnum;j++)//只寻找邻接矩阵的上半三角就欧克{if(my_map->tyust[i][j]<INFINTY)//说明边连线存在{k=number-1;//下面有用处while(k>=0)//一直寻找，返回插入点k{if(se[k].weiget>my_map->tyust[i][j])//权重判断{se[k+1]=se[k];//如果权重大，就将它后移k--;//把游标指向上一个}else  break;}se[k+1].a=i;se[k+1].b=j;se[k+1].weiget=my_map->tyust[i][j];number++;//边数加一}}}///打印出se[]///for(int i=0;i<number;i++){printf("se[%d],a,b,weiget\n",i,se[i].a,se[i].b,se[i].weiget);}初始化my_set[],先指向自己///for(int j=0;j<my_map->vexnum;j++){my_set[j]=j;}cout<<"生成树边:"<<endl;k=0;j=0;while(k<my_map->vexnum-1)//n个顶点需要n-1条边{if(my_set[se[j].a]!=my_set[se[j].b])//如果一条边的两个顶点不都在集合中{//j=0,从最小边开始cout<<my_map->vex[se[j].a]<<"-"<<my_map->vex[se[j].b]<<endl;temp=my_set[se[j].b];for(int i=0;i<my_map->vexnum;i++)//对所有顶点{if(my_set[i]==temp){my_set[i]=my_set[se[j].a];//参照上图来看}}k++;//已有边数加一}j++;}
}

最后贴一下所有代码

#include <iostream>
#include <malloc.h>
#include <cstdio>
#define  MAX_SIZE  20
#define  INFINTY   256
using namespace std;
typedef  struct graph
{int arcnum,vexnum;//弧数，顶点数int tyust[MAX_SIZE][MAX_SIZE];//邻接矩阵char vex[MAX_SIZE];//顶点
}*Graph;
struct side
{int a,b;//一条边的左右两个顶点下标int weiget;//权重
};
int get_pos(Graph my_map,char c)
{for(int i=0;i<my_map->vexnum;i++){if(my_map->vex[i]==c){return i;}}return -1;
}
void print(Graph my_map)
{for(int i=0;i<my_map->vexnum;i++){for(int j=0;j<my_map->vexnum;j++){printf("%-4d",my_map->tyust[i][j]);}cout<<endl;}cout<<endl;
}/*
创建图
*/
Graph creat_graph()
{int arc_num,vex_num;int p1,p2;char in1,in2;int my_weiget;Graph pit=(Graph)malloc(sizeof(graph));cout<<"请按照顺序输入顶点数和弧数"<<endl;cin>>vex_num>>arc_num;pit->arcnum=arc_num;pit->vexnum=vex_num;//初始化权重for(int i=0;i<vex_num;i++){for(int j=0;j<vex_num;j++){pit->tyust[i][j]=INFINTY;}}cout<<"请输入所有顶点"<<endl;for(int i=0;i<vex_num;i++){cin>>pit->vex[i];}for(int j=0;j<arc_num;j++){cout<<"请输入边和权重"<<j+1<<endl;cin>>in1>>in2>>my_weiget;p1=get_pos(pit,in1);p2=get_pos(pit,in2);pit->tyust[p1][p2]=pit->tyust[p2][p1]=my_weiget;}print(pit);return pit;
}/*
克鲁斯卡尔算法
*/
void Kruskal(Graph my_map)
{side se[MAX_SIZE];//存储边的信息int my_set[MAX_SIZE],k=0,number=0;//边数int temp,j;/*按照升序排列边*/for(int i=0;i<my_map->vexnum;i++){for(int j=i+1;j<my_map->vexnum;j++)//只寻找邻接矩阵的上半三角就欧克{if(my_map->tyust[i][j]<INFINTY)//说明边连线存在{k=number-1;//下面有用处while(k>=0)//一直寻找，返回插入点k{if(se[k].weiget>my_map->tyust[i][j])//权重判断{se[k+1]=se[k];//如果权重大，就将它后移k--;//把游标指向上一个}else  break;}se[k+1].a=i;se[k+1].b=j;se[k+1].weiget=my_map->tyust[i][j];number++;//边数加一}}}///打印出se[]///for(int i=0;i<number;i++){printf("se[%d],a,b,weiget\n",i,se[i].a,se[i].b,se[i].weiget);}初始化my_set[],先指向自己///for(int j=0;j<my_map->vexnum;j++){my_set[j]=j;}cout<<"生成树边:"<<endl;k=0;j=0;while(k<my_map->vexnum-1)//n个顶点需要n-1条边{if(my_set[se[j].a]!=my_set[se[j].b])//如果一条边的两个顶点不都在集合中{//j=0,从最小边开始cout<<my_map->vex[se[j].a]<<"-"<<my_map->vex[se[j].b]<<endl;temp=my_set[se[j].b];for(int i=0;i<my_map->vexnum;i++)//对所有顶点{if(my_set[i]==temp){my_set[i]=my_set[se[j].a];}}k++;//已有边数加一}j++;}
}
int main()
{Graph my_map=creat_graph();Kruskal(my_map);return 0;
}