我需要一个算法来划分一个无向图的顶点到一个或多个子图,这样每个子图是一个完整的图(每个顶点相邻的其他每个顶点)。每个顶点必须正好位于其中一个子图中。你知道吗
举个例子:
input = [
(A, B),
(B, C),
(A, C),
(B, D),
(D, E),
]
output = myalgo(input) # [(A, B, C), (D, E)]
下面的图片可以更好地描述问题:
输入列表按距离按降序排序,这就是为什么我连接A-B-C而不是B-D
我认为这可能被称为“强连接组件”,并且已经尝试了以下解决方案:
Finding a Strongly Connected Components in unDirected Graphs:它在寻找不同的东西
Finding all cycles in undirected graphs:它给了我许多周期,但不是最好的,它不关心输入顺序。
An algorithm to create clusters from data pairs in python:它连接所有组件,仅仅因为它们之间有一条路径(a-B-C-D-E)。
Kosaraju's algorithm:它只适用于有向图。
另一次尝试:
印刷品:
用于输入
印刷品:
输入:
印刷品:
警告:这取决于dict在python3.7+中保持插入顺序的事实。在旧版本中,必须使用
matrix = DefaultOrderedDict(dict)
https://stackoverflow.com/a/35968897/9392216:下面是一个类,它实现了对完整子图的分段。它绝不是优化的,可能会得到显著的改进,但这是一个起点
。。。下面是一个有效的例子:
相关问题 更多 >
编程相关推荐