Prim算法和Kruskal算法的实现C++

Prim算法和Kruskal算法都是用于求解图的最小生成树的算法。以下是它们的基本实现：

**Prim算法** (优先队列实现)
Prim算法从任意一个顶点开始，每次选择与当前生成树相连且距离最近的未加入边，直到所有顶点都被包含在内。以下是C++的基本实现框架：

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

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

class Graph {
public:
    // 添加边、邻接矩阵等其他辅助函数...
    std::vector<int> prim(int start) {
        std::vector<bool> visited(numVertices, false);
        std_distances[start] = 0;
        priority_queue<Edge, std::vector<Edge>, greater<Edge>> pq;
        pq.push({start, -1, 0}); // 使用负权重表示更优

        while (!pq.empty()) {
            Edge current = pq.top(); pq.pop();
            if (!visited[current.src]) {
                visited[current.src] = true;
                for (int neighbor : adjList[current.src]) {
                    int newWeight = current.weight + edgeWeights[current.src][neighbor];
                    if (!visited[neighbor] && newWeight < std_distances[neighbor]) {
                        pq.push({neighbor, current.src, newWeight});
                        std_distances[neighbor] = newWeight;
                    }
                }
            }
        }

        return std_distances; // 返回最小生成树各顶点到起始顶点的距离
    }
private:
    int numVertices;
    std::vector<int> std_distances;
    // 其他数据结构，如邻接列表 adjList 等
};

**Kruskal算法**
Kruskal算法则是将所有的边从小到大按权值排序，然后依次添加边，如果这条边不会形成环，则将其加入生成树。以下是C++的基本实现：

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

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

bool isBridge(Graph &graph, int u, int v, std::vector<int> &parent) {
    // ... 实现桥梁检测逻辑 ...
}

Graph::Graph() { ... } // 初始化

std::vector<Edge> kruskal(int numVertices) {
    std::vector<Edge> edges(graph.getEdges()); // 获取边并排序
    std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) -> bool { return a.weight < b.weight; });

    std::vector<int> parent(numVertices, -1); // 每个顶点的父节点
    std::vector<Edge> mst;
    for (const auto &edge : edges) {
        int rootU = findRoot(edge.src, parent);
        int rootV = findRoot(edge.dest, parent);
        if (rootU != rootV && !isBridge(*this, rootU, rootV, parent)) {
            mst.push_back(edge);
            unionSets(rootU, rootV, parent);
        }
    }
    return mst;
}

// 辅助函数 findRoot 和 unionSets