Given a list of nodes, e.g.,

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

and a list of tuples to indicate the non-directional edges connecting two nodes, e.g.,

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

How can I find the number of disjoint trees?

A tree is a group of notes connected by at least one edge, or an isolated node not connected to any other node.

In my example, there are 3 trees which are:

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

I think this is a garden-variety algorithm problem so this question is very likely a duplicate. However I just couldn't find a solution online. Perhaps I am not using the right term to search.

CodePudding user response：

Credits to @beaker and @derpirscher. I posted some links below and closing this question.

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

CodePudding user response：

According to your description, the disjoint trees are not necessarily trees. They could have cycles. They are generally called components.

One of the ways to solve this is to use the concept of Disjoint Set.

Your language environment may have an implementation of disjoint sets natively or as a library, but here is an implementation of Disjoint Set in 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

So the above is generic, not specifically related to your graph problem. Now to use it for your graph, we create a Node instance for each graph node, and call union to indicate that connected nodes belong to the same graph-component:

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()))

We can run it for your example graph as follows:

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

This prints 4 because of these identified disjoint sets:

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