首页 > 代码库 > 最小生成树
最小生成树
/*
1.一个有n个顶点的连通图的生成树是原图的极小连通图,它包含原图中的所有n个顶点,并且具有保持图连通的最小的边。
显然有如下推论:
a.若删除生成树中的一条边,就会使该生成树因变成非连通图而不再满足生成树的定义;
b.若在生成树中增加一条边,就会使该生成树因存在回路而不再满足生成树的定义。
c.一个连通图的生成树可能有许多,使用不同寻找方法可以得到不同的生成树。
2.对于有n个顶点的无向图,无论它的生成树的形状如何,一定有n个顶点,有且只有n-1条边
3.如果无向连通图是一个带权图,那么它的所有生成树中必有一棵边的权值总和最小的生成树,
我们称这棵生成树为最小代价生成树,简称为最小生成树。
4.构造有n个顶点的无向连通带权图的最小生成树必须满足以下三个要求:
a.构造的最小生成树必须包括n个顶点;
b.构造的最小生成树中有且只有n-1条边
c.构造的最小生成树中部存在回路
5.构造最小生成树的典型方法有2种:一种称作普里姆(Prim)算法,一种称作克鲁斯卡尔(Kruskal)算法
6.普里姆算法思想:
假设G=(V,E)为一个带权图,其中V为带权图中顶点的集合,E为带权图中边的权值机会。
设置两个新的集合U和T,其中U用于存放带权图G的最小生成树的顶点的机会,T用于存放带权图G的最小生成树
的权值的集合。
普里姆算法的思想是:令集合U的初值为U={u0},即假设构造最小生成树时从顶点u0开始,集合T的初值为T={}。
从所有顶点u属于U和顶点v属于V-U的带权边中,选出具有最小权值的边(u,v),将顶点v加入集合U中,将边(u,v)
加入集合T中。如此不断重复,当U=V时,最小生成树构造完毕。此时,集合U中存放着最小生成树顶点的集合,集合T中存放着最小
生成树边的权值的集合。
7.克鲁斯卡尔算法:
设无向连通带权图G=(V,E),其中V为顶点集合,E为边的集合。克鲁斯卡尔算法的思想是:
设带权图G的最小生成树T由顶点集合和边的集合构成,其初值为T=(V,{}),即初始时最小生成树T只有带权图G中的顶点集合组成,
各顶点之间没有一条边。这样,最小生成树T中的各个顶点各自构成一个连通分量。然后,按照边的权值递增的顺序考察带权图G中
的边集合E中的各条边,若被考察的边的两个顶点属于T的2个不同的连通分量,则将此边加入到最小生成树T中,同时把两个连通分量连接
为一个连通分量;若被考察的边的两个顶点属于T的同一个连通分量,则将此边舍去,当T中的连通分量个数为1时,T中的该连通分量即为带权图
G的一棵最小生成树。
克鲁斯卡尔算法主要包括2个部分:首先是带权图G中e条边的权值的排序,其次是判断选取的边的2个顶点是否属于同一个连通分量。
8.克鲁斯卡尔算法的时间复杂主要由排序方法决定,而克鲁斯卡尔算法的排序算法只与边的个数有关,与图顶点的个数无关。当使用时间复杂度为
O(elbe)的排序算法时,克鲁斯卡尔算法得时间复杂度即为O(elbe)。因此,当带权图的顶点个数较多,而边的个数较少时,使用克鲁斯卡尔算法
构造最小生成树的时间效率较好。
1.一个有n个顶点的连通图的生成树是原图的极小连通图,它包含原图中的所有n个顶点,并且具有保持图连通的最小的边。
显然有如下推论:
a.若删除生成树中的一条边,就会使该生成树因变成非连通图而不再满足生成树的定义;
b.若在生成树中增加一条边,就会使该生成树因存在回路而不再满足生成树的定义。
c.一个连通图的生成树可能有许多,使用不同寻找方法可以得到不同的生成树。
2.对于有n个顶点的无向图,无论它的生成树的形状如何,一定有n个顶点,有且只有n-1条边
3.如果无向连通图是一个带权图,那么它的所有生成树中必有一棵边的权值总和最小的生成树,
我们称这棵生成树为最小代价生成树,简称为最小生成树。
4.构造有n个顶点的无向连通带权图的最小生成树必须满足以下三个要求:
a.构造的最小生成树必须包括n个顶点;
b.构造的最小生成树中有且只有n-1条边
c.构造的最小生成树中部存在回路
5.构造最小生成树的典型方法有2种:一种称作普里姆(Prim)算法,一种称作克鲁斯卡尔(Kruskal)算法
6.普里姆算法思想:
假设G=(V,E)为一个带权图,其中V为带权图中顶点的集合,E为带权图中边的权值机会。
设置两个新的集合U和T,其中U用于存放带权图G的最小生成树的顶点的机会,T用于存放带权图G的最小生成树
的权值的集合。
普里姆算法的思想是:令集合U的初值为U={u0},即假设构造最小生成树时从顶点u0开始,集合T的初值为T={}。
从所有顶点u属于U和顶点v属于V-U的带权边中,选出具有最小权值的边(u,v),将顶点v加入集合U中,将边(u,v)
加入集合T中。如此不断重复,当U=V时,最小生成树构造完毕。此时,集合U中存放着最小生成树顶点的集合,集合T中存放着最小
生成树边的权值的集合。
7.克鲁斯卡尔算法:
设无向连通带权图G=(V,E),其中V为顶点集合,E为边的集合。克鲁斯卡尔算法的思想是:
设带权图G的最小生成树T由顶点集合和边的集合构成,其初值为T=(V,{}),即初始时最小生成树T只有带权图G中的顶点集合组成,
各顶点之间没有一条边。这样,最小生成树T中的各个顶点各自构成一个连通分量。然后,按照边的权值递增的顺序考察带权图G中
的边集合E中的各条边,若被考察的边的两个顶点属于T的2个不同的连通分量,则将此边加入到最小生成树T中,同时把两个连通分量连接
为一个连通分量;若被考察的边的两个顶点属于T的同一个连通分量,则将此边舍去,当T中的连通分量个数为1时,T中的该连通分量即为带权图
G的一棵最小生成树。
克鲁斯卡尔算法主要包括2个部分:首先是带权图G中e条边的权值的排序,其次是判断选取的边的2个顶点是否属于同一个连通分量。
8.克鲁斯卡尔算法的时间复杂主要由排序方法决定,而克鲁斯卡尔算法的排序算法只与边的个数有关,与图顶点的个数无关。当使用时间复杂度为
O(elbe)的排序算法时,克鲁斯卡尔算法得时间复杂度即为O(elbe)。因此,当带权图的顶点个数较多,而边的个数较少时,使用克鲁斯卡尔算法
构造最小生成树的时间效率较好。
*/
#include<stdio.h> #include<malloc.h> #define MaxSize 10 //定义元素的大小 typedef char DataType; //定义一个类型 #define MaxVertices 10 //定义顶点的最大值 #define MaxWeight 10000 //定义无穷大的具体值 typedef char VerT; typedef struct{ //定义一个结构体 DataType list[MaxSize]; int size; //结构体元素的大小 }SeqList; //结构体的对象 typedef struct{ SeqList Vertices;//存放顶点的顺序表 int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵 int numOfEdges;//边的条数 }AdjMGraph; typedef struct{ int row;//行下标 int col;//列下标 int weight;//权值 }RowColWeight;//边信息结构体 typedef struct{ VerT vertex;//保存最小生成树每条边的弧头顶点数据 int weight;//保存最小生成树的相应边的权值 }MinSpanTree; //初始化 void initiate(SeqList *L){ L->size=0;//定义初始化元素个数 } //求当前元素的个数 int getLength(SeqList L){ return L.size;//返回长度 } //插入数据元素 int insertData(SeqList *L,int i,DataType x){ //在顺序表L的第i(0<=i<=size)个位置前插入数据元素x //插入成功返回1,出人失败返回0 int j; if(L->size>=MaxSize){ printf("顺序表已满,无法插入!!\n"); return 0; }else if(i<0||i>L->size){ printf("插入的位置不合法,不在指定的范围,参数i不合法!\n"); return 0; }else{ //从后向前一致移动数据,为插入做准备 for(j=L->size;j>i;j--){ L->list[j]=L->list[j-1]; } L->list[i]=x; L->size++; return 1; } } //删除数据 int deleteData(SeqList *L,int i,DataType *x){ //删除顺序表中位置为i的数据i>=0&&i<=size-1,把数据保存到x中 //删除成功返回1,否则返回0 int j; if(L->size<=0){ printf("顺序表已空无数据元素可删!\n"); return 0; }else if(i<0||i>L->size-1){ printf("参数i不合法,不能删除!\n"); return 0; }else{ *x=L->list[i]; for(j=i+1;j<=L->size-1;j++){//从前往后一次前移 L->list[j-1]=L->list[j]; } L->size--;//数据元素减一 return 1; } } //取出数据元素 int getData(SeqList L,int i,DataType *x){ if(i<0||i>L.size-1){ printf("参数i不合法,不能删除!\n"); return 0; }else{ *x=L.list[i]; return 1; } } //初始化有n个顶点的顺序表和邻接矩阵 void InitiateG(AdjMGraph *g,int n){ //初始化 int i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i==j){ g->edge[i][j]=0; }else{ g->edge[i][j]=MaxWeight;//MaxWeight表示无穷大 } } } g->numOfEdges=0;//边的条数置为0 initiate(&g->Vertices);//顺序表初始化 } //插入顶点 void InsertVertex(AdjMGraph *g,DataType vertex){ //在图G中插入顶点vertex insertData(&g->Vertices,g->Vertices.size,vertex);//顺序表尾插入 } //插入边 void InsertEdge(AdjMGraph *g,int v1,int v2,int weight){ //在图中插入边<v1,v2>,边<v1,v2>的权为weight if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){ printf("参数v1或v2越界出错!!!\n"); return ; } g->edge[v1][v2]=weight; g->numOfEdges++; } //删除边 void DeleteEdge(AdjMGraph *g,int v1,int v2){ //在G图中删除边<v1,v2> if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){ printf("参数v1或v2越界出错!!!\n"); return ; } if(g->edge[v1][v2]==MaxWeight||v1==v2){ printf("该边不存在!!!\n"); return; } g->edge[v1][v2]=MaxWeight; g->numOfEdges--; } //取第一个邻接顶点 int GetFirstVex(AdjMGraph g,int v){ //在图G中寻找序号为v的顶点的第一个邻接顶点 //如果这样的顶点存在,则返回该邻接顶点的序号,否则返回-1 int col; if(v<0||v>=g.Vertices.size){ printf("参数v1越界出错!!!\n"); return -1; } for(col=0;col<g.Vertices.size;col++){ if(g.edge[v][col]>0&&g.edge[v][col]<MaxWeight){ return col; } } return -1; } //取下一个邻接顶点 int GetNextVex(AdjMGraph g,int v1,int v2){ //在图中寻找v1顶点的邻接顶点v2的下一个邻接顶点 //如果这样的邻接顶点存在,则返回该邻接顶点的序号;否则返回-1 //v1和v2都是相应的顶点的序号 int col; if(v1<0||v1>g.Vertices.size||v2<0||v2>=g.Vertices.size){ printf("参数v1或v2越界出错!!!\n"); return -1; } for(col=v2+1;col<g.Vertices.size;col++){ if(g.edge[v1][col]>0&&g.edge[v1][col]<MaxWeight){ return col; } } return -1; } void CreatGraph(AdjMGraph *g,DataType V[],int n,RowColWeight E[],int e){ //在图中插入n个顶点信息V和e条边信息E int i,k; InitiateG(g,n);//d顶点顺序表初始化 for(i=0;i<n;i++){ InsertVertex(g,V[i]);//插入顶点 } for(k=0;k<e;k++){ InsertEdge(g,E[k].row,E[k].col,E[k].weight);//插入边 } } //普里姆函数设计 //参数g为邻接矩阵存储结构的图 //closeVertex为通过函数得到的最小生成树的顶点和相应顶点边的权值数据 void Prim(AdjMGraph g,MinSpanTree closeVertex[]){ //用普里姆算法建立带权图G的最小生成树closeVertex VerT x; int n=g.Vertices.size,minCost; int *lowCost=(int *)malloc(sizeof(int)*n);//保存集合U中顶点ui与集合V-U中顶点vj的所有边中当前具有最小权值的边(u,v) int i,j,k; for(i=1;i<n;i++){//初始化 //lowCost的初始值为邻接矩阵数组中第0行的值 lowCost[i]=g.edge[0][i];//存放了从集合U中顶点0到集合V-U中各个顶点的权值 } //从顶点0出发构造最小生成树 getData(g.Vertices,0,&x);//取顶点0 closeVertex[0].vertex=x;//保存顶点 lowCost[0]=-1;//标记顶点 for(i=1;i<n;i++){ //寻找当前最小权值的边对应的弧头顶点k minCost=MaxWeight;//MaxWeight为定义的最大值 for(j=1;j<n;j++){ if(lowCost[j]<minCost&&lowCost[j]>0){ minCost=lowCost[j]; k=j; } } getData(g.Vertices,k,&x);//取弧头顶点k closeVertex[i].vertex=x;//保存弧头顶点k的数据 closeVertex[i].weight=minCost;//保存相应的权值 lowCost[k]=-1;//标志顶点k //根据加入集合U的顶点k修改lowCost中的数值 for(j=1;j<n;j++){ if(g.edge[k][j]<lowCost[j]){ lowCost[j]=g.edge[k][j]; } } } } void main(){ AdjMGraph g; DataType a[]={'A','B','C','D','E','F','G'}; RowColWeight rcw[]={{0,1,50},{1,0,50},{0,2,60},{2,0,60},{1,3,65}, {3,1,65},{1,4,40},{4,1,40},{2,3,52},{3,2,52},{2,6,45},{6,2,45}, {3,4,50},{4,3,50},{3,5,30},{5,3,30},{3,6,42},{6,3,42},{6,2,45}, {4,5,70},{5,4,70}}; int n=7,e=20; int i,j; MinSpanTree closeVertex[7];//定义保存最小生成树的数组 CreatGraph(&g,a,n,rcw,e);//创建图 Prim(g,closeVertex);//调用Prim函数 //输出Prim函数得到最小生成树的顶点序列和权值 printf("初始顶点=%c\n",closeVertex[0].vertex); for(i=1;i<n;i++){ printf("顶点=%c 边的权值=%d\n",closeVertex[i].vertex,closeVertex[i].weight); } }
结果输出为:
最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。