我正在研究图表中的问题并试图找出寻找独特路径的方法
让我举个例子，让我们考虑一个包含4个节点和6个带边的边的图，如下所示 -
1 2
2 3
3 4
4 1
1 3
2 4
长度为5的独特循环路径将是 -
-
1 - > 2 - > 3 - > 4 - > 1
-
1 - > 3 - > 2 - > 4 - > 1
-
1 - > 2 - > 4 - > 3 - > 1
如果路径的边缘组相等，则认为两条路径相等 . 考虑两条路径1 - > 2 - > 3 - > 4 - > 1和1 - > 3 - > 2 - > 4 - > 1第一条路径只是set = [（1,2），（2,3） ），（3,4），（4,1）]，而第二个是= [（1,3），（3,2），（2,4），（4,1）]
显然，这两组是不同的，因此路径也是如此 . 边缘的排序是无关紧要的，因为您只是比较任何两个集合（路径）之间的公共边缘的存在 .
一旦我得到循环路径，我如何检查路径中的路径是否具有相同的节点集？即，1 - > 2 - > 3 - > 4 - > 1和1 - > 4 - > 3 - > 2 - > 1具有相同的组，即，
[（1,2），（2,3），（3,4），（4,1）]以不同的顺序排列 .
我想到实现一对套的 Map 和检查重复..仍在寻找更好的选择 . 如何进行任何帮助表示赞赏？
1 回答
你考虑过使用Python Patterns - Implementing Graphs吗？它是一个很好的资源 . 我用它来解决从顶点x到y的图中唯一路径上的编程竞赛问题 . enter link description here