blocks|key|2692623|text|我怀疑它是否是最优的，但你可以做一个基于队列的搜索，假设图肯定有一个循环。每个队列条目将包含表示路径的节点列表。当您从队列中删除一个元素时，请将所有可能的后续步骤添加到队列中，确保您不会重新访问节点。如果最后一个节点与第一个节点相同，则已找到最小周期。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2692624|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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.

blocks|key|161027|text|看看这篇论文--+Directed+Chinese+Postman+Problem。然而，这是正确的问题分类(假设没有更多的限制)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|161028|如果你只是在阅读理论，可以在this+page上好好读一读，它来自算法设计手册。|161029|关键引述(后半部分为定向版本)：|161030|161031|最优邮递员环游图可以通过在图G上添加适当的边来构造，从而使其成为欧拉图。具体地说，我们找到G中每对奇数度顶点之间的最短路径。在G中的两个奇数度顶点之间添加一条路径会使这两个顶点都变为偶数度，从而使我们更接近欧拉图。找到最短路径的最佳集合以添加到G中归结为在奇数度顶点上识别图中的最小重量完美匹配，其中边(i，j)的权重是从i到j的最短路径的长度。对于有向图，这可以使用二部匹配来解决，其中顶点的划分取决于它们有更多的入边或出边。一旦图是欧拉的，就可以使用上面描述的过程在线性时间内提取实际的循环。|blockquote|161032|161033|entityMap|0|LINK|mutability|MUTABLE|url|http://docs.google.com/viewer?a=v&q=cache:sgqn_TYOGyYJ:citeseerx.ist.psu.edu/viewdoc/download%253Fdoi%253D10.1.1.106.4691%2526rep%253Drep1%2526type%253Dpdf%2Bchinese%2Bpostman%2Bdirected%2Bgraph&hl=en&gl=us&pid=bl&srcid=ADGEESj_3IHoWio-Mxt0T4znoW4uZgA0GyS3AJuX7QbvHOgA_FvmS_r7VxfKSEs5YlgHGu9gwbIz1WNoO5_UIC7BUVdE4cgkdkYKyJi6zk_2feEkey99VkhIIP0o9SGfxIm5xSBFI7HZ&sig=AHIEtbSiYnn7aLuzLPN84fvf-pJLaQIMuw|1|http://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE165.HTM^0|9|W|0|0|E|9|1|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|D|3|E|5|6|7|10|8|@]|9|@$A|11|B|12|1|13]]|C|$]]|$1|F|3|G|5|6|7|14|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|15|8|@]|9|@]|C|$]]|$1|I|3|J|5|K|7|16|8|@]|9|@]|C|$]]|$1|L|3|-4|5|6|7|17|8|@]|9|@]|C|$]]|$1|M|3|-4|5|6|7|18|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]|U|$5|P|Q|R|C|$S|V]]]]

Take a look at this paper - <a href="http://docs.google.com/viewer?a=v&amp;q=cache:sgqn_TYOGyYJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.106.4691%26rep%3Drep1%26type%3Dpdf+chinese+postman+directed+graph&amp;hl=en&amp;gl=us&amp;pid=bl&amp;srcid=ADGEESj_3IHoWio-Mxt0T4znoW4uZgA0GyS3AJuX7QbvHOgA_FvmS_r7VxfKSEs5YlgHGu9gwbIz1WNoO5_UIC7BUVdE4cgkdkYKyJi6zk_2feEkey99VkhIIP0o9SGfxIm5xSBFI7HZ&amp;sig=AHIEtbSiYnn7aLuzLPN84fvf-pJLaQIMuw" rel="nofollow noreferrer">Directed Chinese Postman Problem</a>. 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 <a href="http://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE165.HTM" rel="nofollow noreferrer">this page</a>, which is from the Algorithms Design Manual.

Key quote (the second half for the directed version):

