从向量中有效提取同一类节点的算法

Question

我有一个向量（它是分类的结果），这意味着 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 class

and    `s[2]=1`  same information

s[3]=1` so all 1,2,3 are in same class))

现在我必须找到一种方法来从 s: 获取成员向量，以查看哪些节点在同一类中

mVC=[1,1,1,1,2,2,2,2,2,3,3,3,3,3]

(here 1,2,3,4 are in one class)

Answer 1

该向量S看起来像是代表父关系，尽管它可能包含循环。所以，如果你把这个向量看作是一个有向图的邻接表，并在这个数据结构上运行深度优先搜索（DFS），你会找到这个图的连通分量，每个分量都属于同一个班级，用你的术语。您也可以mVC在运行 DFS 的同时进行填充，并以您想要的格式获取数据。但是，与默认的 DFS 不同，您需要留意后边或交叉边，并在遇到这些类型的边之一时更新当前正在探索的节点的分类。下面是一个示例实现。当遇到后边或交叉边时，算法停止递归并将该边的目的地的组件（即分类信息）向上冒泡到当前正在探索的顶点。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 SmVC = [0] * len(S)currentComponent = 1for i in range(1, len(S)):    if mVC[ i ] == 0:        componentAssigned = dfs(S, i, mVC, currentComponent)        if componentAssigned == currentComponent:            currentComponent += 1mVC = mVC[1:] # Gets rid of the dummy 0th element added above# at this point, mVC contains the class relationship in the desired format

Answer 2

这是一个连接组件问题。这是一种方法：S=(2,1,1,3,6,7,5,9,6,13,12,14,12,11)构建一个元组列表，每个元组代表图中的边，并由给定值的索引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,....使用构建网络networkx并提取其connected_components. 这会将“同一类”中的节点分组在一起：import networkx as nxG=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}]