我有很多循环的有向图，可能是强连接的，我需要从中得到一个最小的循环。我的意思是我需要得到周期，这是图中最短的周期，并且每条边至少被覆盖一次。
我一直在寻找一些算法或一些理论背景，但我唯一找到的是中国邮递员算法。但这个解决方案不适用于有向图。
有人可以帮助我吗？谢谢
编辑>>该图的所有边都具有相同的成本 - 例如 1
I have directed graph with lot of cycles, probably strongly connected, and I need to get a minimal cycle from it. I mean I need to get cycle, which is the shortest cycle in graph, and every edge is covered at least once.
I have been searching for some algorithm or some theoretical background, but only thing I have found is Chinese postman algorithm. But this solution is not for directed graph.
Can anybody help me? Thanks
Edit>> All edges of that graph have the same cost - for instance 1
发布评论
评论（5）
看看这篇论文 - 定向中国邮递员问题。但这是正确的问题分类（假设没有更多限制）。
如果您只是阅读理论，请仔细阅读 此页面，来自算法设计手册。
关键引述（指导版本的后半部分）：
Take a look at this paper - Directed Chinese Postman Problem. That is the correct problem classification though (assuming there are no more restrictions).
If you're just reading into theory, take a good read at this page, which is from the Algorithms Design Manual.
Key quote (the second half for the directed version):
我怀疑它是否是最佳的，但是假设图形保证有一个循环，您可以进行基于队列的搜索。每个队列条目将包含代表路径的节点列表。当您从队列中取出一个元素时，将所有可能的后续步骤添加到队列中，确保您不会重新访问节点。如果最后一个节点与第一个节点相同，则您已找到最小循环。
I doubt that it's optimal, but you could do a queue based search assuming the graph is guaranteed to have a cycle. Each queue entry would contain a list of nodes representing paths. When you take an element off the queue, add all possible next steps to the queue, ensuring you are not re-visiting nodes. If the last node is the same as the first node, you've found the minimum cycle.
您正在寻找的称为“欧拉路径”。您可以通过 Google 搜索找到足够的信息，基本信息位于此处
关于算法，有一种算法叫做Fleury算法，google一下或者看看这里
what you are looking for is called "Eulerian path". You can google it to find enough info, basics are here
And about algorithm, there is an algorithm called Fleury's algorithm, google for it or take a look here
我认为可能值得简单地写出哪些顶点是奇数，然后找到它们的哪个组合将导致最少的额外时间（如果权重是时间或距离），那么总长度将是每个边权重加上额外的。例如，如果奇数阶顶点是 A、B、C、D，请尝试 AB 和 CD，然后是 AC 和 BD，依此类推。 （我不确定这是否是一个专门命名的方法，它对我有用）。
编辑：刚刚意识到这主要只适用于无向图。
I think it might be worth while just simply writing which vertices are odd and then find which combo of them will lead to the least amount of extra time (if the weights are for times or distances) then the total length will be every edge weight plus the extra. For example, if the odd order vertices are A,B,C,D try AB&CD then AC&BD and so on. (I'm not sure if this is a specifically named method, it just worked for me).
edit: just realised this mostly only works for undirected graphs.
网络完全由有向边组成的特殊情况可以在多项式时间内解决。我认为原始论文是 Matching, Euler Tours and the Chinese postman (1973) - a有向图问题算法的清晰描述从第 115 页开始（pdf 第 28 页）：
The special case in which the network consists entirely of directed edges can be solved in polynomial time. I think the original paper is Matching, Euler tours and the Chinese postman (1973) - a clear description of the algorithm for the directed graph problem begins on page 115 (page 28 of the pdf):