利用邻接矩阵表示无向图，请实现prim算法

Prim's algorithm, also known as the Prim's minimum spanning tree (MST) algorithm, is a popular algorithm for finding the minimum spanning tree of an undirected weighted graph represented using an adjacency matrix. Here's how you can implement it in C++:

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

using namespace std;

// Function to find the minimum edge weight
int min_edge(vector<vector<int>>& adj, vector<bool>& visited, int node, int& min_weight) {
    int min_val = INT_MAX;
    int min_index = -1;
    for (int i = 0; i < adj[node].size(); i++) {
        if (!visited[i] && adj[node][i] < min_val) {
            min_val = adj[node][i];
            min_index = i;
        }
    }
    min_weight = min_weight ? min_weight : min_val;
    return min_index;
}

// Function to perform Prim's Algorithm
vector<int> prim_mst(vector<vector<int>>& adj, int V) {
    vector<bool> visited(V, false);
    vector<int> parent(V, -1); // Parent array
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // Min heap for edges

    // Add the first vertex with weight 0
    visited[0] = true;
    pq.push({0, 0});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        // Find the minimum edge from the current node
        int min_weight = INT_MAX;
        int v = min_edge(adj, visited, u, min_weight);

        if (min_weight != INT_MAX) {
            // If found, mark the node as visited and update the parent
            visited[v] = true;
            parent[v] = u;

            // Relax the adjacent vertices
            for (int i = 0; i < adj[v].size(); i++) {
                if (!visited[i] && adj[u][i] < INT_MAX) {
                    pq.push({adj[u][i], i});
                }
            }
        }
    }

    return parent;
}

int main() {
    int V, E;
    cout << "Enter number of vertices: ";
    cin >> V;
    cout << "Enter number of edges: ";
    cin >> E;
    
    vector<vector<int>> adj(V, vector<int>(V, INT_MAX)); // Initialize adjacency matrix with infinite weights
    // Read the edges and their weights here

    prim_mst(adj, V); // Call the function
    // Print or use the parent array to reconstruct the MST
    return 0;
}

In this code, we create a `prim_mst` function that takes an adjacency matrix (`adj`) and the number of vertices (`V`). It uses a priority queue to keep track of the smallest edge weights and keeps a boolean array `visited` to mark which nodes are already included in the MST.

To use this implementation, you'll need to input the edges and their weights into the adjacency matrix before calling the `prim_mst` function. The returned `parent` array will then contain the parent-child relationships for each node in the minimum spanning tree.