查找图中树数的算法是什么？

Question

给定一个节点列表，例如，

[1,2,3,4,5,6,7,8,9],

和一个元组列表，用于指示连接两个节点的无向边，例如，

[(2,3), (2,7), (3,7), (4,3), (5,1), (5,6)],

如何找到不相交树的数量？

树是一组由至少一条边连接的音符，或者是不与任何其他节点连接的孤立节点。

在我的示例中，有 3 棵树是：

{2,3,4,7}
{1,5,6}
{9}

我认为这是一个普通的算法问题，所以这个问题很可能是重复的。但是我只是无法在线找到解决方案。可能是我搜索的词不对

Answer 1

感谢@beaker 和@derpirscher。我在下面发布了一些链接并关闭了这个问题。

https://en.wikipedia.org/wiki/Component_(graph_theory)

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/discuss/516491/Java-Union-Find-DFS-BFS-Solutions-Complexity-Explain-Clean-code

Answer 2

根据您的描述，不相交的树不一定是树。他们可以有周期。他们一般被称为components.

解决这个问题的方法之一是使用 Disjoint Set 的概念。

您的语言环境可能在本地或库中有不相交集的实现，但这里是 Python 中不相交集的实现：

# Implementation of Union-Find (Disjoint Set)
class Node:
    def __init__(self):
        self.parent = self
        self.rank = 0

    def find(self):
        if self.parent.parent != self.parent:
            self.parent = self.parent.find()
        return self.parent

    def union(self, other):
        node = self.find()
        other = other.find()
        if node == other:
            return True # was already in same set
        if node.rank > other.rank:
            node, other = other, node
        node.parent = other
        other.rank = max(other.rank, node.rank + 1)
        return False # was not in same set, but now is

所以以上是通用的，与您的图形问题没有具体关系。现在要将它用于您的图形，我们为每个图形节点创建一个 Node 实例，并调用 union 以指示连接的节点属于同一图形组件：

def count_components(nodeids, edges):
    # Create dictionary of nodes, keyed by their IDs
    nodes = {
        nodeid: Node() for nodeid in nodeids
    }
    # All connected nodes belong to the same disjoined set:
    for a, b in edges:
        nodes[a].union(nodes[b])
    # Count distinct roots to which each node links
    return len(set(node.find() for node in nodes.values()))

我们可以运行为您的示例图如下：

vertices = [1,2,3,4,5,6,7,8,9]
edges = [(2,3), (2,7), (3,7), (4,3), (5,1), (5,6)]
print(count_components(vertices, edges))  # 4

由于这些已识别的不相交集，因此打印 4：

{2,3,4,7}
{1,5,6}
{8}
{9}

查找图中树数的算法是什么？

What is the algorithm to find the number of trees in a graph?

algorithm

graph-algorithm