新开的网站建设公司如何推广,wordpress 前台,深圳市网站制作公司,wordpress禁用主题字体Content#xff1a; 一、问题描述二、算法思想三、代码实现四、两种算法的比较五、小结 一、问题描述 利用 prim 算法和 kruskal 算法实现最小生成树问题#xff1b;
二、算法思想 首先判断图是否连通#xff0c;只有在连通的情况下才进行最小树的生成#xff1b;
三、代… Content 一、问题描述二、算法思想三、代码实现四、两种算法的比较五、小结 一、问题描述 利用 prim 算法和 kruskal 算法实现最小生成树问题
二、算法思想 首先判断图是否连通只有在连通的情况下才进行最小树的生成
三、代码实现
#includestdio.h
#includestdlib.h
#includestring.h
#define maxx 999999
#pragma warning(disable:4996)typedef struct arc//弧
{ int index;//指向节点编号float weight;//边的权值struct arc *next;
}AR;typedef struct edge
{int i,j;//边的起点和终点编号float edge;//边的权值
}EG;typedef struct MyGraph
{int type;//0表示无向图1表示有向图int arcnum,vexnum;//边的个数、顶点个数char **vexname;//存放顶点名称的二维数组 AR *N;//表头数组float **A;//邻接矩阵这里使用float型EG *E;//存放边的三元组
}GH;int findvex(char *s,GH *G);//找到图G中名称为s的节点编号并将其返回
void creatGraph(GH *G);//创建图G
void showGraph(GH *G);//以邻接表的形式显示图Gint isconnect(GH *G);//判断图G是否连通是则返回1否则返回0
int BFSvisit(int start,GH *G);//对图G从start号点开始广度优先遍历返回访问过的节点个数void prim(GH *G,int start);//利用prim算法求图G中以start为起点的最小生成树
void showTree(AR *N,char **vexname,int n);//显示最小生成树N表示表头数组vexname中存放顶点名称n表示节点数量void kruskal(GH *G);//利用kruskal算法求图G中的最小生成树
void heapsort(EG *E, int n);//对含有n条边的三元组E进行堆排序
void adjust(int index, EG *E, int n);//对利用顺序表E表示的含有n个节点的完全二叉树的index号节点进行筛选
void changeflag(int m,int y,int *flag, AR *N,int n);//将图G中m号节点所在的连通分支上的点的flag统一赋值为yN为表头数组n表示原图中节点个数int main(void)
{GH *G;int begin;//起点编号//创建图G(GH *)malloc(sizeof(GH));creatGraph(G);printf(图的邻接表形式:\n);showGraph(G);//if (!isconnect(G))//{// printf(该图不连通不具有最小生成树.\n);
// exit(-1);
// }printf(该图连通寻找最小生成树:\n);printf(\n\nprim算法\n);printf(请输入起点编号(-1结束):);scanf(%d, begin);while (begin ! -1){prim(G, begin);printf(请输入起点编号(-1结束):);scanf(%d, begin);}printf(\n\nkruskal算法\n);kruskal(G);free(G);return 0;
}int findvex(char *s,GH *G)//找到图G中名称为s的节点编号并将其返回
{for(int i0;iG-vexnum;i){if(strcmp(s,G-vexname[i])0)return i;}printf(该点不存在\n);exit(-1);
}void creatGraph(GH *G)//创建图G
{int i,j,k,n,m;float edge;char filename[]graph.txt;char str[10],str1[10];FILE *fp;AR *p;fpfopen(filename,r);if(!fp){printf(文件打开失败!\n);exit(-1);}//读取图的类型和节点数量fscanf(fp,%d%d,G-type,n); G-vexnumn;//分配空间G-vexname(char **)malloc(n*sizeof(char *));G-N(AR *)malloc(n*sizeof(AR));G-A(float **)malloc(n*sizeof(float *));//初始化A和Nfor (i 0; i n; i){G-N[i].next NULL;G-A[i] (float *)malloc(n*sizeof(float));for (j 0; j n; j)G-A[i][j]maxx;}//读取顶点名称for(i0;in;i){fscanf(fp,%s,str);//先分配空间G-vexname[i](char *)malloc(strlen(str)*sizeof(char));strcpy(G-vexname[i],str);} //读取边fscanf(fp,%d,m);G-arcnumm;//边的个数G-E(EG *)malloc((m1)*sizeof(EG));//0号位置不存放数据for(k1;km;k){fscanf(fp,%s%s%f,str,str1,edge);ifindvex(str,G);jfindvex(str1,G);//邻接表中添加节点p(AR *)malloc(sizeof(AR));p-indexj;p-weightedge;p-nextG-N[i].next;G-N[i].nextp;//邻接矩阵G-A[i][j]edge;//三元组G-E[k].ii;G-E[k].jj;G-E[k].edgeedge;if(G-type0){//邻接表中添加节点p(AR *)malloc(sizeof(AR));p-indexi;p-weightedge;p-nextG-N[j].next;G-N[j].nextp;//邻接矩阵G-A[j][i]edge;}}fclose(fp);
}void showGraph(GH *G)//以邻接表的形式显示图G
{int i;AR *p; //用于遍历for (i 0; i G-vexnum; i){printf(%s,G-vexname[i]);pG-N[i].next;while (p){if (G-type 1)printf(--);elseprintf(--);printf(%s(%.2f),G-vexname[p-index],p-weight);pp-next;}printf(\n);}printf(\n);
}int isconnect(GH *G)//判断图G是否连通是则返回1否则返回0
{int k;kBFSvisit(0,G);//k广度优先遍历访问到的节点个数if(kG-vexnum)return 1;elsereturn 0;
}int BFSvisit(int start,GH *G)//对图G从start号点开始广度优先遍历返回访问过的节点个数
{int i,n;int *visit;int *q;int front,rear;AR *p;//空间分配nG-vexnum;visit(int *)malloc(n*sizeof(int));q(int *)malloc(n*sizeof(int));//初始化for(i0;in;i)visit[i]0; visit[start]1;q[0]start;front0;rear1;while(front!rear){pG-N[q[front]].next;//对出队点的直接后继进行遍历//printf(%s\n,G-vexname[q[front]]); front;while (p){if (visit[p-index] 0)//如果未被访问添加访问标记入队{visit[p-index]1;q[rear]p-index;rear;}pp-next;} }free(visit);free(q);return rear;//返回广度优先遍历访问到的节点个数
}void prim(GH *G, int start)//利用prim算法求图G中以start为起点的最小生成树
{int i,n;int *pre;float *weight; AR *N,*p;float min;int next;nG-vexnum;pre(int *)malloc(n*sizeof(int));//前驱数组weight(float *)malloc(n*sizeof(float));//距生成树的最短距离值为0.0表示属于生成树N(AR *)malloc(n*sizeof(AR));//表头数组用于存放最小生成树 //1.初始化for (i 0; i n; i){if (G-A[start][i] maxx)pre[i] start; elsepre[i] -1;weight[i] G-A[start][i];N[i].nextNULL;}weight[start]0;//起点放到生成树中//2.寻找距离已生成树最近的顶点minmaxx;for (i 0; i n; i){if (weight[i] ! 0 weight[i] min)//从与原图中与最小生成树连通的节点中选择{minweight[i];nexti;}}while (min maxx){weight[next]0;//3.放入最小生成树中//相应地添加节点p(AR *)malloc(sizeof(AR));p-indexnext;p-weightG-A[pre[next]][next];p-nextN[pre[next]].next;N[pre[next]].nextp;if (G-type 0){p(AR *)malloc(sizeof(AR));p-indexpre[next];p-weightG-A[pre[next]][next];p-nextN[next].next;N[next].nextp;}//4.更新weight和prepG-N[next].next;while (p){if (weight[p-index] ! 0 weight[p-index] p-weight){weight[p-index]p-weight;pre[p-index]next;}pp-next;}//继续寻找minmaxx;for (i 0; i n; i){if (weight[i] ! 0 weight[i] min){minweight[i];nexti;}}}//结果显示showTree(N,G-vexname,n);free(pre);free(weight);free(N);
}void showTree(AR *N, char **vexname, int n)//显示最小生成树N表示表头数组vexname中存放顶点名称n表示节点数量
{int i;AR *p;printf(最小生成树的邻接表形式如下:\n);for (i 0; i n; i){ pN[i].next;if (p){printf(%s, vexname[i]);while (p){printf(--%s(%.2f), vexname[p-index], p-weight);p p-next;}printf(\n);}}printf(\n);
}void kruskal(GH *G)//利用kruskal算法求图G中的最小生成树
{int i;int m,n;int p,q;int *flag; AR *N,*t;mG-arcnum;nG-vexnum;flag(int *)malloc(n*sizeof(int *));//位于同一连通分量的节点的flag值相同N(AR *)malloc(n*sizeof(AR));//表头数组用于存放最小生成树//1.初始化for (i 0; i n; i){flag[i] i;//各自为营N[i].next NULL;}//2.对存放边的三元组G-E进行堆排序heapsort(G-E,m);//3.挑取边for (i 1; i m; i){ //读取两端节点编号pG-E[i].i;qG-E[i].j;if(flag[p]!flag[q])//4.若两端位于不同的连通分支表示该边可选{changeflag(q,flag[p],flag,N,n);//将q号节点所在的连通分支上的点的flag改为flag[p]//相应地添加节点t(AR *)malloc(sizeof(AR));t-indexq;t-weightG-A[p][q];t-nextN[p].next;N[p].nextt;//无向图需要双边添加节点if (G-type 0){t (AR *)malloc(sizeof(AR));t-indexp;t-weightG-A[p][q];t-nextN[q].next;N[q].nextt;}}}//结果显示showTree(N,G-vexname,n);free(flag);free(N);
}void heapsort(EG *E, int n)//对含有n条边的三元组E进行堆排序
{int i;//首先调整所有的父节点for (i n / 2; i 1; i--)adjust(i,E,n);//然后进行n-1趟堆排序找出n-1个最大值for (i 1; i n - 1; i){ //首先进行首尾交换E[0]E[1];E[1]E[n-i1];E[n-i1]E[0];//然后进行调整adjust(1,E,n-i);}
}void adjust(int index, EG *E, int n)//对利用顺序表E表示的含有n个节点的完全二叉树的index号节点进行筛选
{int i,j;iindex;j2*i;E[0]E[i];//哨兵while (j n){if (j 1 n)//保证j始终指向较大的孩子{if(E[j1].edgeE[j].edge)jj1;}if (E[j].edge E[0].edge)//如果大于哨兵{E[i]E[j];//将值赋给父节点ij;//更新循环变量j2*i;}else//E[j].edge E[0].edgebreak;//跳出循环}//i没有孩子或者E[j].edge E[0].edgeE[i]E[0];
}void changeflag(int m,int y,int *flag, AR *N,int n)//将图G中m号节点所在的连通分支上的点的flag统一赋值为yN为表头数组n表示原图中节点个数
{ //利用BFS访问m号节点所在的连通分支更改其flag值int *q;int front,rear;AR *p;q(int *)malloc(n*sizeof(int));//初始化flag[m]y;q[0]m;front0;rear1;while (front ! rear){pN[q[front]].next;front;while (p){if (flag[p-index] ! y){flag[p-index]y;q[rear]p-index;rear;}pp-next;}}free(q);
}四、两种算法的比较 两种算法从不同的角度提出了最小生成树的构造方法 Prim 算法从选节点的角度出发每次都选距离生成树最近的节点从而保证了最后的结果为最小生成树时间复杂度与顶点个数 N 有关每次选择最近顶点需要进行一次遍历比较 N 次之后将其添加进最小生成树更新 weight 和 pre一次遍历N 次操作总共需要选择 N-1 次所以 prim 算法的时间复杂度为 O ( N 2 ) O(N^2) O(N2) Kruskal 算法从另一个角度出发选取边每次都选取权值最小的、添加之后不构成圈的边进行添加同样保证了结果为最小生成树时间复杂度与边的个数 e 有关为方便后续处理首先对边按权值大小进行排序时间复杂度为 O ( e l o g 2 e ) O(elog_2e) O(elog2e)然后对每条边进行判断并决定是否添加e 次操作所以总的时间复杂度为 O ( e l o g 2 e ) O(elog_2e) O(elog2e) 综合所述Prim 算法适合顶点相对较少而边相对稠密的网的最小生成树的求解而 Kruskal 算法适合于求边比较稀疏的网的最小生成树
五、小结
1、 首先进行一次 BFS返回遍历到的节点数目据此判断图是否连通非连通图不具有最小生成树 2、 对于 prim 算法将最小生成树中的节点的 weight[i] 置为0表示其在最小生成树中 3、 最小生成树中每增添一个节点更新其直接后继的 weight 和 pre 4、 kruskal 算法为图的结构体添加成员 E ——存放边的结构体数组成员为两节点编号和边的权值这样在创建图时可以直接创建 E同时图的数据文件中添加边的条数 5、 在执行 kruskal 算法时可对 E 按照边的权值进行堆排序避免了从邻接矩阵中再次读取边的操作降低了算法的时间复杂度 6、 通过 BFS 来实现某一连通分支上所有点的 flag 值的更改
