遍历自环的有向多重图中的所有循环

在Golang实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《遍历自环的有向多重图中的所有循环》，聊聊，希望可以帮助到正在努力赚钱的你。

Golang 中是否有找到具有自边的有向多重图中的所有循环的算法实现？我发现约翰逊算法是有向图的最佳解决方案，并且在 gonum 中给出了实现，但它仅适用于有向图（不适用于多重图）并且不支持自边（实际上 gonum 中的有向图不支持自边）边缘）。我可以在 gonum 中做一些简短/聪明的黑客来使约翰逊的工作用于具有自边的有向多重图吗？或者 Golang 中还有其他实现吗？

可以做的一件事是在自边和同一对节点之间的重复边之间创建一个虚拟节点。这将删除所有自边，并且图形将是有向的，我可以在此处使用约翰逊。但还有更好的办法吗？

解决方案

• 自边：您只需扫描图的每个节点并检查是否存在自边。如果有：将 x -> x 添加到循环列表

• 多图：第一个算法将生成路径作为顶点序列 x1 -> x2 -> x3 -> ...。当您拥有此列表时，迭代从 x1 到 x2 的所有可能的边，然后迭代从 x2 到 x3 的所有可能的边，依此类推...

• “聪明”黑客：从多重图 g 中，创建一个新图 g2，其中 g 的边也显示为顶点：

# if A and B are connected     # create the following 3 vertices and
# by a single edge in G :      # 2 edges in G2 :

   A ---w--> B                     A -> w -> B


# if A and B are connected     # create the following 4 vertices and
# by two edges in G :          # 4 edges in G2 :

     /--x--\                           /-> x --\
    A       B                        A          B
     \--y--/                           \-> y --/

# etc ...

然后在 g2 上运行循环枚举，并根据需要调整输出。

理论要掌握，实操不能落！以上关于《遍历自环的有向多重图中的所有循环》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！