Untitled

#include <iostream>
#include <set>
#include <vector>

using namespace std;

void primShortestPath(vector<vector<int>>& graph, int V) {
    set<int> U;  // Set of visited vertices
    set<int> VU; // Set of unvisited vertices
    set<pair<int, int>> T; // Set of edges in the minimum spanning tree

    U.insert(0); // Start with the first vertex

    for (int v = 1; v < V; v++) {
        VU.insert(v);
    }

    while (U != VU) {
        int minCost = INT_MAX;
        int u, v;

        for (int vertex : U) {
            for (int neighbor : VU) {
                if (graph[vertex][neighbor] < minCost) {
                    minCost = graph[vertex][neighbor];
                    u = vertex;
                    v = neighbor;
                }
            }
        }

        T.insert({u, v});
        U.insert(v);
        VU.erase(v);
    }

    // Print the minimum spanning tree edges
    cout << "Minimum Spanning Tree Edges:" << endl;
    for (auto edge : T) {
        cout << edge.first << " - " << edge.second << endl;
    }
}

int main() {
    int V = 6;  // Number of vertices

    // Example graph represented as an adjacency matrix
    vector<vector<int>> graph = {
        {0, 3, 1, 6, 0, 0},
        {3, 0, 5, 0, 3, 0},
        {1, 5, 0, 5, 6, 4},
        {6, 0, 5, 0, 0, 2},
        {0, 3, 6, 0, 0, 6},
        {0, 0, 4, 2, 6, 0}
    };

    primShortestPath(graph, V);

    return 0;
}