最小生成树-Kruskal算法(C++实现)

• 最开始用Java实现，然后为了作业再用C++实现，然后就发现用C++坑太多了，改这改那的，索性这里就直接说一下注意的点，然后就贴完整代码了，想看详解的小伙伴戳链接
• 算法具体思路与实现详解 https://www.jianshu.com/p/43fa94126ed0

注意

• C++的数组要动态分配内存，才可以实现用变量作为数组大小
  • 一维数组
    int *nums = new int[N]();
    变量类型声明为指针类型，int[N]()的()是把所有元素初始化为0，没有()则未初始化，建议不要省略()
  • 二维数组
    变量类型是指针的指针，并且new关键字后面是int*[N]，不要省略*，因为二维数组每个元素也是一个数组
    然后要对每个元素初始化matrix[i] = new int[N]();

    int **matrix = new int *[N];
    for (int i = 0; i < N; ++i) {
        matrix[i] = new int[N]();
    }

• 在上面分享的用Java实现文章里我用的是重写compare()方法来实现对带权图的边排序，而C++实现我用的是重载<运算符，下面的代码存在于边类Edge里，作用是对Edge使用<运算符时，查找邻接矩阵中对应边的权值，权值小的边是"小"的

    bool operator<(const Edge &e) {
        return matrix[this->A][this->B] < matrix[e.A][e.B];
    }

完整代码

• 头文件

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;


int N = 6;  // 节点个数(修改节点数只需要改这个变量)
int **matrix = new int *[N];  // 暂定6个节点
class Edge {
public:
    // 边的两个端点索引
    int A;
    int B;

    Edge(int A, int B) {
        this->A = A;
        this->B = B;
    }

    bool operator<(const Edge &e) {
        return matrix[this->A][this->B] < matrix[e.A][e.B];
    }
};

template<class T>
class Graph {
public:

    T *datas = new T[N]();  // 保存每个节点的数据
    vector<Edge> edges;  // 边集合

    Graph();

    ~Graph();

    void setDatas(T[]);

    void setMatrix(int, int, int);

    void setEdges();

    int getEnd(int[], int);

    void KruskalTree();
};

• 源文件

#include "Graph.h"

template<class T>
Graph<T>::Graph() {
    for (int i = 0; i < N; ++i) {
        matrix[i] = new int[N]();
    }
}

template<class T>
Graph<T>::~Graph() {
    delete this;
}

template<class T>
void Graph<T>::setDatas(T datas[]) {
    for (int i = 0; i < N; i++) {
        this->datas[i] = datas[i];
    }
}

template<class T>
void Graph<T>::setMatrix(int from, int to, int weight) {
    matrix[from][to] = weight;
}

template<class T>
void Graph<T>::setEdges() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (matrix[i][j] > 0) {
                Edge edge = Edge(i, j);
                edges.push_back(edge);
            }
        }
    }
}

template<class T>
int Graph<T>::getEnd(int ends[], int i) {
    while (ends[i] != 0) {
        i = ends[i];
    }
    return i;
}

template<class T>
void Graph<T>::KruskalTree() {
    int *ends = new int[N]();
    sort(edges.begin(), edges.end());
    vector<Edge> result;
    for (Edge edge : edges) {
        int endOfA = getEnd(ends, edge.A);
        int endOfB = getEnd(ends, edge.B);
        if (endOfA != endOfB) {
            ends[endOfA] = endOfB;
            result.push_back(edge);
        }
    }
    int **treeMatrix = new int*[N];
    for (int i = 0; i < N; ++i) {
        treeMatrix[i] = new int[N]();
    }
    for (Edge edge : result) {
        treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
    }
    for (Edge edge : result) {
        cout << datas[edge.A] << "-" << datas[edge.B] << endl;
    }
    cout << "最小生成树邻接矩阵: " << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << treeMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    string datas[] = {"A", "B", "C", "D", "E", "F"};
    Graph<string> *graph = new Graph<string>();
    graph->setDatas(datas);
    int set[8][3] = {{0, 1, 1},
                     {0, 2, 3},
                     {1, 3, 2},
                     {1, 5, 2},
                     {2, 3, 4},
                     {2, 5, 7},
                     {3, 4, 1},
                     {4, 5, 8}};
    for (int i = 0; i < sizeof(set) / sizeof(set[0]); i++) {
        graph->setMatrix(set[i][0], set[i][1], set[i][2]);
    }
    graph->setEdges();
    graph->KruskalTree();
    return 0;
}

测试结果

图

最小生成树

输出结果如下
[ < A-1-B >, < D-1-E >, < B-2-D >, < B-2-F >, < A-3-C > ]
最小生成树的邻接矩阵:
[0, 1, 3, 0, 0, 0]
[0, 0, 0, 2, 0, 2]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]