连通分支算法

1. 已知一个无向有限图的邻接矩阵，怎么求这个图的连通分支数啊

求出Laplace矩阵的秩就可以了，因为0特征值个个数就是连通分支数。
也可以用类似于最小生成树的算法把所有的连通分支都找出来。

2. 为什么破圈法和避圈法为什么不能求一点至另一点的最短距离

1.1最小生成树

最小生成树：一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边，如图1.1.1所示。

图1.1.1 最小生成树示意图

设G = (V, E)是无向连通带权图，即一个网络。E中的每一条边（v, w）的权为W(v, w)。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

1.1.1避圈法

避圈法的主要思想就是：开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。避圈法主要分为两种：Prim算法和Kruskal算法，下面分别进行介绍。

1.1.1.1 Prim算法

设G = (V, E)是连通带权图，V = {1,2,…,n}。构造G的最小生成树Prim算法的基本思想是：首先置S = {1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S, j∈V – S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。图1.1.2显示了某一带权图。最小生成树的生成过程如下：

→=

c

13;1

→=

c

36;4

32;5

→=

c

c

→=

25;3

最终得到的最小生成树如图1.1.3所示。

图1.1.2 带权图G

图1.1.3 带权图G的最小生成树示意图

1.1.1.2 Kruskal算法

给定无向连通带权图G = (V, E), V = {1,2,...,n}。Kruskal算法构造G的最小生成树的基本思想是：

(1) 将G的n个顶点看成n个孤立的连通分支，并将所有的边按权从小到大排序；

(2) 从第一条边开始，依据每条边的权值递增的顺序检查每一条边，并按照下述方法连接两个不同的连通分支：当查看到第k条边(v, w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点时，就用边(v, w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接查看第k+1条边，这个过程一个进行到只剩下一个连通分支时为止。此时，已构成G的一棵最小生成树。

仍以图1.1.2所示的带权图G为例说明其最小生成树的生成过程，生成过程如下所示：

→=

c

13;1

25;3c →=

36;4c →=

23;5c →=

最终得到的最小生成树和图1.1.3所示是一样的。

1.1.2 破圈法

破圈法可以描述如下：

(1) 如果我们给的连通图G 中没有回路，那么G 本身就是一棵生成树；

(2) 若G 中只有一个回路，则删去G 的回路上的一条边（不删除结点），则产生的图仍是连通的且没有回路，则得到的子图就是图G 的一棵生成树；

(3) 若G 的回路不止一个，只要删去每一个回路上的一条边，直到G 的子图是连通没有回路且与图G 有一样的结点集，那么这个子图就是一棵生成树。

由于我们破坏回路的方法可以不一样，所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权最小，那么在删去回路上的边的时候，总是在保证带权图仍连通的前提下删掉权值较大的边，保留权值较小的边。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边所组成的图即为最小生成树。下面仍利用图1.1.2对破圈法进行说明。

首先是去除权值大的边，并且检测去除该边后整个图是否连通，对于图1.1.2来说，即第一步去掉权值为6的边，如图1.1.4所示。

图1.1.4 去掉权值为6的G 的示意图

从图中可以看出，去掉权值为6的边后整个图仍是连通的。所以接下来去除权值为5的边，并且检测去除该边后图是否连通，结果如图1.1.5所示。由图可知，去掉所有权值为5的边会造成图G 不连通，因此23;5c →=这条边是必须保留的。然后再去除权值为4的

边。由于权值为1、2、3、4的边分别连接着独立的节点，故都必须保留，得到的最小生成

图1.1.5 去掉权值为5的G的示意图

树结果与图1.1.3也是一样的。

1.1.3避圈法与破圈法比较

Prim算法是从空图出发，将点进行二分化，从而逐步加边得到最小生成树。它是近似求解算法，虽然对于大多数最小生成树问题都能求得最优解，但相当一部分求得的是近似最优解，具体应用时不一定很方便。但是它可以看作是很多种最小树算法的概括，在理论上有一定的意义。

Kruskal算法也是从空图出发。它是精确算法，即每次都能求得最优解，但对于规模较大的最小生成树问题，求解速度较慢。

破圈法是从图G出发，逐步去边破圈得到最小生成树。它最适合在图上工作，当图较大时，可以几个人同时在各个子图上工作，因此破圈法在实用上是很方便的。

￥
5.9
网络文库VIP限时优惠现在开通,立享6亿+VIP内容
立即获取
破圈法vs避圈法
1.1最小生成树

最小生成树：一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边，如图1.1.1所示。

图1.1.1 最小生成树示意图

设G = (V, E)是无向连通带权图，即一个网络。E中的每一条边（v, w）的权为W(v, w)。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

第 1 页
1.1.1避圈法

避圈法的主要思想就是：开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。避圈法主要分为两种：Prim算法和Kruskal算法，下面分别进行介绍。

1.1.1.1 Prim算法

设G = (V, E)是连通带权图，V = {1,2,…,n}。构造G的最小生成树Prim算法的基本思想是：首先置S = {1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S, j∈V – S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。图1.1.2显示了某一带权图。最小生成树的生成过程如下：

3. 编程计算无向图的连通分支数，求助

连通分量 在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。 在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
追问：
什么是极大连通子图呢
回答：
最大连通子图 也就是把图的所有结点用最少的边将其连接起来的子图，所以极大连通子图不唯一，也就是因为这个原因可以说最大连通子图是一个累赘概念，因为任何一个极大连通子图，其实都可以叫做最大连通子图，但是一般都不这么叫。

4. “强连通分支算法”相关证明

首先,这个算法求出的是一个有向图最大强连通子图.一个图的最大强连通子图只有一个解集(这没什么疑问吧).
那我只好理解为你要问这个算法如何求出的这个最大强连通子图（C）的解集.
首先改变边方向应该好理解,它能导出一个C。因为一个C里面的点在边改变后还是到能在一次深搜搜到的。唯一问题，如何保证不会搜出不是C的点。
这样的点有两种情况：在原图中这个点可以到达这个C但无法通过这个C到达它本身；可以通过C到达，但无法到达C。
第1种情况，这个点的编号肯定比C大，边变向后，就会先搜这个点，而且不会搜到C。
第2中情况雷同。

建议楼主在实践中采用求最早祖先的方法求最大强连通。方法也比较好理解，代码也短 ，只用一遍深搜就行。
希望楼主看完我的回答有所收益

5. 题目1:一个简单的算法演示程序(JAVA语言实现)

1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。
2. 可以进行手动演示，也可以自动步进式演示。
3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。
4. 不同的算法输入要求见下。
界面要求：
1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。
2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。
其他要求：
1. 标识符命名遵循Windows命名规范。
2. 能够注意各种异常处理，注重提高程序运行效率。
提交内容：
1. 全部源代码。
2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）
参考算法：
1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。
4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。

6. sparkgraphx的连通分支算法有什么作用

连通分支算法使用最小编号的顶点来标记每个连通分支。在一个社会网络，连通图近似簇。这里我们计算一个连通分支实例，所使用的数据集和PageRank一样。

7. 求krusal算法原理

kruskal算法构造G的最小生成树的思想是，首先将G的n个顶点看成是n个孤立的连通分支，将所有的边按权从小到大排序，然后从第一条边开始，依边权递增的顺序查看每一边，并按下述方法连接两个不同的连通分支:当查看到第k条边(v,w)时，如果端点v,w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边。这个过程就是G的一棵最小生成树。

8. 什么是分支算法

分支限界算法：
分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：

1 ．产生当前扩展结点的所有孩子结点；

2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；

3 ．将其余的孩子结点加入活结点表；

4 ．从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式：

1 ． FIFO(First In First Out) 分支定界算法：按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。

2 ．最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个耗费或收益。如果要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点；如果要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。

又称分支定界搜索法。过程系统综合的一类方法。该法是将原始问题分解，产生一组子问题。分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝）。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。

分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。

在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。
搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。
所以，对程序进行优化，就成为搜索算法编程中最关键的一环。
本文所要讨论的便是搜索算法中优化程序的一种基本方法枣“剪枝”。

什么是剪枝
相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的：
1、这个方向有路可走，我没走过
2、往这个方向前进
3、是死胡同，往回走，回到上一个路口
4、重复第一步，直到找着出口
这样的思路很好理解，编程起来也比较容易。但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨，无法忍受。
我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？
答案是：可以的。
剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。
搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则。
剪枝的原则
1、正确性
正如上文所述，枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也剪掉了的话，剪枝也就失去了意义。所以，剪枝的前提是一定要保证不丢失正确的结果。
2、准确性
在保证了正确性的基础上，我们应该根据具体问题具体分析，采用合适的判断手段，使不包含最优解的枝条尽可能多的被剪去，以达到程序“最优化”的目的。可以说，剪枝的准确性，是衡量一个优化算法好坏的标准。
3、高效性 设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少。但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾。
因此，如何在优化与效率之间寻找一个平衡点，使得程序的时间复杂度尽可能降低，同样是非常重要的。倘若一个剪枝的判断效果非常好，但是它却需要耗费大量的时间来判断、比较，结果整个程序运行起来也跟没有优化过的没什么区别，这样就太得不偿失了。
综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。
剪枝算法按照其判断思路可大致分成两类：可行性剪枝及最优性剪枝。

对于分支定界算法,上界是已求得的可行解的目标函数值中的最小者,分为初始上界和在探测过程中产生的动态上界.分支定界法在求最优解的迭代过程中, 若某结点估计的下界不小于已知的上界, 则不必从该节点往下继续搜索. 因此若能产生一个较好的上界, 可以消除许多不必要的列举计算.

分支定界算法的实现
在描述分支定界算法步骤之前, 先对算法涉及到的有关术语进行定义如下:
p —— 分支层数;
C*—— 当前最优目标函数值;
P*—— 相应于C*的工件顺序;
P1—— 当前节点(现在需要进行分支的节点)所对应的部分序列.
分支定界算法的实施步骤如下:
步骤1 初始化: 设置p = 0, P 1 = Á (空集) , C* = ∞.设当前节点总是与P 1 相对应. 此时, 当前节点即根节点.
步骤2 计算从当前节点分支得到的各个子节点的下界, 并按下界值由小到大对各子节点排序. 令p ←p + 1.
步骤3 如果当前节点被探测尽, 令p ←p - 1, 转步骤6. 否则, 设当前层(第p 层) 各活动子节点中具有最小下界值的节点为Q , 则在P 1末尾加入Q 对应第p 位置上的工件, 此时的当前节点转为Q , 转步骤4.
步骤4 因为当前节点是同层同父节点具有最小下界值的节点, 如果当前节点下界值大于或等于C* , 则不必再搜索当前节点及其同层同父的活动节点, 这样, 当前节点的上一层节点(父节点)被探测尽, p ←p - 1, 去掉P 1 中的最后一个工件,转步骤6. 否则, 转步骤5.
步骤5 如果p = n, 则得到一个较优顺序.令P* = P 1, C* 是当前节点的下界值, p ←p - 1,去掉P 1 中最后一个工件, 转步骤6; 否则转步骤2.
步骤6 若p ≠ 0, 去掉P 1 中最后一个工件,转步骤3; 否则, 算法停止. C* 是最优的目标函数值, P* 是最优顺序.

分支结构算法的实现(编程基础)

我现在学到了分支结构了。又遇到问题了，不知道你还在不在,可以帮我吗?(可以，没问题.)
1、用Pascal语言表示下列的条件表达式：
（1）：x小于10；
（2）：0<=y<=5;(‘小于等于’不会打)
（3）：x大于5或x为负数；
（4）：ch在“A”和“Z”之间（包括“A”和“Z”）；
（5）：年龄（age)不小于18，国籍(natioality)不是中国“CHINA”,也不是朝鲜“KOREA”的男性公民(sex=`maie`);
（6）：正数，在2～100之间且不能被2，或3，或5整除。
2、试写出下列各项的Pascal语句：
（1）：如果wage大于10000，便减去10%的wage.
（2）：如果Choice的值为1，则读取x的值，并打印x的平方；否则读取y的值，并打印y的平方。

9. 麻烦问下各路大牛 怎么求无向图中的最小环长度 万分感谢

我用的是Dijsktra算法进行的计算。假设一个环中有两个顶点A,B，那么走完这个环的最小路程是从A到B的最短路+去掉A到B的最短路上的所有路径后的A到B（B到A）的最短路（就相当于是从A走到B再走到A的最短路）

因此，在外层枚举A，算出A到各个点的最短路，同时记下路径。然后枚举每一个B，删掉A到B上最短路径所经过的边，再算一次A到B的最短路径，然后两者相加，求得一个环的最短路。最后找一个最小的环的长度，输出即可。时间复杂度到了O(n^4)，所以我有一组花了0.9s.

但是这道题的难点在于那个BT的INPUT-------从来都没有见过的图的输入方式：告诉的是边与边的关系。

我是这样解决的：找出所有的边的两个端点（不管是否重复），并把这些端点连了哪些边记录下来。然后去掉重复的顶点，剩下的就是图的顶点。接着通过枚举寻找任意两个顶点是否都连了相同的边，如果连了，说明这两个顶点就是被这条边所连，因此就可以在邻接矩阵中记录下来。时间复杂度O(n^3)

这一题是我一次AC的。。。难得在USACO Cheapter4 里面一次AC哈。。

Cherry还有更好的O(n^3)的算法，我也不知道怎么做的。感兴趣的去看一下子。

10. 无向图用矩阵幂算法如何求其连通分支数

设连通矩阵A，x->y若连通，则A[x][y]=1（当然也有A[y][x]=1），否则A[x][y]=0，特别地有A[x][x]=1

此时A[x][y]>0当且仅当x->y有直接连通的边

再考虑A^2=A*A，A^2[x][y]>0当且仅当x->y有长度小于等于2条边的通路

最后，A^n[x][y]>0当且仅当x->y有任意长度的通路（n是节点数目）

所以用快速幂求出A^n，然后将A^n作为邻接矩阵，DFS一遍就可以了