# Untitled

unknown
plain_text
a year ago
1.4 kB
1
Indexable
Never
```#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

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;
}
```