老年人糊涂了在经过吵架后突然糊涂如何让他平复下来

来源：蜘蛛抓取(WebSpider) 时间：2020-02-22 13:28 标签： 老年人糊涂了

【1】什么是最小生成树

对于连通的带权图(连通网)G，其生成树也是带权的

生成树T各边的权值总和称为该树的权。

注意：最小是指权值最小

一个连通图的生成树是一个极尛的连通子图它包含全部的顶点，但只有足以构成一棵树的n-1条边

求最小生成树有两种算法：普里姆算法和克鲁斯卡尔算法

不好理解？看不懂能通俗点不？看个实例哈：

假设你是电信实施工程师需要为一个镇的九个村庄架设通信网络做设计。

村庄位置大致如下图之間连线的数字表示村与村间的可通达直线距离。

你们领导要求你必须用最小的成本完成这次任务你说怎么办？

好这就是很现实的一个朂小生成树案例。且听下面详解

利用 普里姆算法 要解决如上问题，首先我们构造图的邻接矩阵如下图所示：

注意：实际中我们用65535来代表无穷大。

关于普里姆算法以及讲解如下图：

针对上面我们遇到的实际案例普里姆算法执行循环过程如下图：

每次所选最小边分别如 图1-圖8 所示：

最后用所有边把各个顶点连通也就是所谓的最小生成树。

【3】普里姆算法的实现

40 /////二维数组的创建并初始化 92 // 图采用邻接矩阵存储 最尛生成树 普里姆算法 99 //lowcost的值为0在这里就是此下标的顶点已经加入生成树 110 min = INFINITY; // 初始化最小权值为常数，通常设置为不可能到达的数值 115 // 如果两个顶點之间存在边有权值不为0并且小于min 128 { // 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值

代码中所引用是头文件SeqList.h从随笔《》拷贝即可，也可以自己另行处理

/最小生成树之Prim算法

/*定义邻接矩阵類型*/

/*建立图的邻接矩阵*/

printf("请输入边的信息按照起点，终点权值的形式输入：\n");

/*初始化图的边集数组*/

/*根据图的邻接矩阵生成图的边集数组*/

/*按升序排列图的边集数组*/

/*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*/

/*给T赋初值，对应为v1依次到其余各顶点的边*/

/*进行n-1次循環每次求出最小生成树中的第k条边*/

/*把最短边对调到k-1下标位置*/

/*把新加入最小生成树T中的顶点序号赋给j*/

/*修改有关边，使T中到T外的每一个顶点保持一条到目前为止最短的边*/

/*输出边集数组的每条边*/

printf("按照起点终点，权值的形式输出的最小生成树为：\n");

我要回帖

更多关于 老年人糊涂了 的文章

 

随机推荐