将节点聚类到森林中不同树中的算法

Question

n-tree 的森林就在那里。

用户会给我们边数。

示例:- 1 2、3 4，表示 1 和 2、3 和 4 相连

任务是找出哪个节点是哪棵树的一部分？

我的方法:-

1. 建立一个数组，数组的索引代表节点。 array[i] = j，这里表示i的根是j。

这是基本方法。通过我们可以很容易地知道哪个节点是哪棵树的一部分。

时间复杂度 O(N^2)

但我需要高效的算法，请帮助我。

Answer 1

听起来你在寻找 a disjoint-set data structure / the union-find algorithm :

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union–find algorithm is an algorithm that performs two useful operations on such a data structure:

• Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
• Union: Join two subsets into a single subset.

...

Disjoint-set forests are data structures where each set is represented by a tree data structure, in which each node holds a reference to its parent node (see spaghetti stack).

In a disjoint-set forest, the representative of each set is the root of that set's tree. Find follows parent nodes until it reaches the root. Union combines two trees into one by attaching the root of one to the root of the other.