用邻接表和优先队列实现的prim算法c++代码不用pair

Prim算法是一种用于寻找图的最小生成树的算法。在C++中，使用邻接表和优先队列（通常是std::priority_queue）可以有效地实现Prim算法。以下是使用邻接表和优先队列实现Prim算法的C++代码示例，不使用pair类型：

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

using namespace std;

typedef struct Edge {
    int to;     // 目标顶点
    int weight; // 边的权重
} Edge;

typedef struct {
    vector<Edge*> adj; // 邻接表
} Graph;

Graph* createGraph(int vertices) {
    Graph* graph = new Graph;
    graph->adj = vector<Edge*>(vertices);
    return graph;
}

void addEdge(Graph* graph, int src, int dest, int weight) {
    Edge* edge = new Edge;
    edge->to = dest;
    edge->weight = weight;
    graph->adj[src].push_back(edge);
}

int primMST(Graph* graph, int src) {
    int vertices = graph->adj.size();
    vector<int> key(vertices, INT_MAX); // 存储每个顶点到MST的最短边的权重
    vector<int> parent(vertices, -1); // 存储MST的边的父节点
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq; // 优先队列

    key[src] = 0; // 源点到自身的距离设为0
    pq.push({0, src}); // 将源点加入优先队列

    while (!pq.empty()) {
        Edge currentEdge = pq.top();
        pq.pop();

        int u = currentEdge.to;
        if (key[u] != currentEdge.weight) continue; // 如果当前边不是最优边，则跳过

        for (Edge* edge : graph->adj[u]) {
            int v = edge->to;
            if (key[v] > edge->weight) {
                key[v] = edge->weight;
                pq.push(*edge);
                parent[v] = u;
            }
        }
    }

    int sum = 0;
    for (int i = 1; i < vertices; ++i) {
        if (parent[i] != -1) {
            sum += graph->adj[parent[i]][0]->weight; // 假设每个顶点的邻接表的第一个边是到i的边
        }
    }

    return sum;
}

int main() {
    int vertices = 5;
    Graph* graph = createGraph(vertices);

    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 2, 4);
    addEdge(graph, 1, 2, 2);
    addEdge(graph, 1, 3, 3);
    addEdge(graph, 2, 3, 3);
    addEdge(graph, 3, 4, 2);

    int mstWeight = primMST(graph, 0);
    cout << "Minimum Spanning Tree weight: " << mstWeight << endl;

    return 0;
}

这段代码首先定义了图的邻接表表示和边的结构。然后，它实现了createGraph函数来创建图，addEdge函数来添加边，以及primMST函数来计算最小生成树的权重。在primMST函数中，使用了一个优先队列来存储边，并在每次迭代中选择权重最小的边加入最小生成树。最后，main函数展示了如何使用这些函数来计算最小生成树的权重。1234567