个人中心
文章发布
退出
作者热门文章
- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
27
4
在生成树的过程中，把已经在生成树中的节点看作一个集合，把剩下的节点看作另外一个集合，从连接两个集合的边中选择一条权值最小的边即可。
首先任选一个节点，例如节点1，把它放在集合 U 中，U={1},那么剩下的节点为 V-U={2,3,4,5,6,7},集合 V 是图的所有节点集合。
现在只需要看看连接两个集合（U 和 V-U）的边中，哪一条边的权值最小，把权值最小的边关联的节点加入集合 U 中。从上图可以看出，连接两个集合的 3 条边中，1-2 边的权值最小，选中它，把节点 2 加入集合 U 中，U={1,2}，V - U={3,4,5,6}，如下图所示。
再从连接两个集合（U 和 V-U）的边中选择一条权最小的边。从上图看出，在连接两个集合的4条边中，节点2到节点7的边权值最小，选中这条边，把节点7加入集合U={1,2,7}中，V-U={3,4,5,6}。
如此下去，直到 U=V 结束，选中的边和所有的节点组成的图就是最小生成树。这就是 Prim 算法。
直观地看图，很容易找出集合 U 到 集合 U-V 的边中哪条边的权值是最小的，但在程序中穷举这些边，再找最小值，则时间复杂度太高。可以通过设置数组巧妙解决这个问题，closet[j] 表示集合 V-U 中的节点 j 到集合 U 中的最邻近点，lowcost[j] 表示集合 V-U 中节点 j 到集合 U 中最邻近点的边值，即边(j,closest[j]) 的权值。
例如在上图中，节点 7 到集合 U 中的最邻近点是2，cloeest[7]=2。节点 7 到最邻近点2 的边值为1，即边(2,7)的权值，记为 lowcost[7]=1,如下图所示。
所以只需在集合 V - U 中找到 lowcost[] 只最小的节点即可。
1 初始化
令集合 U={u0}，u0 属于 V，并初始化数组 closest[]、lowcost[]和s[]。
2 在集合 V-U 中找 lowcost 值最小的节点t，即 lowcost[t]=min{lowcost[j]},j 属于 V-U，满足该公式的节点 t 就是集合 V-U 中连接 U 的最邻近点。
3 将节点 t 加入集合 U 中。
4 如果集合 V - U 为空，则算法结束，否则转向步骤 5。
5 对集合 V-U 中的所有节点 j 都更新其 lowcost[] 和 closest[]。if(C[t][j]<lowcost[j]){lowcost[j]=C[t][j];closest[j]=t;},转向步骤2。
按照上面步骤，最终可以得到一棵权值之和最小的生成树。
图 G=（V,E）是一个无向连通带权图，如下图所示。
1 初始化。假设 u0=1，令集合 U={1},集合 V-U={2,3,4,5,6,7},s[1]=true，初始化数组 closest[]：除了节点1，其余节点均为1，表示集合 V-U 中的节点到集合 U 的最邻近点均为1.lowcost[]:节点1到集合 V-U 中节点的边值。closest[] 和 lowcost[] 如下图所示。
初始化后的图为：
2 找 lowcost 最小的节点，对应的 t=2，选中的边和节点如下图。
3 加入集合U中。将节点 t 加入集合 U 中，U={1,2}，同时更新 V-U={3,4,5,6,7}
4 更新。对 t 在集合 V-U 中的每一个邻接点 j,都可以借助 t 更新。节点 2 的邻接点是节点 3 和节点7。
C[2][3]=20<lowcost[3]=无穷大，更新最邻近距离 lowcost[3]=20,最邻近点 closest[3]=2;
C[2][7]=1<lowcost[7]=36，更新最邻近距离 lowcost[7]=1,最邻近点 closest[7]=2;
更新后的 closest[] 和 lowcost[] 如下图所示。
更新后的集合如下图所示：
5 找 lowcost 最小的节点，对应的 t=7，选中的边和节点如下图。
6 加入集合U中。将节点 t 加入集合 U 中，U={1,2,7}，同时更新 V-U={3,4,5,6}
7 更新。对 t 在集合 V-U 中的每一个邻接点 j,都可以借助 t 更新。节点 7 的邻接点是节点 3、4、5、6。
C[7][3]=4<lowcost[3]=20，更新最邻近距离 lowcost[3]=4,最邻近点 closest[3]=7;
C[7][4]=4<lowcost[4]=无穷大，更新最邻近距离 lowcost[3]=9,最邻近点 closest[4]=7;
C[7][5]=4<lowcost[5]=无穷大，更新最邻近距离 lowcost[3]=16,最邻近点 closest[5]=7;
C[7][6]=4<lowcost[6]=28，更新最邻近距离 lowcost[3]=25,最邻近点 closest[6]=7;
更新后的 closest[] 和 lowcost[] 如下图所示。
更新后的集合如下图所示：
8 找 lowcost 最小的节点，对应的 t=3，选中的边和节点如下图。
9 加入集合U中。将节点 t 加入集合 U 中，U={1,2,3,7}，同时更新 V-U={4,5,6}
10 更新。对 t 在集合 V-U 中的每一个邻接点 j,都可以借助 t 更新。节点 3 的邻接点是节点 4。
C[3][4]=15>lowcost[4]=9，不更新
closest[] 和 lowcost[] 数组不改变。
更新后的集合如下图所示：
11 找 lowcost 最小的节点，对应的 t=4，选中的边和节点如下图。
12 加入集合U中。将节点 t 加入集合 U 中，U={1,2,3,4,7}，同时更新 V-U={5,6}
13 更新。对 t 在集合 V-U 中的每一个邻接点 j,都可以借助 t 更新。节点 4 的邻接点是节点 5。
C[4][5]=3<lowcost[5]=16，更新最邻近距离 lowcost[5]=3,最邻近点 closest[5]=4;
更新后的 closest[] 和 lowcost[] 如下图所示。
更新后的集合如下图所示：
14 找 lowcost 最小的节点，对应的 t=5，选中的边和节点如下图。
15 加入集合U中。将节点 t 加入集合 U 中，U={1,2,3,4,5,7}，同时更新 V-U={6}
16 更新。对 t 在集合 V-U 中的每一个邻接点 j,都可以借助 t 更新。节点 5 的邻接点是节点 6。
C[5][6]=17<lowcost[6]=25，更新最邻近距离 lowcost[6]=17,最邻近点 closest[6]=5;
更新后的集合如下图所示：
17 找 lowcost 最小的节点，对应的 t=6，选中的边和节点如下图。
18 加入集合U中。将节点 t 加入集合 U 中，U={1,2,3,4,5,6,7}，同时更新 V-U={}
19 更新。对 t 在集合 V-U 中的每一个邻接点 j,都可以借助 t 更新。节点 6 在集合 V-U 中无邻接点。不用更新 closest[] 和 lowcost[] 。
20 得到的最小生成树如下。最小生成树的权值之和为 57.
27
4
0
晚上在 QQ 上看到昵称为“乱码”的好友回答了搜搜问问里一个问题： 在VBS中有办法定义字节数组么？ 在VBS中有办法定义字节数组么？就是字节子类型数组（VarType是8209的那种）注意不是V
例如，员工管理应用程序可能包括一个EmPloyee 类。然后可以用这个类来创建和维护特定实例，比如Gonn和Sally。 根据预定义的类创建对象常称为类的实例化（class insta
在自然语言中，我们理解抽象的概念是，一个物体的一种大的描述，这种描述对某类物体来说是共有的特性。那么在PHP中也是一样的，我们把一个类进行抽象，可以指明类的一般行为，这个类应该是一个模板，它指示它的
DBA_2PC_PENDING Oracle会自动处理分布事务，保证分布事务的一致性，所有站点全部提交或全部回滚。一般情况下，处理过程在很短的时间内完成，根本无法察觉到。但是，如果在commit或
目录 计算过程 投影分量计算 假设你有一家理发店,已经记录了过去一年中所有顾客的头发长度和发型偏好的数据。现在你想从这些数据中提取一些主要的信息,比如顾客最常
Object.defineProperty函数会直接在一个对象上定义一个新的属性，或者修改一个对象的现有属性，并返回此对象。 一、简单使用 const obj = {} Object.defineP
SPL官网 http://www.scudata.com.cn/ 介绍 业务逻辑经常包含较复杂的流程和计算，同时涉及数据库的读写。由于授权麻烦、影响数据库安全、无法迁移、技术要求高、编写困难等原因，很
SPL官网 http://www.scudata.com.cn/ 介绍 业务逻辑经常包含较复杂的流程和计算，同时涉及数据库的读写。由于授权麻烦、影响数据库安全、无法迁移、技术要求高、编写困难等原因，很
一 点睛 Thrift 是一歀基于 CS 架构的 RPC 框架，最初由 Facebook 研发，2008 年转入 Apache 组织。开发人员可以使用 Thrift 提供的 IDL（接口定义语言）来定
数据库应用程序与主应用程序分开存在，并存储数据集合。 每个数据库都使用一个或多个API来创建，访问，管理，搜索和复制其包含的数据。 数据库还使用非关系数据源，例如对象或文件。 然而，数据库证明是大数
介绍 Ant是一个 Apache 基金会下的跨平台的基于 Java 语言开发的构件工具。在我们详细了解 Apache Ant 之前， 让我们来讲解为什么构建工具是需要最先了解的。 构建工具的需求
我现在正在尝试学习ocaml，并希望从一个小程序开始，生成所有位组合: [“0”，“0”，“0”] [“0”，“0”，“1”] [“0”，“1”，“0”] ... 等等 我的想法是下面的代码: let
我正在做我的介绍 C 类(class)作业，我的任务是执行以下任务...... 为一个函数编写代码，该函数通过值接收两个参数(a 和 b)并通过引用具有另外两个参数(c 和 d)。所有参数都是双倍的。
我希望提供有关我网站内容的快速演示，以及如何在用户访问我的页面后立即以正确的方式使用它们。我希望使用顶部的弹出式窗口进行演示。 我的意思是小信息框，一个接一个地通知用户各个步骤。任何人都可以帮助我如何
与C、Java等语言一样，JavaScript中可以用&&、||、!三个逻辑判断符来对boolean值进行逻辑判断。与C、Java不同的是，JavaScript中逻辑与(&&
JavaScript中，==与===操作符均可用于判断两个值是否相等；不同之处在于，如果进行判断的两个值类型不一致，===操作符会直接返回false，而==操作符则会在类型转换后再进行判断。详细的判
JavaScript中，object转换为boolean的操作非常简单：所有的object转换成boolean后均为true；即使是new Boolean(false)这样的object在转换为bo
在android开发中，当不满足触发条件就按返回键的时候，就要对此进行检测。尤其是当前Activity需要往前一个Activity传送消息时。即Activity1跳转到Activity3如果采用的是
背景 当要求系统启动一个应用程序时，系统会先查找当前命令是否是内部命令，若不是，则在当前目录下查找，如果仍没有找到，则在系统变量 Path 指定的路径去查找。JDK（Java Developmen
概述 想做一个微信的公众平台，阅读了微信官方给的网址接入的示例代码，发现有个问题好像一直都是半知半解的，就是在类里边直接使用$_GET。仔细查了下关于这方面的知识，发现PHP中这部分的基础知识掌握
我是一名优秀的程序员,十分优秀！