<pre><code>from collections import defaultdict
def create_adjacency_matrix(connections):
matrix = defaultdict(dict)
for a, b in connections:
matrix[a][b] = 1
matrix[b][a] = 1
return matrix
def is_connected_to_all(vertex, group, matrix):
for v in group:
if vertex != v and vertex not in matrix[v]:
return False
return True
def group_vertexes(input):
matrix = create_adjacency_matrix(input)
groups = []
current_group = set()
for vertex in matrix.keys():
if is_connected_to_all(vertex, current_group, matrix):
current_group.add(vertex)
else:
groups.append(current_group)
current_group = {vertex}
groups.append(current_group)
return groups
</code></pre>
<pre><code>input = [("A", "B"), ("B", "C"), ("A", "C"), ("B", "E"), ("E", "D")]
print(group_vertexes(input))
# [{'C', 'B', 'A'}, {'D', 'E'}]
</code></pre>
<p>警告:这取决于dict在python3.7+中保持插入顺序的事实。在旧版本中,必须使用<code>matrix = DefaultOrderedDict(dict)</code><a href="https://stackoverflow.com/a/35968897/9392216">https://stackoverflow.com/a/35968897/9392216</a>:</p>