编写网站的语言有哪些,wordpress直接,外贸网站推广机构,青岛建网站最小生成树
最小生成树#xff08;minimum spanning tree#xff09;是由n个顶点#xff0c;n-1条边#xff0c;将一个连通图连接起来#xff0c;且使权值最小的结构。 最小生成树可以用Prim#xff08;普里姆#xff09;算法或kruskal#xff08;克鲁斯卡尔#xff…最小生成树
最小生成树minimum spanning tree是由n个顶点n-1条边将一个连通图连接起来且使权值最小的结构。 最小生成树可以用Prim普里姆算法或kruskal克鲁斯卡尔算法求出。
我们将以下面的带权连通图为例讲解这两种算法的实现
注由于测试输入数据较多程序可以采用文件输入 Prim普里姆算法 时间复杂度ON^2N为顶点数 prim算法又称“加点法”用于边数较多的带权无向连通图 方法每次找与之连线权值最小的顶点将该点加入最小生成树集合中 注意相同权值任选其中一个即可但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树
1.初始化 lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]0表示i点加入了MST。 mst[i]:表示对应lowcost[i]的起点当mst[i]0表示起点i加入MST。 由于我们规定最开始的顶点是1所以lowcost[1]0MST[1]0。即只需要对2~n进行初始化即可。
#define MAX 100
#define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n)
{ int lowcost[MAX]; int mst[MAX]; int i, j, min, minid, sum 0; for (i 2; i n; i) { lowcost[i] graph[1][i];//lowcost存放顶点1可达点的路径长度 mst[i] 1;//初始化以1位起始点 } mst[1] 0; 2.查找最小权值及路径更新 定义一个最小权值min和一个最小顶点ID minid通过循环查找出min和minid另外由于规定了某一顶点如果被连入则lowcost[i]0所以不需要担心重复点问题。所以找出的终点minid在MST[i]中可以找到对应起点min为权值直接输出即可。 我们连入了一个新的顶点自然需要对这一点可达的路径及权值进行更新所以循环中还应该包括路径更新的代码。
for (i 2; i n; i) { min MAXCOST; minid 0; for (j 2; j n; j) { if (lowcost[j] min lowcost[j] ! 0) { min lowcost[j];//找出权值最短的路径长度 minid j; //找出最小的ID } } printf(V%d-V%d%d\n,mst[minid],minid,min); sum min;//求和 lowcost[minid] 0;//该处最短路径置为0 for (j 2; j n; j){ if (graph[minid][j] lowcost[j])//对这一点直达的顶点进行路径更新 { lowcost[j] graph[minid][j]; mst[j] minid;} } } printf(最小权值之和%d\n,sum);
} 具体代码如下
#includestdio.h
#define MAX 100
#define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n)
{ int lowcost[MAX]; int mst[MAX]; int i, j, min, minid, sum 0; for (i 2; i n; i) { lowcost[i] graph[1][i];//lowcost存放顶点1可达点的路径长度 mst[i] 1;//初始化以1位起始点 } mst[1] 0; for (i 2; i n; i) { min MAXCOST; minid 0; for (j 2; j n; j) { if (lowcost[j] min lowcost[j] ! 0) { min lowcost[j];//找出权值最短的路径长度 minid j; //找出最小的ID } } printf(V%d-V%d%d\n,mst[minid],minid,min); sum min;//求和 lowcost[minid] 0;//该处最短路径置为0 for (j 2; j n; j){ if (graph[minid][j] lowcost[j])//对这一点直达的顶点进行路径更新 { lowcost[j] graph[minid][j]; mst[j] minid;} } } printf(最小权值之和%d\n,sum);
}
int main()
{ int i, j, k, m, n; int x, y, cost; //freopen(1.txt,r,stdin);//文件输入 scanf(%d%d,m,n);//m顶点的个数n边的个数 for (i 1; i m; i)//初始化图 { for (j 1; j m; j) { graph[i][j] MAXCOST; } } for (k 1; k n; k) { scanf(%d%d%d,i,j,cost);graph[i][j] cost; graph[j][i] cost; } prim(graph, m); return 0;
} 编译运行结果 kruskal克鲁斯卡尔算法 时间复杂度ONlogNN为边数 kruskal算法又称“加边法”用于边数较少的稀疏图 方法每次找图中权值最小的边将边连接的两个顶点加入最小生成树集合中 注意相同权值任选其中一个即可但是不允许出现闭合回路的情况。 代码部分通过以下步骤可以得到最小生成树
1.初始化 构建边的结构体包括起始顶点、终止顶点边的权值 借用一个辅助数组vset[i]用来判断某边是否加入了最小生成树集合
#define MAXE 100
#define MAXV 100
typedef struct{int vex1; //边的起始顶点int vex2; //边的终止顶点int weight; //边的权值
}Edge;
void kruskal(Edge E[],int n,int e)
{ int i,j,m1,m2,sn1,sn2,k,sum0;int vset[n1];for(i1;in;i) //初始化辅助数组vset[i]i;k1;//表示当前构造最小生成树的第k条边初值为1j0;//E中边的下标初值为0
2.取边和辅助集合更新 按照***排好的顺序***依次取边若不属于同一集合则将其加入最小生成树集合每当加入新的边所连接的两个点即纳入最小生成树集合为避免重复添加需要进行辅助集合更新 注由于kruskal算法需要按照权值大小顺序取边所以应该事先对图按权值升序这里我采用了快速排序算法具体算法可以参照快速排序C语言 while(ke)//生成的边数小于e时继续循环{m1E[j].vex1;m2E[j].vex2;//取一条边的两个邻接点sn1vset[m1];sn2vset[m2]; //分别得到两个顶点所属的集合编号if(sn1!sn2)//两顶点分属于不同的集合该边是最小生成树的一条边{//防止出现闭合回路 printf(V%d-V%d%d\n,m1,m2,E[j].weight);sumE[j].weight;k; //生成边数增加if(kn)break;for(i1;in;i) //两个集合统一编号if (vset[i]sn2) //集合编号为sn2的改为sn1vset[i]sn1;}j; //扫描下一条边}printf(最小权值之和%d\n,sum);
}具体算法实现
#include stdio.h
#define MAXE 100
#define MAXV 100
typedef struct{int vex1; //边的起始顶点int vex2; //边的终止顶点int weight; //边的权值
}Edge;
void kruskal(Edge E[],int n,int e)
{ int i,j,m1,m2,sn1,sn2,k,sum0;int vset[n1];for(i1;in;i) //初始化辅助数组vset[i]i;k1;//表示当前构造最小生成树的第k条边初值为1j0;//E中边的下标初值为0while(ke)//生成的边数小于e时继续循环{m1E[j].vex1;m2E[j].vex2;//取一条边的两个邻接点sn1vset[m1];sn2vset[m2]; //分别得到两个顶点所属的集合编号if(sn1!sn2)//两顶点分属于不同的集合该边是最小生成树的一条边{//防止出现闭合回路 printf(V%d-V%d%d\n,m1,m2,E[j].weight);sumE[j].weight;k; //生成边数增加 if(kn)break;for(i1;in;i) //两个集合统一编号if (vset[i]sn2) //集合编号为sn2的改为sn1vset[i]sn1;}j; //扫描下一条边}printf(最小权值之和%d\n,sum);
}
int fun(Edge arr[],int low,int high){int key;Edge lowx;lowxarr[low];keyarr[low].weight;while(lowhigh){while(lowhigh arr[high].weightkey)high--;if(lowhigh)arr[low]arr[high];while(lowhigh arr[low].weightkey)low;if(lowhigh)arr[high--]arr[low];}arr[low]lowx;return low;}
void quick_sort(Edge arr[],int start,int end)
{int pos;if(startend){posfun(arr,start,end);quick_sort(arr,start,pos-1);quick_sort(arr,pos1,end);}
}
int main()
{Edge E[MAXE];int nume,numn;//freopen(1.txt,r,stdin);//文件输入printf(输入顶数和边数:\n);scanf(%d%d,numn,nume);for(int i0;inume;i)scanf(%d%d%d,E[i].vex1,E[i].vex2,E[i].weight);quick_sort(E,0,nume-1);kruskal(E,numn,nume);
}
编译运行结果
