c++ - Kruskal's Algorithm in O(n log n) -
i'm interested in learning how run kruskal's algorithm on o(n log n) in c++. have implemented algorithm solution runs on o(n^2), , code below.
i know should possible run kruskal's on o(n log n), i'm stymied how can done. appreciate , tips.
#include <vector> #include <algorithm> #include <set> using namespace std; //sort weight bool sorting (vector<int> i, vector<int> j) {return i[2]<j[2];} class submap { private: set<int> finder; public: submap(int x) {finder.insert(x);} submap(set<int> x) {finder = x;} set<int> pointreturn() {return finder;} //function add new set current tree void add(set<int> np) { finder.insert(np.begin(), np.end()); } void add(int n) { finder.insert(n); } int size() {return int(finder.size());} //find function returns true if value not found bool find(int x) { if (finder.find(x) == finder.end()) return true; else return false; } }; class map { private: vector<submap> submaps; public: int find(int x) { int finder = -1; for(int = 0; < int(submaps.size()); i++) { if(!submaps[i].find(x)) { finder = i; break; } } return finder; } void newsubmap(int a, int b) { set<int> nextset; nextset.insert(a); nextset.insert(b); submaps.push_back(submap(nextset)); } void addendum(int a, int index) { submaps[index].add(a); } submap subfind(int i) {return submaps[i];} void fuse(int index1, int index2) { submaps[index1].add(submaps[index2].pointreturn()); vector<submap> nextmaps; for(int = 0; < int(submaps.size()); i++) { if (i != index2) nextmaps.push_back(submaps[i]); } submaps = nextmaps; } int size() {return submaps[0].size();} }; map kruskal (vector<vector<int>> &graph, int weight, int junct) { //sort graph sort(graph.begin(), graph.end(), sorting); map currmap; int usedweight = 0; for(int i=0; i<graph.size(); i++) { int = currmap.find(graph[i][0]); int b = currmap.find(graph[i][1]); //the boolean expression here false if both points in same submap if(a != b || == -1) { usedweight += graph[i][2]; //if neither point in map far if(a == -1 && b == -1) { currmap.newsubmap(graph[i][0], graph[i][1]); } //if 1 point in map far else if (a != -1 && b == -1) { currmap.addendum(graph[i][1], a); } else if (a == -1 && b != -1) { currmap.addendum(graph[i][0], b); } //if both points in map, different submaps else { currmap.fuse(a, b); } } //if first set in map spanning, algorithm done if(currmap.size() == junct) break; } return (currmap); }