解决方案
据我所知,布莱恩的预感不仅正确,而且还有一个更强有力的命题:不在最小生成树中的每条边都恰好添加一个新的“基环”。
为了了解这一点,让我们看看当添加一条不在 MST 中的边 E 时会发生什么。让我们用最喜欢的数学方法来使事情复杂化并添加一些符号;)将原始图称为 G、添加 E G' 之前的图以及添加 E G'' 后的图。因此我们需要找出“基本周期计数”如何从 G' 变为 G''。
添加 E 必须至少关闭一个循环(否则 E 将首先出现在 G 的 MST 中)。显然,它必须在 G' 中已有的基础周期上添加至少一个“基周期”。但它会添加多个吗?
它不能添加超过两个,因为没有边可以是两个以上基循环的成员。但如果 E 是两个基循环的成员,那么这两个基循环的“并集”一定是 G' 中的基循环,因此我们再次得到循环数的变化仍然是 1。
因此,对于不在 MST 中的每条边,您都会获得一个新的基本周期。所以“计数”部分很简单。找到每个基循环的所有边有点棘手,但按照上面的推理,我认为这可以做到(在伪Python中):
for v in vertices[G]:
cycles[v] = []
for e in (edges[G] \ mst[G]):
cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
if cycle_to_split == None:
# we're adding a completely new cycle
path = find_path(e.node1, e.node2, mst[G])
for vertex on path:
cycles[vertex].append(path + [e])
cycles
else:
# we're splitting an existing base cycle
cycle1, cycle2 = split(cycle_to_split, e)
for vertex on cycle_to_split:
cycles[vertex].remove(cycle_to_split)
if vertex on cycle1:
cycles[vertex].append(cycle1)
if vertex on cycle2:
cycles[vertex].append(cycle2)
base_cycles = set(cycles)
编辑: :该代码应该找到图中的所有基本周期(底部设置的base_cycles)。假设您知道如何:
- 找到图的最小生成树 (mst[G])
- 查找两个列表之间的差异 (edges \ mst[G])
- 找到两个列表的交集
- 查找 MST 上两个顶点之间的路径
- 通过添加额外的边将循环分成两部分(分割函数)
主要还是遵循上面的讨论。对于不在 MST 中的每条边,有两种情况:它要么带来一个全新的基础周期,要么将现有的基础周期一分为二。为了跟踪这两种情况中的哪一种,我们跟踪顶点所属的所有基本循环(使用循环字典)。
其他提示
从头顶开始,我将首先查看任何最小生成树算法(Prim,Kruskal等)。没有更多的基本周期(如果我理解正确),而不是MST中没有的边....
以下是我的实际未经测试的 C#代码,用于查找所有这些“基本周期”:
public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
new Dictionary<VertexT, HashSet<List<EdgeT>>>();
// For each vertex, initialize the dictionary with empty sets of lists of
// edges
foreach (VertexT vertex in connectedComponent)
cycles.Add(vertex, new HashSet<List<EdgeT>>());
HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);
foreach (EdgeT edgeNotInMST in
GetIncidentEdges(connectedComponent).Except(spanningTree)) {
// Find one cycle to split, the HashSet resulted from the intersection
// operation will contain just one cycle
HashSet<List<EdgeT>> cycleToSplitSet =
cycles[(VertexT)edgeNotInMST.StartPoint]
.Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);
if (cycleToSplitSet.Count == 0) {
// Find the path between the current edge not in ST enpoints using
// the spanning tree itself
List<EdgeT> path =
FindPath(
(VertexT)edgeNotInMST.StartPoint,
(VertexT)edgeNotInMST.EndPoint,
spanningTree);
// The found path plus the current edge becomes a cycle
path.Add(edgeNotInMST);
foreach (VertexT vertexInCycle in VerticesInPathSet(path))
cycles[vertexInCycle].Add(path);
} else {
// Get the cycle to split from the set produced before
List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
List<EdgeT> cycle1 = new List<EdgeT>();
List<EdgeT> cycle2 = new List<EdgeT>();
SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);
// Remove the cycle that has been splitted from the vertices in the
// same cicle and add the results from the split operation to them
foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
cycles[vertex].Remove(cycleToSplit);
if (VerticesInPathSet(cycle1).Contains(vertex))
cycles[vertex].Add(cycle1);
if (VerticesInPathSet(cycle2).Contains(vertex))
cycles[vertex].Add(cycle2); ;
}
}
}
HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
// Create the set of cycles, in each vertex should be remained only one
// incident cycle
foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
ret.AddAll(remainingCycle);
return ret;
}
Oggy's 代码非常良好且清除但是我很确定它包含错误,或者我不理解你的伪python代码:)
cycles[v] = []
不能是边列表的顶点索引字典。在我看来,它必须是列表边缘的顶点索引字典。
并且,为了增加精确度:
for vertex on cycle_to_split:
循环到分割可能是有序边缘列表,因此要通过顶点迭代它,您必须在一组顶点中将其转换。这里的订单可以忽略不计,所以这是一个非常简单的算法。
我再说一遍,这是未经测试和不完整代码,但是向前迈进了一步。它仍然需要一个合适的图形结构(我使用incidency列表)和许多图表alghoritms,你可以在像Cormen这样的教科书中找到。我无法在教科书中找到FindPath()和SplitCycle(),并且非常难以在图形中的边数+顶点的线性时间内对它们进行编码。我会在这里测试时报告它们。
非常感谢Oggy!
检测循环的标准方法是使用两个迭代器 - 对于每次迭代,一个向前移动一步,另一个向前移动。如果有一个循环,它们会在某个时刻相互指向。
这种方法可以扩展到记录所发现的循环并继续前进。