TA貢獻(xiàn)1777條經(jīng)驗(yàn) 獲得超10個(gè)贊
如果您可以使用庫(kù)，假設(shè)您的數(shù)組是a（請(qǐng)注意，您不能將組件作為 numpy 數(shù)組，因?yàn)樗鼈兛梢允?numpy 中不存在的非矩形數(shù)組，因此這會(huì)將它們作為集合輸出）：
import networkx as nx
G=nx.Graph()
G.add_edges_from(a)
print(sorted(nx.connected_components(G), key = len, reverse=True))
#[{0, 4, 5, 6, 7}, {1, 2, 13, 9}, {16, 3, 14}]
TA貢獻(xiàn)1852條經(jīng)驗(yàn) 獲得超1個(gè)贊
就圖論而言，您需要從邊數(shù)組創(chuàng)建一個(gè)圖，然后找到該圖的連通分量。純粹的基于解決方案對(duì)我來(lái)說(shuō)似乎太難了，但你仍然可以使用用 C 編寫的（與純 Python 不同）numpy使其成為 C 級(jí)別。您需要先安裝。igraphnetworkxpython-igraph
小事例
igraph.Graph.clusters()方法返回一個(gè)特殊的igraph.clustering.VertexClustering類實(shí)例，可以轉(zhuǎn)換為list：
import igraph
arr = np.array([[0, 4], [0, 7], [1, 2], [1, 9], [2, 1], [2, 8], [3, 10],
[3, 11], [4, 0], [4, 5], [5, 4], [5, 6], [6, 5], [6, 7], [7, 0], [7, 6]])
g = ig.Graph()
g.add_vertices(12)
g.add_edges(arr)
i = g.clusters()
print(list(i))
#output: [[0, 4, 5, 6, 7], [1, 2, 8, 9], [3, 10, 11]]
igraph還支持像在中完成的那樣繪制這些連接的組件networkx，但您可能需要pycairo從非官方二進(jìn)制文件下載并安裝它才能解鎖igraph.plot選項(xiàng)：
pal = ig.drawing.colors.ClusterColoringPalette(len(i)) #passing a number of colors
color = pal.get_many(i.membership) # a list of color codes for each vertex
ig.plot(g, bbox = (200, 100), vertex_label=g.vs.indices,
vertex_color = color, vertex_size = 12, vertex_label_size = 8)
一般情況
請(qǐng)注意，如果使用初始數(shù)組而不是簡(jiǎn)單的數(shù)組，igraph則會(huì)拋出一個(gè)異常。InternalError這是因?yàn)槊總€(gè)頂點(diǎn)都應(yīng)該在添加邊之前聲明，并且所有頂點(diǎn)都不允許有缺失的數(shù)字（事實(shí)上，這是允許的，但重新索引是靜默完成的，并且可以使用“name”屬性訪問(wèn)舊名稱）。這個(gè)問(wèn)題可以通過(guò)編寫一個(gè)自定義函數(shù)來(lái)解決，該函數(shù)從重新標(biāo)記的邊創(chuàng)建圖形：
def create_from_edges(edgelist):
g = ig.Graph()
u, inv = np.unique(edgelist, return_inverse=True)
e = inv.reshape(edgelist.shape)
g.add_vertices(u) #add vertices, not reindexed
g.add_edges(e) #add edges, reindexed
return g
arr = np.array([[0, 4], [0, 7], [1, 2], [1, 13], [2, 1], [2, 9], [3, 14],
[3, 16], [4, 0], [4, 5], [5, 4], [5, 6], [6, 5], [6, 7], [7, 0], [7, 6]])
g = create_from_edges(arr)
i = g.clusters()
print(list(i))
#output: [[0, 4, 5, 6, 7], [1, 2, 8, 9], [3, 10, 11]]
輸出中使用了新標(biāo)簽（從而使其不正確），但仍然可以訪問(wèn)舊標(biāo)簽，如下所示：
print('new_names:', g.vs.indices)
print('old_names:', g.vs['name'])
>>> new_names: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> old_names: [0, 1, 2, 3, 4, 5, 6, 7, 9, 13, 14, 16]
它們可用于預(yù)覽原始圖表（vertex_label現(xiàn)在不同）：
pal = ig.drawing.colors.ClusterColoringPalette(len(i)) #passing a number of colors
color = pal.get_many(i.membership) ##a list of color codes for each vertex
ig.plot(g, bbox = (200, 100), vertex_label=g.vs['name'],
vertex_color = color, vertex_size = 12, vertex_label_size = 8)
最后，您需要使用舊的頂點(diǎn)名稱來(lái)修復(fù)輸出?？梢赃@樣做：
output = list(i)
old_names = np.array(g.vs['name'])
fixed_output = [old_names[n].tolist() for n in output]
#new output: [[0, 4, 5, 6, 7], [1, 2, 9, 13], [3, 14, 16]]
TA貢獻(xiàn)1735條經(jīng)驗(yàn) 獲得超5個(gè)贊
我確信有更快的方法，而且我不研究圖論，但你可以從這個(gè)開(kāi)始；
x = [[ 0, 4],
[ 0, 7],
[ 1, 2],
[ 1, 13],
[ 2, 1],
[ 2, 9],
[ 3, 14],
[ 3, 16],
[ 4, 0],
[ 4, 5],
[ 5, 4],
[ 5, 6],
[ 6, 5],
[ 6, 7],
[ 7, 0],
[ 7, 6]]
nodes = list(set([item for sublist in x for item in sublist]))
grps = {n: g for n, g in zip(nodes, range(len(nodes)))}
for v in x:
t = grps[v[0]]
f = grps[v[1]]
if t != f:
for n in grps:
if grps[n] == f:
grps[n] = t
ret = [[k for k, v in grps.items() if v==g] for g in set(grps.values())]
print(ret)
舉報(bào)