C++ program to perform Prim's Algorithm

// Prim's Algorithm #include using namespace std; int main() { int v, i, j, min, c, current, nv; // Assume maxium weight as 1000 int INF = 1000; // Create graph of v vertices cout << "Enter the number of vertices in the graph: "; cin >> v; int adj[v+1][v+1]; for (i=1; i<=v; i++) { for (j=1; j<=v; j++) { adj[i][j] = -1; } } bool visited[v+1]; int path[v+1]; int distance[v+1]; for (i=1; i<=v; i++) { for (j=1; j<=v; j++) { if (j==i) { adj[i][j] = 0; } else { if (adj[i][j] >= 0) { // do nothing } else { cout << "If vertex " << i << " is adjacent to vertex " << j << endl; cout << "Enter weight of edge, else enter 0: "; cin >> adj[i][j]; adj[j][i] = adj[i][j]; cout << endl; } } } } // Initializing the 3 arrays for (i=1; i<=v; i++) { visited[i] = false; path[i] = 0; distance[i] = INF; } current = 1; visited[current] = true; nv = 1; while ( nv != v ) { // Processing the adjacent vertices for (i=1; i<=v; i++) if (adj[current][i] != 0) if(visited[i] != true) if(distance[i] > adj[current][i]) { distance[i] = adj[current][i]; path[i] = current ; } // Finding the closest vertex min = INF ; for (i = 1; i <= v; i++) if(visited[i] != true) if(distance[i] < min) { min = distance[i]; current = i; } visited[current] = true; nv = nv + 1; } c=0; for (i=2; i<=v; i++) { c = c + distance[i]; cout << "Vertex " << i << " is connected to vertex " << path[i]; cout << endl; } cout << "Minimum cost is " << c; cout << endl; return 0; } // aiuto