GESP 8级客观题｜最小生成树｜课堂讲解

考试频率：高频。本卷共 2 题。

1. 求一个包含v个顶点、e条边的带权连通无向图的最小生成树，Prim算法的时间复杂度为$O(v+e)$。

   {{ select(1) }}

• 对
• 错

2. 下面最小生成树的Kruskal算法程序中，横线处应该填入的是（）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int u, v, weight;
    bool operator <(const Edge & other) const {
        return weight < other.weight;
    }
};
int findParent(int vertex, vector<int> & parent) {
    if (parent[vertex] == -1)
        return vertex;
    return parent[vertex] = findParent(parent[vertex], parent);
}
int main() {
    int n, m;
    cin >> n >> m; // n: 顶点数, m: 边数
    vector<Edge> edges(m);
    vector<int> parent(n, -1);
    int totalWeight = 0;
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    sort(edges.begin(), edges.end());
    for (const auto & edge : edges) {
        int uParent = findParent(edge.u, parent);
        int vParent = findParent(edge.v, parent);
        if (__________) { // 在此处填入选项
            parent[uParent] = vParent;
            totalWeight += edge.weight;
        }
    }
}

{{ select(2) }}

• uParent == vParent
• uParent >= vParent
• uParent != vParent
• uParent <= vParent