پیاده سازی disjoint set

Question

ساختار disjoint set رو چطوری میشه داخل ++C کد زد ؟ آیا راهی بهتر از استفاده از Tree و پوینتر هم وجود داره ؟

Answer 1

disjoint set ساختاری هست  که جاهایی استفاده میشه که نیاز به تعداد زیاد از 3 تا عملیات زیر داشته باشید :

1_ make set  ساختن یک مجموعه جدید

2_find set پیدا کردن این که یک عنصر خاص در کدوم مجموعه هست

3_ union  ترکیب 2 مجموعه 

 

برای نمونه یکی از کاربرد ها برای پیاده سازی الگوریتم kruskal هست که برای پیدا کردن minimum spanning tree استفاده میشه .

 

در ساختار بالا amortized cost  برای انجام n تا عملیات های بالا  از این مرتبه هست :   

 

که alpha تابعی هست با سرعت رشد خیلی پایین  که f تعداد find set ها  و n تعداد عملیات های union هست . پس میشه گفت تقریبا هر 3 عملیات در این ساختار (1)O هستند .

 

برای پیاده سازی علاوه بر forest ,tree میشه از hash table هم استفاده کرد :

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

template<class T>
class DisjointSet
{
public:
	void makeSet(const T& a)
	{
		parents_[a] = a;
		Ranks_[a] = 0;
	}
	void merge(const T& a, const T& b)
	{
		auto root_a = find_set(a);
		auto root_b = find_set(b);
		//az rank estefade mikonim ta onsori ke child haye bishtari dare parent bashe
		//ta forest mored nazaremoon flat tar beshe
		if (Ranks_[root_a] > Ranks_[root_b]){
			parents_[root_b] = root_a;
		}
		else{
			parents_[root_a] = root_b;
			if (Ranks_[root_a] == Ranks_[root_b])
				Ranks_[root_b]++;
		}
	}

	T find_set(const T& a)
	{
		if (parents_[a] != a){
			//path compression(baraye sorat bishtar har bar ke find mikonim parent 
                        //ro ham onsor aval mizarim ke dafeat badi sari tar bashe jost ojoo
			parents_[a] = find_set(parents_[a]);
		}
		return parents_[a];
	}
private:
	std::unordered_map<T, T> parents_;
	std::unordered_map<T, int > Ranks_;

};

int main(int argc, char **argv)
{
	DisjointSet<std::string> disjointSet;

	disjointSet.makeSet("set1");
	disjointSet.makeSet("set2");
	disjointSet.makeSet("set3");
	disjointSet.makeSet("set4");
	disjointSet.makeSet("set5");


	cout << disjointSet.find_set("set1") << '\n';//set1 chap mishe

	disjointSet.merge("set1", "set2");//trakib 2 ta majmoo e

	cout << disjointSet.find_set("set1") << '\n';//parent set2 chap mishe

	disjointSet.merge("set4", "set5");

	cout << disjointSet.find_set("set4") << '\n';//parent yani set5 chap mishe

	disjointSet.merge("set4", "set1");//tarkib set1 va set4

	//dakhele cout payeen az oonjaiee ke hame set ha merge shodan pas hame parent ha 
	//yeki hastan pas 4 ta set2 chap mishe
	cout << disjointSet.find_set("set1") << " " << disjointSet.find_set("set2") << " "<<
		disjointSet.find_set("set5") <<" "<< disjointSet.find_set("set4") << '\n';

	return 0;
}