Prim算法

Prim算法是一种用于寻找加权连通图的最小生成树（MST）的贪心算法。该算法从任意一个顶点开始，逐步将最近的未访问过的顶点添加到正在构建的最小生成树中，直到所有顶点都被包含在内。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAX = 100; // 假设图的最大顶点数为100
int graph[MAX][MAX]; // 图的邻接矩阵表示
bool visited[MAX];   // 访问标记数组
int parent[MAX];     // 记录每个节点的父节点
int key[MAX];        // 记录每个节点的最小权重
int V;               // 图中的顶点数

// 更新与当前节点u相连的所有节点的key值
void updateKeys(int u) {
    for (int v = 0; v < V; ++v) {
        if (graph[u][v] && !visited[v]) {
            if (graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
}

// 找到下一个加入MST的节点
int findMinKeyVertex() {
    int minKey = INT_MAX, minVertex = -1;
    for (int v = 0; v < V; ++v) {
        if (!visited[v] && key[v] < minKey) {
            minKey = key[v];
            minVertex = v;
        }
    }
    return minVertex;
}

// Prim算法主函数
void primMST() {
    // 初始化所有节点的key值为无穷大，parent为-1
    for (int i = 0; i < V; ++i) {
        key[i] = INT_MAX;
        parent[i] = -1;
        visited[i] = false;
    }

    // 选择第一个顶点作为起始点
    int startVertex = 0;
    key[startVertex] = 0; // 起始点的key值为0

    for (int count = 0; count < V - 1; ++count) {
        // 选择key值最小且未访问的顶点
        int u = findMinKeyVertex();
        visited[u] = true;

        // 更新与顶点u相邻的所有顶点的key值
        updateKeys(u);
    }

    // 输出最小生成树的边和权重
    cout << "Edge \tWeight\n";
    for (int i = 1; i < V; ++i) {
        cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl;
    }
}

int main() {
    // 示例图
    V = 5; // 设置顶点数量
    memset(graph, 0, sizeof(graph)); // 初始化图的邻接矩阵

    // 添加边和权重
    graph[0][1] = 2; graph[1][0] = 2;
    graph[0][3] = 6; graph[3][0] = 6;
    graph[1][2] = 3; graph[2][1] = 3;
    graph[1][3] = 8; graph[3][1] = 8;
    graph[1][4] = 5; graph[4][1] = 5;
    graph[2][4] = 7; graph[4][2] = 7;

    // 调用Prim算法
    primMST();

    return 0;
}

primMST() 函数实现了Prim算法的核心逻辑，它首先选择一个起点并将它的key值设置为0，然后通过循环不断选择最小key值的未访问节点，并更新与之相连的所有节点的key值。最后，程序输出最小生成树中每条边的信息及对应的权重。

Kruskal算法

Kruskal算法是另一种常用的求解加权连通图最小生成树（MST）的算法。与Prim算法不同的是，Kruskal算法关注的是边而不是顶点。它通过按权重顺序选择边来构建MST，同时确保不会形成环路。

代码实现

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

using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    vector<Edge> edges;
};

// 并查集相关函数
int find(vector<int>& subsets, int i) {
    if (subsets[i] == i)
        return i;
    return find(subsets, subsets[i]);
}

void Union(vector<int>& subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    subsets[xroot] = yroot;
}

// 比较函数，用于排序边
bool compare(Edge e1, Edge e2) {
    return e1.weight < e2.weight;
}

// Kruskal算法主函数
void KruskalMST(Graph& graph) {
    int V = graph.V;
    vector<Edge> result; // 存储MST的结果
    int e = 0; // 结果数组的索引
    sort(graph.edges.begin(), graph.edges.end(), compare); // 对边按权重排序

    vector<int> subsets(V);
    for (int v = 0; v < V; ++v)
        subsets[v] = v; // 初始化并查集

    for (Edge next_edge : graph.edges) {
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        // 如果包括这条边不会形成环，则包含这条边
        if (x != y) {
            result.push_back(next_edge);
            Union(subsets, x, y);
            e++;
        }

        // 如果包含了V-1条边，就停止
        if (e == V - 1)
            break;
    }

    // 输出MST中的边和它们的权重
    cout << "Following are the edges in the constructed MST\n";
    for (Edge edge : result)
        cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
}

int main() {
    // 创建一个图实例
    Graph graph;
    graph.V = 4; // 顶点数
    graph.E = 5; // 边数
    graph.edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};

    // 调用Kruskal算法
    KruskalMST(graph);

    return 0;
}