时间戳

首页 > 解决方案 > 在具有自边的有向多重图中查找所有循环

go - 在具有自边的有向多重图中查找所有循环

问题描述

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

可以做的一件事是在自身边和同一对节点之间的重复边之间创建一个虚拟节点。这将删除所有自我边缘，并且图形将是有向的，我可以在这里使用 Johnson's。但是有没有更好的方法？

标签： gographcycle

解决方案

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

  • 多图：第一个算法将生成路径作为顶点序列X1 -> X2 -> X3 -> ...。当你有这个列表时，迭代所有可能的边缘从X1to X2，然后所有可能的边缘从X2toX3等等......

  • “聪明” hack：从您的多重图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，并根据需要调整输出。

推荐阅读