在有向图中寻找最短周期的算法 [英] Algorithm for finding shortest cycles in directed graph

问题描述

例如，给出一个图：

p>

最短的周期为：ACDA，DABD

如果我只需要找到一个最短周期，那么我会在每个顶点运行BFS并跟踪最小周期。但我不知道如何枚举所有最小的周期。

有一个类似的 SO问题，但是最小循环是不是较小循环的并集的循环。在这里，我只寻找具有最少边数的循环。

解决方案

以拓扑排序的方式运行多个DFS搜索：从一个随机顶点开始，只要有一些未探索的顶点，就继续运行新的DFS搜索。

在搜索中，只要找到后沿，你知道（1）有一个周期（2）该周期中的边数。如果您还需要获取循环中的边缘列表，请为每个当前检测到的循环保留一个数组，并在DFS调用图中回溯时填充它。如果后端是一个节点A-> B，当你到达后面的节点B时，该数组将包含循环中的所有边。

当然，要跟踪到目前为止发现的最短周期，以避免记录边界列表的周期长于此最小值。

A shortest cycle is one with the minimum number of edges.

For example, given a graph:

The shortest cycles are: ACDA, DABD

If I only needed to find one shortest cycle, I would just run BFS on every vertex and keep track of the smallest cycle. But I don't know how to enumerate all smallest cycles.

There is a similar SO question on enumerating minimal cycles in a digraph, but there a minimal cycle is one which is not a union of smaller cycles. Here I am only looking for the cycles with the minimum number of edges.

解决方案

Run a number of DFS searches as in topological sort: start from a random vertex, and continue running new DFS searches as long as there are some unexplored vertices.

In a search, as soon as you find a back edge, you know that (1) there's a cycle (2) the number of edges in that cycle. If you also need to get a list of edges in the cycle, keep an array for each "currently detected cycle" and fill it as you backtrack in the DFS call graph. If the back-edge was a node A->B, When you'll reach back node B, the array is going to contain all edges in the cycle.

Of course, keep in track the "shortest cycle found so far" to avoid bookkeeping edge lists for cycles that are longer than this minimum.

这篇关于在有向图中寻找最短周期的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！