3

我有兴趣学习如何在 C++ 中在 O(n log n) 上运行 Kruskal 算法。我已经使用在 O(n^2) 上运行的解决方案实现了该算法，其代码如下。

我知道应该可以在 O(n log n) 上运行 Kruskal，但我不知道如何做到这一点。我将不胜感激任何和所有提示。

#include <vector>
#include <algorithm>
#include <set>
using namespace std;

//sort by 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 to add new set to 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 the value is 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 i = 0; i < 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 i = 0; i < 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 the graph
    sort(graph.begin(), graph.end(), sorting);
    Map currmap;

    int usedweight = 0;
    for(int i=0; i<graph.size(); i++) {
        int a = currmap.find(graph[i][0]);
        int b = currmap.find(graph[i][1]);

        //the boolean expression here is false if both points are already in the same submap
        if(a != b || a == -1) {

            usedweight += graph[i][2];

            //if neither point is in the map so far
            if(a == -1 && b == -1) {
                currmap.newsubmap(graph[i][0], graph[i][1]);
            }

            //if one point is in the map so 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 are in the map, but different submaps
            else {
                currmap.fuse(a, b);
            }
        }
        //if the first set in the map is spanning, the algorithm is done
        if(currmap.size() == junct)
            break;
    }

    return (currmap);
}
4

0 回答 0