Prim算法实现结果不一致，请求问题排查与解决

问题背景 #

我用STL的priority_queue实现了Prim算法寻找最小生成树（MST），部分测试用例能得到正确结果，但另一些测试用例输出错误。输入为邻接表格式的文本文件：第一行是顶点数量，后续每行以顶点索引开头，后跟若干（邻接顶点索引，边权值）对。

测试用例情况 #

运行正确的测试用例 #

9
0 1 4 7 8
1 2 8 7 11
2 3 7 8 2 5 4
3 4 9 5 14
4 5 10 
5 6 2
6 7 1 8 6
7 8 7

运行错误的测试用例 #

9
0 8 18 6 1 4 10 7 7
6 4 6 1 20
4 1 3 7 5
1 3 12
3 8 4 2 9
2 5 2 
8 2 15 5 8

代码实现 #

Prim算法核心逻辑 #

void MST::getMST() {
    const int n = graph.adjacencyList.size();
    std::vector<bool> visited(n, false);
    std::vector<int> parent(n, -1);
    std::vector<int> key(n, std::numeric_limits<int>::max());

    // Start from vertex 0
    key[0] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        if (parent[u] != -1) {
            edges.push_back({parent[u], u});
        }
        for (const auto& [v, weight] : graph.adjacencyList[u]) {
            if (!visited[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }
}

图文件读取函数 #

void Graph::readGraphFromFile(const std::string& filename) {
    std::ifstream inFile(filename);
    if (!inFile) {
        std::cerr << "Unable to open the file: " << filename << std::endl;
        return;
    }

    // Read vertex count
    inFile >> vertexCount;
    adjacencyList.resize(vertexCount);

    // Read edges
    std::string line;
    std::getline(inFile, line); // Read the rest of the line after vertexCount
    while (std::getline(inFile, line)) {
        std::istringstream lineStream(line);
        int vertex, neighbor, weight;
        lineStream >> vertex;
        while (lineStream >> neighbor >> weight) {
            adjacencyList[vertex].push_back(std::make_pair(neighbor, weight));
        }
    }

    inFile.close();
}

MST类构造函数 #

// Constructor initializes the MST object with the input graph
MST::MST(const Graph& g){
    graph = g;
}

MST边保存到文件函数 #

// Saves the Minimum Spanning Tree edges to a file
void MST::saveToFile(const std::string& filename) const {
    std::ofstream outFile(filename);
    if (!outFile) {
        std::cerr << "Unable to open the file: " << filename << std::endl;
        return;
    }

    for (const auto& edge : edges) {
        outFile << edge.first << " -- " << edge.second << std::endl;
    }

    outFile.close();
}

提问 #

请问我的实现中可能存在哪些问题？

内容的提问来源于stack exchange，提问作者volia