algorithm - 如何找到连通子图？

Question

我有一个网络，但这个网络没有连接。我想知道如何在这个网络中找到最大的连通图？

Answer 1

要计算节点所属的连通分量，只需运行任何类型的图搜索算法，例如广度优先搜索。

要解决您的问题，请遍历网络中的所有节点并执行以下操作：

1. 如果给定节点已添加到组件中，则转到下一个节点（继续迭代）
2. 如果该节点尚未添加到组件中，则运行任何图形搜索（例如上面建议的 BFS）并将所有访问过的节点标记为属于同一组件。
3. 选择上面步骤 2 中构造的最大尺寸的组件。

Answer 2

另一种简单的方法是使用union-find：

S = array filled with 1s (|V| elements)

for each edge (u,v) in E:
    if find_set(u) != find_set(v):
        sum = S[find_set(u)] + S[find_set(v)]
        S[find_set(v)] = sum
        S[find_set(u)] = sum
        union_set(u, v)

最后，S[find_set(u)] 将是节点 u 所属的连通分量的大小。要找到最大值，您只需要 find max(S)。

由于 find_set 和 union_set 都易于实现（每行 2 行 C++），我发现这种方法比 DFS 或 BFS 更干净。

Answer 3

设图为 a[n][n]，如果 i,j 连接，则 a[i][j]=1。

您可以执行以下操作。

count=0;/global


void dfs(int i)
{

int k;
for(k=0;k<n;k++)
    if(A[i][k]==1 && !visited[k])
    {
        count++;
        visited[k]=1;
        dfs(k);
    }
}
for(i=0; i < n;i++)
    {
        if(!visited[i])
        {
            count=1;
            visited[i]=1;
            dfs(i);
                            // map i with count .. here

        }
    }

因此，一旦您完成了网络中的节点数与其节点之一的映射。

您现在需要做的就是在您的地图中找到最大计数的节点。

所以你会得到 key ，它是一个带有 count map(i) 的大网络节点。

使所有节点访问到 0 并再次应用 dfs(i) 你可以得到整个网络连接

反正我和你都有数。