我很喜欢这个问题，谢谢！:P
我有一个用C#编写的解决方案。找到循环的算法非常简短（约10行），但是周围有很多杂乱的东西（例如Node和Edge类的实现）。
我使用了变量命名约定，字母“e”表示边，字母“a”表示边开始的节点，“b”表示它连接到的节点。根据这些约定，这就是算法：
public static IEnumerable<Cycle> FindAllCycles()
{
HashSet<Node> alreadyVisited = new HashSet<Node>();
alreadyVisited.Add(Node.AllNodes[0]);
return FindAllCycles(alreadyVisited, Node.AllNodes[0]);
}
private static IEnumerable<Cycle> FindAllCycles(HashSet<Node> alreadyVisited, Node a)
{
for (int i = 0; i < a.Edges.Count; i++)
{
Edge e = a.Edges[i];
if (alreadyVisited.Contains(e.B))
{
yield return new Cycle(e);
}
else
{
HashSet<Node> newSet = i == a.Edges.Count - 1 ? alreadyVisited : new HashSet<Node>(alreadyVisited);
newSet.Add(e.B);
foreach (Cycle c in FindAllCycles(newSet, e.B))
{
c.Build(e);
yield return c;
}
}
}
}
它有一个优化可以重复使用一些Hashsets，这可能会令人困惑。我已经包含了以下代码，它产生完全相同的结果，但是这个实现没有优化，所以你可以更容易地理解它是如何工作的。
private static IEnumerable<Cycle> FindAllCyclesUnoptimized(HashSet<Node> alreadyVisited, Node a)
{
foreach (Edge e in a.Edges)
if (alreadyVisited.Contains(e.B))
yield return new Cycle(e);
else
{
HashSet<Node> newSet = new HashSet<Node>(alreadyVisited);
newSet.Add(e.B);//EDIT: thnx dhsto
foreach (Cycle c in FindAllCyclesUnoptimized(newSet, e.B))
{
c.Build(e);
yield return c;
}
}
}
这里使用了 节点(Node)、边缘(Edge)和循环(Cycle) 的以下实现。它们都非常简单明了，尽管我花了很多时间使一切都不可变，并且成员尽可能不可访问。
public sealed class Node
{
public static readonly ReadOnlyCollection<Node> AllNodes;
internal static readonly List<Node> allNodes;
static Node()
{
allNodes = new List<Node>();
AllNodes = new ReadOnlyCollection<Node>(allNodes);
}
public static void SetReferences()
{//call this method after all nodes have been created
foreach (Edge e in Edge.AllEdges)
e.A.edge.Add(e);
}
//All edges linking *from* this node, not to it.
//The variablename "Edges" it quite unsatisfactory, but I couldn't come up with anything better.
public ReadOnlyCollection<Edge> Edges { get; private set; }
internal List<Edge> edge;
public int Index { get; private set; }
public Node(params int[] nodesIndicesConnectedTo)
{
this.edge = new List<Edge>(nodesIndicesConnectedTo.Length);
this.Edges = new ReadOnlyCollection<Edge>(edge);
this.Index = allNodes.Count;
allNodes.Add(this);
foreach (int nodeIndex in nodesIndicesConnectedTo)
new Edge(this, nodeIndex);
}
public override string ToString()
{
return this.Index.ToString();
}
}
public sealed class Edge
{
public static readonly ReadOnlyCollection<Edge> AllEdges;
static readonly List<Edge> allEdges;
static Edge()
{
allEdges = new List<Edge>();
AllEdges = new ReadOnlyCollection<Edge>(allEdges);
}
public int Index { get; private set; }
public Node A { get; private set; }
public Node B { get { return Node.allNodes[this.bIndex]; } }
private readonly int bIndex;
internal Edge(Node a, int bIndex)
{
this.Index = allEdges.Count;
this.A = a;
this.bIndex = bIndex;
allEdges.Add(this);
}
public override string ToString()
{
return this.Index.ToString();
}
}
public sealed class Cycle
{
public readonly ReadOnlyCollection<Edge> Members;
private List<Edge> members;
private bool IsComplete;
internal void Build(Edge member)
{
if (!IsComplete)
{
this.IsComplete = member.A == members[0].B;
this.members.Add(member);
}
}
internal Cycle(Edge firstMember)
{
this.members = new List<Edge>();
this.members.Add(firstMember);
this.Members = new ReadOnlyCollection<Edge>(this.members);
}
public override string ToString()
{
StringBuilder result = new StringBuilder();
foreach (var member in this.members)
{
result.Append(member.Index.ToString());
if (member != members[members.Count - 1])
result.Append(", ");
}
return result.ToString();
}
}
接下来，为了说明您可能如何使用这个小型API，我已经实现了您的两个示例。 基本上就是通过指定节点链接到哪些节点来创建所有节点，然后调用SetReferences()来设置一些引用。之后，调用公开可访问的FindAllCycles()应该返回所有循环。我已经排除了重置静态成员的任何代码，但这很容易实现。它只需要清除所有静态列表。
static void Main(string[] args)
{
InitializeExampleGraph1();//or: InitializeExampleGraph2();
Node.SetReferences();
var allCycles = FindAllCycles().ToList();
}
static void InitializeExampleGraph1()
{
new Node(1, 2);//says that the first node(node a) links to b and c.
new Node(2);//says that the second node(node b) links to c.
new Node(0, 3);//says that the third node(node c) links to a and d.
new Node(0);//etc
}
static void InitializeExampleGraph2()
{
new Node(1);
new Node(0, 0, 2);
new Node(0);
}
我必须指出，这些示例中边缘的索引与您的图像中的索引不对应，但是可以通过简单的查找来避免。
结果: 第一个示例的所有循环为allCycles:{3, 2, 0}
{5, 4, 2, 0}
{3, 1}
{5, 4, 1}
allCycles是第二个示例中的变量:
{1, 0}
{2, 0}
{4, 3, 0}
我希望您对这个解决方案感到满意并使用它。我几乎没有对代码进行注释，所以我知道可能很难理解。如果是这种情况，请问我，我会加上注释的！
FindAllCyclesUnoptimized 方法中，HashSet 始终保持为空。我尝试进行了编辑，但被拒绝了。我认为只需要在 newSet 声明后添加 newSet.Add(e.B); 就可以与上面的函数匹配，但我可能错了。 - David Sherret使用广度优先搜索（Breadth-first search）查找节点A和节点B之间的所有路径 - 我们称该函数为get_all_paths
要查找所有循环，您只需要：
cycles = []
for x in nodes:
cycles += get_all_paths(x,x)
get_all_paths(x,x) 的意思是，一个环就是起点和终点相同的路径。
这只是一种替代方案 - 我希望它能给你新的想法。
编辑
另一种选择是计算所有可能的路径，并每次检查第一条边是否从最后一条边结束 - 是否为环。
这里是其Python代码。
def paths_rec(path,edges):
if len(path) > 0 and path[0][0] == path[-1][1]:
print "cycle", path
return #cut processing when find a cycle
if len(edges) == 0:
return
if len(path) == 0:
#path is empty so all edges are candidates for next step
next_edges = edges
else:
#only edges starting where the last one finishes are candidates
next_edges = filter(lambda x: path[-1][1] == x[0], edges)
for edge in next_edges:
edges_recursive = list(edges)
edges_recursive.remove(edge)
#recursive call to keep on permuting possible path combinations
paths_rec(list(path) + [edge], edges_recursive)
def all_paths(edges):
paths_rec(list(),edges)
if __name__ == "__main__":
#edges are represented as (node,node)
# so (1,2) represents 1->2 the edge from node 1 to node 2.
edges = [(1,2),(2,3),(3,4),(4,2),(2,1)]
all_paths(edges)
int[,] Adjacency = new int[6, 6] {
{ 0,1,0,1,0,0 },
{ 0,0,0,1,0,0 },
{ 0,0,0,0,1,0 },
{ 0,1,1,0,0,0 },
{ 0,1,0,0,0,1 },
{ 0,0,1,1,0,0 }};
public void Start()
{
List<List<int>> Out = new List<List<int>>();
FindAllCycles(new List<int>(), Out, 0);
Console.WriteLine("");
foreach (List<int> CurrCycle in Out)
{
string CurrString = "";
foreach (int Currint in CurrCycle) CurrString += Currint + ", ";
Console.WriteLine(CurrString);
}
}
private void FindAllCycles(List<int> CurrentCycleVisited, List<List<int>> Cycles, int CurrNode)
{
CurrentCycleVisited.Add(CurrNode);
for (int OutEdgeCnt = 0; OutEdgeCnt < Adjacency.GetLength(0); OutEdgeCnt++)
{
if (Adjacency[CurrNode, OutEdgeCnt] == 1)//CurrNode Is connected with OutEdgeCnt
{
if (CurrentCycleVisited.Contains(OutEdgeCnt))
{
int StartIndex = CurrentCycleVisited.IndexOf(OutEdgeCnt);
int EndIndex = CurrentCycleVisited.IndexOf(CurrNode);
Cycles.Add(CurrentCycleVisited.GetRange(StartIndex, EndIndex - StartIndex + 1));
}
else
{
FindAllCycles(new List<int>(CurrentCycleVisited), Cycles, OutEdgeCnt);
}
}
}
}
1-2-3-4-5-6包含了 2 个循环，并且它包含了重复的顶点 (a)，但它是一个循环，不包含重复路径（例如 5-6-5-6）。 - ulrichb