如何计算连通图的数量？

Question

给定一个节点数组和一个边数组，如何计算连接图的数量？

- abx23

---

你目前尝试了什么？给我们看看你的代码片段，并告诉我们你卡在哪里了。 - CoolBeans

Answer 1

为了详细说明quasiverse的答案，这里是一个简短的伪代码：

make_set(v) 创建一个只有v作为成员的新集合。

union(x, y) 合并两个集合x和y。新集合的代表元素从两个集合中选择一个。

get_representatve(v) 返回给定节点所属集合的代表元素。

在图G =（V，E）中查找连通分量：

foreach vertex v in V:
    make_set(v)

foreach edge (u, v) in E:
    if get_representatve(u) != get_representatve:
         union(u, v)

实现必要的函数是读者的练习；-）无论如何，对于无向图来说，它将正常工作，但如果您想要强连通分量，应该看一下Tarjan算法。

对于并行实现，据我所知，没有高效确定性算法，但有一些有趣的随机算法。

- Voo

Answer 2

• 从其中一个节点开始进行BFS或DFS，以获取从该节点连接的所有节点。
• 现在遍历节点列表以查找尚未包含在内的任何节点，
• 在节点上执行相同的过程。重复直到访问了所有节点。
• 现在您将拥有所有图形数据。

- Zimbabao

---

并查集对于大型数据集来说会比这个更快，虽然这个也能用。 - thomasfedb

请查看此链接以获取关于并查集的良好解释：http://www.algorithmist.com/index.php/Union_Find - Kshitij Banerjee

Answer 3

你可以使用并查集（可以搜索一下）。将所有节点作为单独的集合开始，然后对于每条边，将连接该边的两个节点加入同一个集合中。然后通过遍历所有节点并找到有多少不同的代表来检查有多少不同的集合。

- flight

---

+1：但是您应该指出，仅当计划动态更新图形时，使用宽/深度优先搜索才更好。对于静态图形，使用广/深度优先搜索更好。 - Aryabhatta

Answer 4

是的，有一种算法，其时间复杂度与图的大小成线性关系，为O（|V| + |E|）。

visited := the empty set
count := 0
for each vertex v in vertices:
    if v not in visited:
        count++
        add v and all nodes reachable from v to visited
return count

- rlibby

Answer 5

对于无向图，可以使用简单的DFS算法在O(n)时间内完成。具体步骤如下：

定义一个名为explore的过程，该过程查找从给定节点可以到达的所有节点。这只是一个递归的DFS过程，在每个节点处，您需要找到该节点的所有子节点并将它们推入堆栈中。

要找到答案，请从任何节点开始DFS，并在该节点上启动explore过程。保持一个整数（假设为cc），并在每次调用explore过程时将其传递给它。此外，保持一个哈希映射/字典或类似物，将cc映射到相应的节点。在explore过程的每个级别上，将当前节点映射到此时的cc。每次递归调用explore过程时，都将相同的cc值传递给它。

每次explore返回到DFS循环时，增加cc并将该值传递给下一次。完成整个DFS后，您将拥有一个将每个节点映射到其相应连接组件编号的字典。此过程结束时cc的值可以告诉您图中有多少个连接组件。

以下是伪代码：

function explore(node, graph, cc, map){
    map(currentNode) = cc
    //find all children of current node, and push onto stack. 
    //mark current node as visited
    for i in stack:
        explore(i, graph, cc, map)
}

function DFS{
     int cc = -1
     for node in keysOfGraph:
          if not visited:
              cc++
              explore(node, graph, cc, map)

return cc
}

来自Dasgupta算法（第3.2.3节）

- efficiencyIsBliss