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

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 classand    `s[2]=1`  same informations[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 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

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 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}]