最小生成树利用无向网的的邻接矩阵存储结构实现prim算法的最小生成树和kruskal算法的最小生成树

Prim算法和Kruskal算法都是求解最小生成树的经典算法之一，这里我们分别介绍如何使用无向网的邻接矩阵存储结构实现这两个算法。

## Prim算法

Prim算法是一种贪心算法，它从一个源节点开始不断扩展最小生成树的边，直到所有节点都被包含在最小生成树中。具体实现步骤如下：

1. 初始化最小生成树的边集为空集，将源节点加入最小生成树中。

2. 对于不在最小生成树中的节点，计算它们与最小生成树中节点的连边的权值，选择权值最小的边加入最小生成树中。

3. 重复步骤2，直到所有节点都被包含在最小生成树中。

下面是使用C++实现Prim算法的代码：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAXN = 100; // 最大节点数
const int INF = INT_MAX; // 无穷大

int graph[MAXN][MAXN]; // 无向网的邻接矩阵
bool visited[MAXN]; // 节点是否被访问过
int dist[MAXN]; // 节点到最小生成树的距离
int parent[MAXN]; // 最小生成树中节点的父节点

void prim(int start, int n) {
    // 初始化
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[start] = 0;
    // 按照Prim算法，不断扩展最小生成树
    for (int i = 0; i < n; i++) {
        // 找到距离最小的节点
        int minDist = INF, minIndex = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }
        // 将节点加入最小生成树中
        visited[minIndex] = true;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[minIndex][j] < dist[j]) {
                dist[j] = graph[minIndex][j];
                parent[j] = minIndex;
            }
        }
    }
}

int main() {
    int n = 6; // 节点数
    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = INF;
        }
    }
    graph[0][1] = graph[1][0] = 6;
    graph[0][2] = graph[2][0] = 1;
    graph[0][3] = graph[3][0] = 5;
    graph[1][2] = graph[2][1] = 5;
    graph[1][4] = graph[4][1] = 3;
    graph[2][3] = graph[3][2] = 5;
    graph[2][4] = graph[4][2] = 6;
    graph[2][5] = graph[5][2] = 4;
    graph[3][5] = graph[5][3] = 2;
    graph[4][5] = graph[5][4] = 6;
    prim(0, n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) {
            cout << parent[i] << "-" << i << " " << graph[parent[i]][i] << endl;
            sum += graph[parent[i]][i];
        }
    }
    cout << "Weight of MST: " << sum << endl;
    return 0;
}

## Kruskal算法

Kruskal算法也是一种贪心算法，它从所有边中选择权值最小的边，依次加入最小生成树中，直到所有节点都被包含在最小生成树中。具体实现步骤如下：

1. 初始化最小生成树的边集为空集。

2. 将所有边按照权值从小到大排序。

3. 依次选择每条边，如果它的两个端点不在同一个连通分量中，则将它加入最小生成树中，否则跳过。

4. 重复步骤3，直到所有节点都被包含在最小生成树中。

下面是使用C++实现Kruskal算法的代码：

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

const int MAXN = 100; // 最大节点数
const int INF = INT_MAX; // 无穷大

struct Edge {
    int from, to, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

int parent[MAXN]; // 节点的父节点
int rank[MAXN]; // 节点所在集合的秩

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;
    if (rank[rootX] < rank[rootY]) {
        swap(rootX, rootY);
    }
    parent[rootY] = rootX;
    if (rank[rootX] == rank[rootY]) {
        rank[rootX]++;
    }
}

vector<Edge> kruskal(int n, vector<Edge>& edges) {
    // 初始化
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    // 将边按照权值从小到大排序
    sort(edges.begin(), edges.end());
    // 依次选择每条边
    vector<Edge> result;
    for (Edge edge : edges) {
        if (find(edge.from) != find(edge.to)) {
            result.push_back(edge);
            unionSet(edge.from, edge.to);
        }
    }
    return result;
}

int main() {
    int n = 6; // 节点数
    // 初始化边
    vector<Edge> edges = {
        {0, 1, 6},
        {0, 2, 1},
        {0, 3, 5},
        {1, 2, 5},
        {1, 4, 3},
        {2, 3, 5},
        {2, 4, 6},
        {2, 5, 4},
        {3, 5, 2},
        {4, 5, 6}
    };
    vector<Edge> result = kruskal(n, edges);
    int sum = 0;
    for (Edge edge : result) {
        cout << edge.from << "-" << edge.to << " " << edge.weight << endl;
        sum += edge.weight;
    }
    cout << "Weight of MST: " << sum << endl;
    return 0;
}