将图形分割为完全子图的算法

Question

我需要一个算法来划分一个无向图的顶点到一个或多个子图，这样每个子图是一个完整的图（每个顶点相邻的其他每个顶点）。每个顶点必须正好位于其中一个子图中。你知道吗

举个例子：

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：它只适用于有向图。

Answer 1

另一次尝试：

lst = [
    ('A', 'B'),
    ('B', 'C'),
    ('A', 'C'),
    ('B', 'D'),
    ('D', 'E'),
]

d = {}
for i, j in lst:
    d.setdefault(i, []).append(j)
    d.setdefault(j, []).append(i)

from itertools import combinations

rv, seen_segments, seen_vertices = [], set(), set()
for k, v in d.items():
    if len(v) == 1:
        segment = set((k, v[0])).difference(seen_vertices)
        seen_vertices.update(segment)
        rv.append([tuple(segment), ])
    else:
        graph = []
        for i, j in combinations([k] + v, 2):
            if not j in d[i]:
                break
            else:
                graph.append(tuple(sorted((i, j))))
        else:
            if graph:
                graph = [segment for segment in graph if segment not in seen_segments]
                seen_segments.update(graph)
                if graph:
                    rv.append(graph)

from pprint import pprint
pprint(rv)

印刷品：

[[('A', 'B'), ('A', 'C'), ('B', 'C')], [('D', 'E')]]

---

用于输入

lst = [
    ('A', 'B'),
    ('B', 'C'),
]

印刷品：

[[('A', 'B')], [('C',)]]

---

输入：

lst = [
    ('A', 'B'),
    ('B', 'C'),
    ('C', 'D'),
]

印刷品：

[[('B', 'A')], [('D', 'C')]]