prime算法求最小生成树

Prime算法是求解最小生成树的一种常用算法，其基本思想是从图中任意一个节点开始，每次选择与当前生成树中的节点相邻且权值最小的边，将其加入生成树，并将其相邻的节点加入到已访问的节点集合中，直到生成树中包含所有节点为止。

具体实现步骤如下：
1. 选择一个任意的起始节点，将其加入已访问节点集合visited中。
2. 遍历与已访问节点集合visited中的节点相邻的所有节点，找到权值最小的边，将其加入生成树中。
3. 将新加入的节点加入已访问节点集合visited中。
4. 重复步骤2和3，直到已访问节点集合visited中包含所有节点。

下面是伪代码实现：

// 定义节点和边的数据结构
struct Node {
    int id; // 节点编号
};
struct Edge {
    int from; // 起始节点编号
    int to; // 目标节点编号
    int weight; // 权值
};

vector<Node> nodes; // 所有节点
vector<Edge> edges; // 所有边
vector<int> visited(nodes.size(), 0); // 已访问节点
vector<Edge> mst; // 最小生成树

// 从start节点开始构建最小生成树
void prime(int start) {
    visited[start] = 1; // 将start节点加入已访问节点集合中
    while (mst.size() < nodes.size() - 1) { // 生成树中边数为节点数-1
        Edge min_edge = {0, 0, INT_MAX}; // 初始化权值最小边
        for (Edge e : edges) {
            if (visited[e.from] ^ visited[e.to]) { // 如果边的两端节点一个已访问，一个未访问
                if (e.weight < min_edge.weight) { // 选择权值最小的边
                    min_edge = e;
                }
            }
        }
        visited[min_edge.from] = visited[min_edge.to] = 1; // 将新加入的节点加入已访问节点集合中
        mst.push_back(min_edge); // 将权值最小边加入生成树中
    }
}

该算法的时间复杂度为O(n^2)，其中n为节点数。如果使用堆优化可以将时间复杂度降为O(nlogn)。