将循环图分解为最短路径子图的极小数目
给定一个循环图，我正在寻找一种算法，它将这个图分解成无圈子图。每个子图都有一个根顶点，其中这个顶点是计算最短路径的源。例如，给定下面的循环图，其中循环介于3,4和5之间：
+-------------------------+
| |
| |
+----------+----------+ |
v | v |
+---+ +---+ +---+ +---+ +---+ |
| 1 | --> | 3 | <--> | 4 | <--> | 5 | --> | 6 | |
+---+ +---+ +---+ +---+ +---+ |
^ |
| |
| |
+---+ |
| 2 | |
+---+ |
+---+ |
| 7 | <---------------------+
+---+与1相关的最短路径子图是：
+---+ +---+ +---+ +---+
| 1 | --> | 3 | --> | 4 | --> | 7 |
+---+ +---+ +---+ +---+
|
|
v
+---+ +---+
| 5 | --> | 6 |
+---+ +---+与2相关的最短路径子图是：
+---+
| 7 |
+---+
^
|
|
+---+ +---+ +---+ +---+
| 2 | --> | 4 | --> | 5 | --> | 6 |
+---+ +---+ +---+ +---+
|
|
v
+---+
| 3 |
+---+与5相关的最短路径图是：
+---+ +---+ +---+ +---+
| 6 | <-- | 5 | --> | 4 | --> | 7 |
+---+ +---+ +---+ +---+
|
|
v
+---+
| 3 |
+---+注意，相对于3的最短路径子图是1的子集，4是2的子集，6和7是leafs。
我目前(天真)的解决方案是为每个节点执行一个BFS，对访问的节点进行标记以防止循环。然后检查这些子图是否是彼此的子集，以创建最小数目的不同子图。有什么更好、更正式的解决方案吗？
编辑在我的情况下的图是不加权的，但是对于后代有一个通用的解决方案是很好的。
(用http://bloodgate.com/graph-demo制作的图形)
回答 1
Stack Overflow用户
发布于 2011-08-25 20:59:38
Templatety胡枝子，OP对"BFS“的使用表明该图是未加权的。
这里有一个算法，它与最终集合中每个根的和成正比，它是从根可以到达的子图大小的总和。对于有界度的图，这是输出大小的顺序。
出于唯一性的考虑，我将假设“最短路径”意味着长度最小-lex顺序。在较高层次上，我们计算一个处理顶点的顺序，这样如果顶点u的BFS树包含顶点v，则在v之前对u进行排序，每个顶点在线性时间内处理，包括确定它包含的顶点。
通过寻找强分量，对强分量进行拓扑排序，然后对每个单分量内的顶点进行任意排序，计算阶数。显然，u包含v，只有当从u可到达的顶点集是从v到的顶点的适当超集时，才能包含v。
若要处理顶点u，请从u中计算BFS树，然后确定其子树没有弧离开子树的顶点集--这些都是被包含的顶点。通过遍历树的深度来确定后者--首先，为每个顶点v记录一个区间I(v)，其左端点为入口时间，其右端点为退出时间。对于每个顶点v，计算包含I(v)的最小区间J(v)和具有弧v->w的所有I(w)，用DFS计算每个顶点v的最小区间K(v)，其中含有K(w)的最小区间K(v)包含v.
为什么要这么做？我们知道，根在u上的树的v子树是根在v上的树的子集，假设u包含v(换句话说，这两棵树是相等的)。很明显，从v的子树到v子树的每个弧线的头都到了v的子树，否则，就应该对头进行探索。相反地，假设u不包含v上的树，根在v上的树包含一个不存在于v子树中的顶点，因此有一个弧离开v的子树。
我希望这个描述对你是有用的，但我担心你的实际问题包括快速点到点最短路径查询和子二次空间，对此可能有更好的方法。
https://stackoverflow.com/questions/7196157
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号