1

假设现在你有一组数据：

Data 1: (1, 2);
Data 2: (1, 3);
Data 3: (7, 8);
Data 4: (8, 20);

现在的任务是合并数据集，如果它与另一个数据集有共同元素。在我们的示例中，数据 1 将与数据 2 合并，因为它们共享公共数字 1。数据 3 和数据 4 也是如此。我的问题是我们如何才能在 C++ 中非常有效地实现此功能。目前我的实现是基于 std::vector > 数据结构的，如下代码所示：

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>


using namespace std;
bool find_the_element(const set<int> &mysets, const vector<int> &myvector)
{
    for(int i=0; i<myvector.size(); i++)
    {
        set<int>::iterator it;
        it = mysets.find(myvector[i]);
        if (it != mysets.end())
            return true;
    }
    return false;

}





int main () 
{



    set<vector<int> > myset;
    vector<int> a;
    a.push_back(1);
    a.push_back(2);

    vector<int> b;
    b.push_back(1);
    b.push_back(3);

    vector<int> c;
    c.push_back(7);
    c.push_back(8);

    vector<int> d;
    d.push_back(8);
    d.push_back(20);
    vector<vector<int> > my_vector_array;
    my_vector_array.push_back(a);
    my_vector_array.push_back(b);
    my_vector_array.push_back(c);
    my_vector_array.push_back(d);


    vector<set<int> > my_sets;
    for(int i=0; i<my_vector_array.size(); i++)
    {
        vector<int> temp_vector = my_vector_array[i];

        if (my_sets.empty())
        {
            set<int> temp_set;
            for(int j=0; j<temp_vector.size(); j++)
                temp_set.insert(temp_vector[j]);

            my_sets.push_back(temp_set);
        }
        else
        {
            bool b_find = false;
            for(int j=0; j<my_sets.size(); j++)
            {
                set<int>temp_set;
                temp_set = my_sets[j];
                if (find_the_element(temp_set,temp_vector))
                {
                    b_find = true;
                    my_sets[j].insert(temp_vector.begin(), temp_vector.end());

                    break;
                }

            }
            if (b_find)
            {
                // something already done
            }
            else
            {
                set<int> temp_set;
                for(int j=0; j<temp_vector.size(); j++)
                    temp_set.insert(temp_vector[j]);

                my_sets.push_back(temp_set);
            }

        }
    }
}

我想知道 C++ 中是否有更有效的数据结构或有效的算法来完成这项工作。谢谢！

4

1 回答 1

4

实现可以快速合并的集合的最有效方法之一是使用不相交集数据结构。

这个想法是最初将每个集合表示为一个链表，链表的头部作为整个集合的标识符。随着集合被合并，节点被重新指向头部以加速进一步的搜索。

链接上的文章有伪代码；C++ 实现应该不会太难。

您需要单独保留一个将map您到目前为止看到的整数与它们在不相交集森林中的节点连接起来。您将浏览您的数据集，一个一个地获取它们的项目，在 中查找项目map，然后点击指向其数据集的链接，或者使用您正在添加的项目创建一个新的“单例”不相交集。

于 2012-10-03T14:06:04.693 回答