اولا این که 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;
}