首页 > 试题广场 >

Disjoint-set data structure

[问答题]
Disjoint-set data structure
In computing, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. It supports two useful operations:

Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its "representative"; by comparing the result of two Find operations, one can determine whether two elements are in the same subset.
Union: Join two subsets into a single subset.
The other important operation, MakeSet, which makes a set containing only a given element (a singleton), is generally trivial. With these three operations, many practical partitioning problems can be solved (see the Applications section).

In order to define these operations more precisely, some way of representing the sets is needed. One common approach is to select a fixed element of each set, called its representative, to represent the set as a whole. Then, Find(x) returns the representative of the set that x belongs to, and Union takes two set representatives as its arguments.

Disjoint-set forests
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. 

Question 1: According to the information above,implement three functions:MakeSet(),Fins(),Union().You can use C/C++/Python/Java.

In this naive form, this approach is no better than the linked-list approach, because the tree it creates can be highly unbalanced; however, it can be enhanced in two ways.

The first way, called union by rank, is to always attach the smaller tree to the root of the larger tree, rather than vice versa. Since it is the depth of the tree that affects the running time, the tree with smaller depth gets added under the root of the deeper tree, which only increases the depth if the depths were equal. In the context of this algorithm, the term rank is used instead of depth since it stops being equal to the depth if path compression (described below) is also used. One-element trees are defined to have a rank of zero, and whenever two trees of the same rank r are united, the rank of the result is r+1. Just applying this technique alone yields a worst-case running-time of O(\log n) per MakeSet, Union, or Find operation. 

The second improvement, called path compression, is a way of flattening the structure of the tree whenever Find is used on it. The idea is that each node visited on the way to a root node may as well be attached directly to the root node; they all share the same representative. To effect this, as Find recursively traverses up the tree, it changes each node's parent reference to point to the root that it found. The resulting tree is much flatter, speeding up future operations not only on these elements but on those referencing them, directly or indirectly. 

Question 2: Implement the above improvements.You can use C/C++/Python/Java.

Question 3:You can answer this question in Chinese.What are the real world applications of this data structures?
Question 1:
#define N 100
int* represent = new int[N];  void MakeSet()
{
    for (int i = 0; i < N; ++i)
    {
         represent[i] = i;
    }
}

int Find(int x)
{
    if (represent[x] == x)
    {
        return x;
    }
    else
    {
        return Find(represent[x]);
    }
}

void Union(int x, int y)
{
    represent[represent[x]] = represent[y];
}

Question 2:
int* rank = new int[N];

void MakeSet()
{
    for (int i = 0; i < N; ++i)
    {
        represent[i] = i;
        rank[i] = 0;
    } 
}

int Find(int x)
{
    if (represent[x] == x)
    {
        rank[x] = 0;
        return x;
    }
    else
    {
        represent[x] = find(represent[x]);
        rank[x] = rank[represent[x]] + 1;
        return represent[x];
    }
}

void Union(int x, int y)
{
    if (rank[x] < rank[y])
    {
        int temp = x;
        x = y;
        y = temp;
    }
    represent[represent[x]] = represent[y];
    find(x);
}

Question 3:
并查询;Kruscal算法。
发表于 2015-04-16 16:16:47 回复(0)