在Go语言中查找有向图G中的所有循环。

huangapple go评论110阅读模式
英文:

Find all cycles in a directed Graph Golang

问题

我正在尝试使用Golang生成包含在有向图中的所有循环(或至少一些循环)。
我目前有两个结构体:

Node:{ ID(字符串),resolved(布尔值),edges([]Edge)}
Edge:{ ID(字符串),start(Node),end(Node),weight(Float64)}

目前循环的权重不是问题(暂时不考虑)。
我找到了一些关于如何检测循环或找到最短路径等的答案,但是没有找到一个能够帮助我的算法。
我应该如何继续?(欢迎任何建议)

英文:

I'm trying to generate all the cycles contained in a directed graph using Golang (or at least a few).
I currently have two structs :

Node : { ID (string), resolved (bool), edges ([]Edge) }  
Edge : { ID (string), start (Node), end (Node), weight (Float64)}  

The cycle weight is not an issue (for the moment).
I've found some answers regarding how to detect cycles, or find shortest path etc. but i didn't find an algorithm that can quite help me.
How shall I proceed? (any suggestion is welcome)

答案1

得分: 2

有两个部分的问题。

关于检测图中所有循环的算法,请参考这个相关问题(因为这不是特定于Go的),其中有有用的解释和伪代码,您可以用来实现您的解决方案。

https://stackoverflow.com/questions/546655/finding-all-cycles-in-a-directed-graph

至于特定的Go代码,有几个库可以处理图形,您可以查看它们的文档和源代码(它们甚至可能提供可以直接使用的功能来解决您的问题)。

例如:https://godoc.org/github.com/twmb/algoimpl/go/graph

英文:

There are two parts to the question.

Regarding algorithms to detect all cycles in a graph, take a look at this related question (since this is not go-specific), there are useful explanations and pseudo-code that you can use to implement your solution.

https://stackoverflow.com/questions/546655/finding-all-cycles-in-a-directed-graph

As per specific go code, there are several libraries out there that work with graphs, you can take a look at their documentation and source code (they might even provide functionality that you can use out-of-the-box to solve your problem).

For example: https://godoc.org/github.com/twmb/algoimpl/go/graph

答案2

得分: 1

我建议从定义“循环”开始,例如假设它是从一个节点开始并以相同节点结束的图遍历。

要枚举所有符合这个定义的循环,你需要考虑从所有节点开始的所有路径,并检查这些路径是否回到了起始点。

然而,需要注意的是,这个定义实际上可以多次计算每个循环子图 - 沿着循环路径的任何节点 - 是一个循环还是多个循环?如果多个循环的路径相交,情况会变得更加复杂,循环路径的数量会急剧增加,很难确定哪些循环是“相同的”。

我希望你能明白,除非是非常小且简单的图,否则暴力方法是不可行的。对于你的目的来说,关注最小循环或仅仅识别循环子图就足够了。

正如 @eugenioy 已经提到的,这个问题之前已经有人问过,并且你可以通过查看那个线程中的答案来缩小你的问题范围。

因此,根据你对“所有”和“循环”的理解,你可能可以找到一个算法,以与你感兴趣的方式定义循环,并且如果你在将其转换为 Go 时遇到困难,可以提出一个更具针对性的问题,而我认为你目前的问题并不是关于 Go 的。

英文:

I would suggest starting with defining what a cycle is - for example let's suppose it is a traversal through the graph that starts and ends in the same node.

To enumerate all cycles with this definition, you'll need to consider all paths starting from all nodes, and check if any of those paths go back to their start point.

However, observe that this definition can actually count each cyclical subgraph many times - any node along a cyclical path - is that one cycle or several? And things get even more complicated if the paths of several cycles intersect, the number of cyclical paths increases drastically, and it's not very clear which cycles are "the same".

I hope it's easy to see that a brute force approach is intractable for anything but very small and simple graphs, and that something concerned with say minimal cycles or even just identifying cyclic subgraphs is enough for your purposes.

As already mentioned by @eugenioy, this has been asked before and you can probably narrow down your question by looking at the answers in that thread.

So, depending on what you mean by "all" and what you mean by "cycles", you can probably find an algorithm that defines cycles in the same way that you are interested in, and, and ask a more focused question if you're having trouble translating it to Go, which I don't think your question is really about at the moment.

huangapple
  • 本文由 发表于 2017年5月15日 22:29:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/43982089.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定