پیاده سازی الگوریتم kruskal با استفاده از disjoint set - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

پیاده سازی الگوریتم kruskal با استفاده از disjoint set

+2 امتیاز
104 بازدید

قبلا داخل این سوال در مورد disjoint set توضحاتی دادم.

این جا در مورد یکی از کاربرد های این ساختار که پیاده سازی الگوریتم kruskal هست بحث می کنیم. 

سوال : چطور میشه الگوریتم kruskal را با ++C پیاده سازی کرد ؟

 

سوال شده آبان 18, 1393  بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85

1 پاسخ

+2 امتیاز

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

الگوریتم kruskal یک الگوریتم Greedy هست  . بر اساس انتخاب یال با کمترین طول کار می کنه .

 

و به این شکل عمل می کنه که  :

همه یال های گراف را  به شکل صعودی مرتب می کنیم  .

بعد این لیست مرتب شده شامل یال ها را پیمایش می کنیم اگر 2 راس دو طرف اون یال تا حالا جزوی از مجموعه جواب نبودن اون یال رو به مجموعه جواب اضافه می کنیم.

 

مرتبه زمانی این الگوریتم هم همون مرتبه زمانی مرتب سازی لیست یال ها یعنی ElogE هست (E تعداد یال هاست ) که داخل گراف های dense مرتبه زمانی v^2)logv ) میشه (v تعداد راس ها ) .

 

شبه کد از ویکیپدیا :

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

کد ++C با استفاده از این سوال : 

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

using Weight = int;
using Node = int;
using WeightedEdges = std::vector<std::pair<Weight, std::pair<Node, Node>>>;
using Edges = std::vector<std::pair<Node, Node>>;
using Nodes = std::vector<Node>;
using std::make_pair;


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_;

};

Edges Kruskal(WeightedEdges& edges,const Nodes& nodes)
{
	Edges A;
	DisjointSet<int> s;

	for (auto& node : nodes)
		s.makeSet(node);
	std::sort(edges.begin(), edges.end());

	for (auto& edge : edges)
	{
		Node u = edge.second.first;
		Node v = edge.second.second;
		if (s.find_set(u) != s.find_set(v))
		{
			s.merge(u, v);
			A.push_back(make_pair(u,v));
		}
	}
	return A;
}

int main(int argc, char** argv)
{
	/*
	      1
		6 |\ 3
		  | \ 
          2--3
		    4
	*/
	WeightedEdges graph;//baraye zakhire shekl bala
	graph.push_back(make_pair(6, make_pair(1, 2)));  //edge az ras 1 be 2 ba tool 6
	graph.push_back(make_pair(3, make_pair(1, 3)));  //edge az ras 1 be 3 ba tool 3
	graph.push_back(make_pair(4, make_pair(2, 3)));  //edge az ras 2 be 3 ba tool 4

	Edges res = Kruskal(graph, { 1, 2, 3 });

	for (auto& edge : res)
	{
		std::cout << edge.first << " " << edge.second << " \n"; 
	}

	//khorooji
	// 1 2
	// 2 3

	return 0;
}
 
پاسخ داده شده آبان 18, 1393 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
...