我需要一个工作算法来在无向图中查找所有简单循环。我知道成本可能是指数的，问题是 NP 完全的，但我将在一个小图中（最多 20-30 个顶点）使用它，并且循环数量很少。
经过长时间的研究（主要是这里），我仍然没有工作方法。以下是我的搜索摘要：
无向图中的循环-> 仅检测是否存在循环
在无向图中查找多边形-> 非常好的描述，但没有解决方案
在有向图中查找所有循环-> 仅在有向图中查找循环
我找到的唯一解决我的问题的答案是这个：
似乎找到一组基本循环并对它们进行异或运算可以解决问题。找到一组基本循环很容易，但我不明白如何组合它们以获得图中的所有循环......
对于无向图，标准方法是寻找所谓的循环基：一组简单的循环，可以通过组合所有其他循环从中生成。这些不一定都是图中的简单循环。例如考虑下图：
A
/ \
B ----- C
\ /
D
这里有 3 个简单的循环：ABCA、BCDB 和 ABDCA。但是，您可以将其中的每 2 个作为基础，并将第 3 个作为 2 的组合。这与有向图有很大的不同，因为需要观察边缘方向，因此无法如此自由地组合循环。
为无向图寻找循环基的标准基线算法是这样的：构建一棵生成树，然后为不属于树的每个边从该边和树上的一些边构建一个循环。这样的循环必须存在，否则边缘将成为树的一部分。
例如，上面示例图的可能生成树之一是：
A
/ \
B C
\
D
不在树中的 2 条边是 BC 和 CD。对应的简单循环是ABCA和ABDCA。
您还可以构建以下生成树：
A
/
B ----- C
\
D
对于这个生成树，简单的循环是 ABCA 和 BCDB。
基线算法可以以不同的方式进行细化。据我所知，最好的改进属于 Paton（K. Paton，An algorithm for find a basic set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518.）。此处提供了 Java 的开源实现：http ://code.google.com/p/niographs/ 。
我应该提到你如何结合循环基础中的简单循环来形成新的简单循环。您首先以任何（但此后固定）顺序列出图形的所有边。然后，通过将 1 放置在属于循环的边的位置并将零放置在不属于循环的边的位置，您可以通过 0 和 1 的序列来表示循环。然后你对序列进行按位异或（XOR）。您执行 XOR 的原因是您想要排除属于两个循环的边，从而使组合循环不简单。您还需要通过检查序列的按位与是否不全为零来检查 2 个周期是否有一些共同的边缘。否则 XOR 的结果将是 2 个不相交的循环，而不是一个新的简单循环。
这是上面示例图的示例：
我们首先列出边：（（AB），（AC），（BC），（BD），（CD））。那么简单循环ABCA、BDCB和ABDCA表示为(1, 1, 1, 0, 0), (0, 0, 1, 1, 1)和(1, 1, 0, 1, 1)。现在我们可以用 BDCB 对 ABCA 进行异或运算，结果是 (1, 1, 0, 1, 1)，这正是 ABDCA。或者我们可以对 ABCA 和 ABDCA 进行异或运算，结果为 (0, 0, 1, 1, 1)。这正是BDCB。
给定一个循环基础，您可以通过检查 2 个或更多不同基础循环的所有可能组合来发现所有简单循环。该过程在此处进行了更详细的描述：http: //dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf第 14 页。
为了完整起见，我会注意到使用算法来查找有向图的所有简单循环似乎是可能的（而且效率低下）。无向图的每条边都可以用两条相反方向的有向边代替。然后有向图的算法应该可以工作。对于必须忽略的无向图的每条边，将有 1 个“假”2 节点循环，并且无向图的每个简单循环都会有顺时针和逆时针版本。用于在有向图中查找所有循环的算法的 Java 开源实现可以在我已经引用的链接中找到。
Axel，我已将您的代码翻译成 python。大约 1/4 的代码行并且更清晰易读。
graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
cycles = []
def main():
global graph
global cycles
for edge in graph:
for node in edge:
findNewCycles([node])
for cy in cycles:
path = [str(node) for node in cy]
s = ",".join(path)
print(s)
def findNewCycles(path):
start_node = path[0]
next_node= None
sub = []
#visit each edge and each node of each edge
for edge in graph:
node1, node2 = edge
if start_node in edge:
if node1 == start_node:
next_node = node2
else:
next_node = node1
if not visited(next_node, path):
# neighbor node not on path yet
sub = [next_node]
sub.extend(path)
# explore extended path
findNewCycles(sub);
elif len(path) > 2 and next_node == path[-1]:
# cycle found
p = rotate_to_smallest(path);
inv = invert(p)
if isNew(p) and isNew(inv):
cycles.append(p)
def invert(path):
return rotate_to_smallest(path[::-1])
# rotate cycle path such that it begins with the smallest node
def rotate_to_smallest(path):
n = path.index(min(path))
return path[n:]+path[:n]
def isNew(path):
return not path in cycles
def visited(node, path):
return node in path
main()
以下是基于深度优先搜索的 C#（和 Java，请参见答案末尾）的演示实现。
外循环扫描图的所有节点并从每个节点开始搜索。节点邻居（根据边列表）被添加到循环路径中。如果不能添加更多未访问的邻居，则递归结束。如果路径长于两个节点并且下一个邻居是路径的起点，则找到一个新的循环。为了避免重复循环，循环通过将最小节点旋转到开始来标准化。倒序循环也被考虑在内。
这只是一个幼稚的实现。经典论文是：Donald B. Johnson。找到有向图的所有基本电路。SIAM J. 计算机，4（1）：77–84，1975。
using System;
using System.Collections.Generic;
namespace akCyclesInUndirectedGraphs
{
class Program
{
// Graph modelled as list of edges
static int[,] graph =
{
{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}
};
static List<int[]> cycles = new List<int[]>();
static void Main(string[] args)
{
for (int i = 0; i < graph.GetLength(0); i++)
for (int j = 0; j < graph.GetLength(1); j++)
{
findNewCycles(new int[] {graph[i, j]});
}
foreach (int[] cy in cycles)
{
string s = "" + cy[0];
for (int i = 1; i < cy.Length; i++)
s += "," + cy[i];
Console.WriteLine(s);
}
}
static void findNewCycles(int[] path)
{
int n = path[0];
int x;
int[] sub = new int[path.Length + 1];
for (int i = 0; i < graph.GetLength(0); i++)
for (int y = 0; y <= 1; y++)
if (graph[i, y] == n)
// edge referes to our current node
{
x = graph[i, (y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
Array.Copy(path, 0, sub, 1, path.Length);
// explore extended path
findNewCycles(sub);
}
else if ((path.Length > 2) && (x == path[path.Length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
cycles.Add(p);
}
}
}
static bool equals(int[] a, int[] b)
{
bool ret = (a[0] == b[0]) && (a.Length == b.Length);
for (int i = 1; ret && (i < a.Length); i++)
if (a[i] != b[i])
{
ret = false;
}
return ret;
}
static int[] invert(int[] path)
{
int[] p = new int[path.Length];
for (int i = 0; i < path.Length; i++)
p[i] = path[path.Length - 1 - i];
return normalize(p);
}
// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.Length];
int x = smallest(path);
int n;
Array.Copy(path, 0, p, 0, path.Length);
while (p[0] != x)
{
n = p[0];
Array.Copy(p, 1, p, 0, p.Length - 1);
p[p.Length - 1] = n;
}
return p;
}
static bool isNew(int[] path)
{
bool ret = true;
foreach(int[] p in cycles)
if (equals(p, path))
{
ret = false;
break;
}
return ret;
}
static int smallest(int[] path)
{
int min = path[0];
foreach (int p in path)
if (p < min)
min = p;
return min;
}
static bool visited(int n, int[] path)
{
bool ret = false;
foreach (int p in path)
if (p == n)
{
ret = true;
break;
}
return ret;
}
}
}
演示图的周期：
1,3,2
1,4,3,2
1,4,6,2
1,3,4,6,2
1,4,6,2,3
1,4,3
2,6,4,3
7,9,8
用Java编码的算法：
import java.util.ArrayList;
import java.util.List;
public class GraphCycleFinder {
// Graph modeled as list of edges
static int[][] graph =
{
{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}
};
static List<int[]> cycles = new ArrayList<int[]>();
/**
* @param args
*/
public static void main(String[] args) {
for (int i = 0; i < graph.length; i++)
for (int j = 0; j < graph[i].length; j++)
{
findNewCycles(new int[] {graph[i][j]});
}
for (int[] cy : cycles)
{
String s = "" + cy[0];
for (int i = 1; i < cy.length; i++)
{
s += "," + cy[i];
}
o(s);
}
}
static void findNewCycles(int[] path)
{
int n = path[0];
int x;
int[] sub = new int[path.length + 1];
for (int i = 0; i < graph.length; i++)
for (int y = 0; y <= 1; y++)
if (graph[i][y] == n)
// edge refers to our current node
{
x = graph[i][(y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
System.arraycopy(path, 0, sub, 1, path.length);
// explore extended path
findNewCycles(sub);
}
else if ((path.length > 2) && (x == path[path.length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
{
cycles.add(p);
}
}
}
}
// check of both arrays have same lengths and contents
static Boolean equals(int[] a, int[] b)
{
Boolean ret = (a[0] == b[0]) && (a.length == b.length);
for (int i = 1; ret && (i < a.length); i++)
{
if (a[i] != b[i])
{
ret = false;
}
}
return ret;
}
// create a path array with reversed order
static int[] invert(int[] path)
{
int[] p = new int[path.length];
for (int i = 0; i < path.length; i++)
{
p[i] = path[path.length - 1 - i];
}
return normalize(p);
}
// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.length];
int x = smallest(path);
int n;
System.arraycopy(path, 0, p, 0, path.length);
while (p[0] != x)
{
n = p[0];
System.arraycopy(p, 1, p, 0, p.length - 1);
p[p.length - 1] = n;
}
return p;
}
// compare path against known cycles
// return true, iff path is not a known cycle
static Boolean isNew(int[] path)
{
Boolean ret = true;
for(int[] p : cycles)
{
if (equals(p, path))
{
ret = false;
break;
}
}
return ret;
}
static void o(String s)
{
System.out.println(s);
}
// return the int of the array which is the smallest
static int smallest(int[] path)
{
int min = path[0];
for (int p : path)
{
if (p < min)
{
min = p;
}
}
return min;
}
// check if vertex n is contained in path
static Boolean visited(int n, int[] path)
{
Boolean ret = false;
for (int p : path)
{
if (p == n)
{
ret = true;
break;
}
}
return ret;
}
}
这只是这个算法的一个非常蹩脚的 MATLAB 版本，它改编自上面的 python 代码，供任何可能需要它的人使用。
function cycleList = searchCycles(edgeMap)
tic
global graph cycles numCycles;
graph = edgeMap;
numCycles = 0;
cycles = {};
for i = 1:size(graph,1)
for j = 1:2
findNewCycles(graph(i,j))
end
end
% print out all found cycles
for i = 1:size(cycles,2)
cycles{i}
end
% return the result
cycleList = cycles;
toc
function findNewCycles(path)
global graph cycles numCycles;
startNode = path(1);
nextNode = nan;
sub = [];
% visit each edge and each node of each edge
for i = 1:size(graph,1)
node1 = graph(i,1);
node2 = graph(i,2);
if node1 == startNode
nextNode = node2;
elseif node2 == startNode
nextNode = node1;
end
if ~(visited(nextNode, path))
% neighbor node not on path yet
sub = nextNode;
sub = [sub path];
% explore extended path
findNewCycles(sub);
elseif size(path,2) > 2 && nextNode == path(end)
% cycle found
p = rotate_to_smallest(path);
inv = invert(p);
if isNew(p) && isNew(inv)
numCycles = numCycles + 1;
cycles{numCycles} = p;
end
end
end
function inv = invert(path)
inv = rotate_to_smallest(path(end:-1:1));
% rotate cycle path such that it begins with the smallest node
function new_path = rotate_to_smallest(path)
[~,n] = min(path);
new_path = [path(n:end), path(1:n-1)];
function result = isNew(path)
global cycles
result = 1;
for i = 1:size(cycles,2)
if size(path,2) == size(cycles{i},2) && all(path == cycles{i})
result = 0;
break;
end
end
function result = visited(node,path)
result = 0;
if isnan(node) && any(isnan(path))
result = 1;
return
end
for i = 1:size(path,2)
if node == path(i)
result = 1;
break
end
end
这是上面python代码的C++版本：
std::vector< std::vector<vertex_t> > Graph::findAllCycles()
{
std::vector< std::vector<vertex_t> > cycles;
std::function<void(std::vector<vertex_t>)> findNewCycles = [&]( std::vector<vertex_t> sub_path )
{
auto visisted = []( vertex_t v, const std::vector<vertex_t> & path ){
return std::find(path.begin(),path.end(),v) != path.end();
};
auto rotate_to_smallest = []( std::vector<vertex_t> path ){
std::rotate(path.begin(), std::min_element(path.begin(), path.end()), path.end());
return path;
};
auto invert = [&]( std::vector<vertex_t> path ){
std::reverse(path.begin(),path.end());
return rotate_to_smallest(path);
};
auto isNew = [&cycles]( const std::vector<vertex_t> & path ){
return std::find(cycles.begin(), cycles.end(), path) == cycles.end();
};
vertex_t start_node = sub_path[0];
vertex_t next_node;
// visit each edge and each node of each edge
for(auto edge : edges)
{
if( edge.has(start_node) )
{
vertex_t node1 = edge.v1, node2 = edge.v2;
if(node1 == start_node)
next_node = node2;
else
next_node = node1;
if( !visisted(next_node, sub_path) )
{
// neighbor node not on path yet
std::vector<vertex_t> sub;
sub.push_back(next_node);
sub.insert(sub.end(), sub_path.begin(), sub_path.end());
findNewCycles( sub );
}
else if( sub_path.size() > 2 && next_node == sub_path.back() )
{
// cycle found
auto p = rotate_to_smallest(sub_path);
auto inv = invert(p);
if( isNew(p) && isNew(inv) )
cycles.push_back( p );
}
}
}
};
for(auto edge : edges)
{
findNewCycles( std::vector<vertex_t>(1,edge.v1) );
findNewCycles( std::vector<vertex_t>(1,edge.v2) );
}
}
受@LetterRip 和@Axel Kemper 启发这是Java 的较短版本：
public static int[][] graph =
{
{1, 2}, {2, 3}, {3, 4}, {2, 4},
{3, 5}
};
public static Set<List<Integer>> cycles = new HashSet<>();
static void findNewCycles(ArrayList<Integer> path) {
int start = path.get(0);
int next = -1;
for (int[] edge : graph) {
if (start == edge[0] || start == edge[1]) {
next = (start == edge[0]) ? edge[1] : edge[0];
if (!path.contains(next)) {
ArrayList<Integer> newPath = new ArrayList<>();
newPath.add(next);
newPath.addAll((path));
findNewCycles(newPath);
} else if (path.size() > 2 && next == path.get(path.size() - 1)) {
List<Integer> normalized = new ArrayList<>(path);
Collections.sort(normalized);
cycles.add(normalized);
}
}
}
}
public static void detectCycle() {
for (int i = 0; i < graph.length; i++)
for (int j = 0; j < graph[i].length; j++) {
ArrayList<Integer> path = new ArrayList<>();
path.add(graph[i][j]);
findNewCycles(path);
}
for (List<Integer> c : cycles) {
System.out.println(c);
}
}
这是上面python代码的vb .net版本：
Module Module1
' Graph modelled as list of edges
Public graph As Integer(,) = {{{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}}
Public cycles As New List(Of Integer())()
Sub Main()
For i As Integer = 0 To graph.GetLength(0) - 1
For j As Integer = 0 To graph.GetLength(1) - 1
findNewCycles(New Integer() {graph(i, j)})
Next
Next
For Each cy As Integer() In cycles
Dim s As String
s = cy(0)
For i As Integer = 1 To cy.Length - 1
s = s & "," & cy(i)
Next
Console.WriteLine(s)
Debug.Print(s)
Next
End Sub
Private Sub findNewCycles(path As Integer())
Dim n As Integer = path(0)
Dim x As Integer
Dim [sub] As Integer() = New Integer(path.Length) {}
For i As Integer = 0 To graph.GetLength(0) - 1
For y As Integer = 0 To 1
If graph(i, y) = n Then
' edge referes to our current node
x = graph(i, (y + 1) Mod 2)
If Not visited(x, path) Then
' neighbor node not on path yet
[sub](0) = x
Array.Copy(path, 0, [sub], 1, path.Length)
' explore extended path
findNewCycles([sub])
ElseIf (path.Length > 2) AndAlso (x = path(path.Length - 1)) Then
' cycle found
Dim p As Integer() = normalize(path)
Dim inv As Integer() = invert(p)
If isNew(p) AndAlso isNew(inv) Then
cycles.Add(p)
End If
End If
End If
Next
Next
End Sub
Private Function equals(a As Integer(), b As Integer()) As Boolean
Dim ret As Boolean = (a(0) = b(0)) AndAlso (a.Length = b.Length)
Dim i As Integer = 1
While ret AndAlso (i < a.Length)
If a(i) <> b(i) Then
ret = False
End If
i += 1
End While
Return ret
End Function
Private Function invert(path As Integer()) As Integer()
Dim p As Integer() = New Integer(path.Length - 1) {}
For i As Integer = 0 To path.Length - 1
p(i) = path(path.Length - 1 - i)
Next
Return normalize(p)
End Function
' rotate cycle path such that it begins with the smallest node
Private Function normalize(path As Integer()) As Integer()
Dim p As Integer() = New Integer(path.Length - 1) {}
Dim x As Integer = smallest(path)
Dim n As Integer
Array.Copy(path, 0, p, 0, path.Length)
While p(0) <> x
n = p(0)
Array.Copy(p, 1, p, 0, p.Length - 1)
p(p.Length - 1) = n
End While
Return p
End Function
Private Function isNew(path As Integer()) As Boolean
Dim ret As Boolean = True
For Each p As Integer() In cycles
If equals(p, path) Then
ret = False
Exit For
End If
Next
Return ret
End Function
Private Function smallest(path As Integer()) As Integer
Dim min As Integer = path(0)
For Each p As Integer In path
If p < min Then
min = p
End If
Next
Return min
End Function
Private Function visited(n As Integer, path As Integer()) As Boolean
Dim ret As Boolean = False
For Each p As Integer In path
If p = n Then
ret = True
Exit For
End If
Next
Return ret
End Function
端模块
这是python代码的节点版本。
const graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
let cycles = []
function main() {
for (const edge of graph) {
for (const node of edge) {
findNewCycles([node])
}
}
for (cy of cycles) {
console.log(cy.join(','))
}
}
function findNewCycles(path) {
const start_node = path[0]
let next_node = null
let sub = []
// visit each edge and each node of each edge
for (const edge of graph) {
const [node1, node2] = edge
if (edge.includes(start_node)) {
next_node = node1 === start_node ? node2 : node1
}
if (notVisited(next_node, path)) {
// eighbor node not on path yet
sub = [next_node].concat(path)
// explore extended path
findNewCycles(sub)
} else if (path.length > 2 && next_node === path[path.length - 1]) {
// cycle found
const p = rotateToSmallest(path)
const inv = invert(p)
if (isNew(p) && isNew(inv)) {
cycles.push(p)
}
}
}
}
function invert(path) {
return rotateToSmallest([...path].reverse())
}
// rotate cycle path such that it begins with the smallest node
function rotateToSmallest(path) {
const n = path.indexOf(Math.min(...path))
return path.slice(n).concat(path.slice(0, n))
}
function isNew(path) {
const p = JSON.stringify(path)
for (const cycle of cycles) {
if (p === JSON.stringify(cycle)) {
return false
}
}
return true
}
function notVisited(node, path) {
const n = JSON.stringify(node)
for (const p of path) {
if (n === JSON.stringify(p)) {
return false
}
}
return true
}
main()
这不是答案！
@尼古拉·奥格尼亚诺
1. 试图理解我们应该如何用简单循环生成组合循环
我试图理解你提到的
您还需要通过检查序列的按位与是否不全为零来检查 2 个周期是否有一些共同的边缘。否则 XOR 的结果将是 2 个不相交的循环，而不是一个新的简单循环。
我想了解我们应该如何处理如下图：
0-----2-----4
| /| /
| / | /
| / | /
| / | /
|/ |/
1-----3
假设基本/简单循环是：
0 1 2
1 2 3
2 3 4
显然，如果我使用以下按位XORand AND，它将错过循环 0 1 3 4 2。
bitset<MAX> ComputeCombinedCycleBits(const vector<bitset<MAX>>& bsets) {
bitset<MAX> bsCombo, bsCommonEdgeCheck; bsCommonEdgeCheck.set();
for (const auto& bs : bsets)
bsCombo ^= bs, bsCommonEdgeCheck &= bs;
if (bsCommonEdgeCheck.none()) bsCombo.reset();
return bsCombo;
}
我认为主要问题在这里bsCommonEdgeCheck &= bs？如果有 3 个以上的简单循环组成联合循环，我们应该使用什么？
2.试图理解我们如何得到联合循环的顺序
例如，使用下图：
0-----1
|\ /|
| \ / |
| X |
| / \ |
|/ \|
3-----2
假设基本/简单循环是：
0 1 2
0 2 3
0 1 3
使用按位异或后，我们完全失去了简单循环的顺序，如何获得组合循环的节点顺序？
上面的循环查找器似乎有一些问题。C# 版本无法找到一些循环。我的图表是：
{2,8},{4,8},{5,8},{1,9},{3,9},{4,9},{5,9},{6,9},{1,10},
{4,10},{5,10},{6,10},{7,10},{1,11},{4,11},{6,11},{7,11},
{1,12},{2,12},{3,12},{5,12},{6,12},{2,13},{3,13},{4,13},
{6,13},{7,13},{2,14},{5,14},{7,14}
例如，循环：1-9-3-12-5-10未找到。我也尝试了 C++ 版本，它返回的周期数非常大（数千万），这显然是错误的。很可能，它与周期不匹配。
对不起，我有点紧张，我没有进一步调查。我根据 Nikolay Ognyanov 的帖子编写了自己的版本（非常感谢您的帖子）。对于上面的图表，我的版本返回 8833 个周期，我正在尝试验证它是否正确。C# 版本返回 8397 个周期。
Matlab 版本遗漏了一些东西，函数 findNewCycles(path) 应该是：
函数 findNewCycles(路径)
global graph cycles numCycles;
startNode = path(1);
nextNode = nan;
sub = [];
% visit each edge and each node of each edge
for i = 1:size(graph,1)
node1 = graph(i,1);
node2 = graph(i,2);
if (node1 == startNode) || (node2==startNode) %% this if is required
if node1 == startNode
nextNode = node2;
elseif node2 == startNode
nextNode = node1;
end
if ~(visited(nextNode, path))
% neighbor node not on path yet
sub = nextNode;
sub = [sub path];
% explore extended path
findNewCycles(sub);
elseif size(path,2) > 2 && nextNode == path(end)
% cycle found
p = rotate_to_smallest(path);
inv = invert(p);
if isNew(p) && isNew(inv)
numCycles = numCycles + 1;
cycles{numCycles} = p;
end
end
end
end