我有一個向量（它是分類的結(jié)果），這意味著 i 和 s[i] 屬于同一類例如：S=(2,1,1,3,6,7,5,9,6,13,12,14,12,11)(( `s[1]=2 `so node 1 and 2 are in same classand `s[2]=1` same informations[3]=1` so all 1,2,3 are in same class))現(xiàn)在我必須找到一種方法來從 s: 獲取成員向量，以查看哪些節(jié)點(diǎn)在同一類中mVC=[1,1,1,1,2,2,2,2,2,3,3,3,3,3](here 1,2,3,4 are in one class)
2 回答
偶然的你
TA貢獻(xiàn)1841條經(jīng)驗(yàn) 獲得超3個贊
該向量S看起來像是代表父關(guān)系，盡管它可能包含循環(huán)。所以，如果你把這個向量看作是一個有向圖的鄰接表，并在這個數(shù)據(jù)結(jié)構(gòu)上運(yùn)行深度優(yōu)先搜索（DFS），你會找到這個圖的連通分量，每個分量都屬于同一個班級，用你的術(shù)語。您也可以mVC在運(yùn)行 DFS 的同時進(jìn)行填充，并以您想要的格式獲取數(shù)據(jù)。
但是，與默認(rèn)的 DFS 不同，您需要留意后邊或交叉邊，并在遇到這些類型的邊之一時更新當(dāng)前正在探索的節(jié)點(diǎn)的分類。
下面是一個示例實(shí)現(xiàn)。當(dāng)遇到后邊或交叉邊時，算法停止遞歸并將該邊的目的地的組件（即分類信息）向上冒泡到當(dāng)前正在探索的頂點(diǎn)。
def dfs(S, u, mVC, currentComponent):
mVC[u] = currentComponent
if mVC[ S[u] ] == 0:
mVC[u] = dfs(S, S[u], mVC, currentComponent)
else:
mVC[u] = mVC[S[u]]
return mVC[u]
S = [0] + list(S) # to handle the 1-indexing of the content in S
mVC = [0] * len(S)
currentComponent = 1
for i in range(1, len(S)):
if mVC[ i ] == 0:
componentAssigned = dfs(S, i, mVC, currentComponent)
if componentAssigned == currentComponent:
currentComponent += 1
mVC = mVC[1:] # Gets rid of the dummy 0th element added above
# at this point, mVC contains the class relationship in the desired format
開滿天機(jī)
TA貢獻(xiàn)1786條經(jīng)驗(yàn) 獲得超13個贊
這是一個連接組件問題。這是一種方法：
S=(2,1,1,3,6,7,5,9,6,13,12,14,12,11)
構(gòu)建一個元組列表，每個元組代表圖中的邊，并由給定值的索引S和值本身組成：
edges = [(ix+1, i) for ix, i in enumerate(S)]
# [(1, 2), (2, 1), (3, 1), (4, 3), (5, 6), (6, 7), (7, 5), (8,....
使用構(gòu)建網(wǎng)絡(luò)networkx并提取其connected_components. 這會將“同一類”中的節(jié)點(diǎn)分組在一起：
import networkx as nx
G=nx.Graph()
G.add_edges_from(edges)
list(nx.connected_components(G))
輸出
[{1, 2, 3, 4}, {5, 6, 7, 8, 9}, {10, 11, 12, 13, 14}]
添加回答
舉報
0/150
提交
取消