<blockquote>
 The optimal postman tour can be constructed by adding the appropriate edges to the graph G so as to make it Eulerian. Specifically, we find the shortest path between each pair of odd-degree vertices in G. Adding a path between two odd-degree vertices in G turns both of them to even-degree, thus moving us closer to an Eulerian graph. Finding the best set of shortest paths to add to G reduces to identifying a minimum-weight perfect matching in a graph on the odd-degree vertices, where the weight of edge (i,j) is the length of the shortest path from i to j. For directed graphs, this can be solved using bipartite matching, where the vertices are partitioned depending on whether they have more ingoing or outgoing edges. Once the graph is Eulerian, the actual cycle can be extracted in linear time using the procedure described above.
</blockquote>

blocks|key|1283678|text|你要找的东西叫做“欧拉路径”。你可以谷歌它来找到足够的信息，基础是here和关于算法，有一种算法称为弗勒里的算法，谷歌为它或看看here|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1283679|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Eulerian_path|1|http://www.austincc.edu/powens/%2BTopics/HTML/05-6/05-6.html^0|X|4|0|1S|4|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

what you are looking for is called "Eulerian path". You can google it to find enough info, basics are <a href="http://en.wikipedia.org/wiki/Eulerian_path" rel="nofollow noreferrer">here</a>
And about algorithm, there is an algorithm called Fleury's algorithm, google for it or take a look <a href="http://www.austincc.edu/powens/+Topics/HTML/05-6/05-6.html" rel="nofollow noreferrer">here</a>

blocks|key|160143|text|网络完全由有向边组成的特殊情况可以在多项式时间内求解。我认为最初的论文是Matching,+Euler+tours+and+the+Chinese+postman+(1973)的--关于有向图问题的算法的清晰描述开始于第115页(pdf的第28页)：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|160144|160145|当连通图的所有边都是有向的，并且图是对称的时，有一个特别简单和有吸引力的算法来指定欧拉环游...|blockquote|160146|160147|在有向对称连通图G中寻找Euler环游的算法是首先找到G的一个生成树，然后在任何节点n处，除了树形的根r之外，为指向远离n的边指定任何顺序，只要树形的边在排序中最后。对于根r，可以为远离r的边指定任何顺序。|160148|van+Aardenne-Ehrenfest和de+Bruin使用该算法来枚举某个有向图1中的所有欧拉旅行。|160149|entityMap|0|LINK|mutability|MUTABLE|url|http://www.springerlink.com/content/m13073156441m47x/^0|10|1G|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|-4|5|6|7|Y|8|@]|9|@]|C|$]]|$1|E|3|F|5|G|7|Z|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]|$1|I|3|J|5|6|7|11|8|@]|9|@]|C|$]]|$1|K|3|L|5|6|7|12|8|@]|9|@]|C|$]]|$1|M|3|-4|5|6|7|13|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]]]

The special case in which the network consists entirely of directed edges can be solved in polynomial time. I think the original paper is <a href="http://www.springerlink.com/content/m13073156441m47x/" rel="nofollow noreferrer">Matching, Euler tours and the Chinese postman (1973)</a> - a clear description of the algorithm for the directed graph problem begins on page 115 (page 28 of the pdf):

<blockquote>
 When all of the edges of a connected graph are directed and the graph
 is symmetric, there is a particularly simple and attractive algorithm for
 specifying an Euler tour...
 
 The algorithm to find an Euler tour in a directed, symmetric, connected graph G is to first find a spanning arborescence of G. Then, at
 any node n, except the root r of the arborescence, specify any order for
 the edges directed away from n so long as the edge of the arborescence
 is last in the ordering. For the root r, specify any order at all for the
 edges directed away from r.
 
 This algorithm was used by van Aardenne-Ehrenfest and de Bruin to
 enumerate all Euler tours in a certain directed graph [ 1 ].
</blockquote>

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

Minimal path - all edges at least once

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有很多圈的有向图，可能是强连通的，我需要从它得到一个最小的圈。我的意思是我需要得到循环，这是图中最短的循环，每条边至少被覆盖一次。我一直在寻找一些算法或一些理论背景，但我唯一找到的是中国邮递员算法。但这种解决方案不适用于有向图。有人能帮我吗？谢谢Edit>>该图的所有边都具有相同的成本-例如1

问最小路径-所有边至少一次
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问最小路径-所有边至少一次EN