JBS*_*rro 13
我很开心这个问题,谢谢!: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}
我希望您对此解决方案感到满意并使用它.我几乎没有对代码发表评论,所以我知道它可能很难理解.在这种情况下,请询问,我会对此发表评论!
怎么样使用广度优先搜索来查找节点 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)
| 归档时间： |
|
| 查看次数： |
4671 次 |
| 最近记录： |