#include <>
#define MAX 100
#define MAXCOST 100000
int graph[MAX][MAX];
int Prim(int graph[MAX][MAX], int n)
{
/* lowcost[i] records the minimum weight of the edge with i as the end point. When lowcost[i]=0, it means that the end point i is added to the spanning tree */
int lowcost[MAX];
/* mst[i] records the starting point corresponding to lowcost[i] */
int mst[MAX];
int i, j, min, minid, sum = 0;
/* By default, node 0 is selected to be added to the spanning tree, and initializes it from node 1 */
for (i = 1; i < n; i++)
{
/* The shortest distance is initialized to the distance from other nodes to node 0 */
lowcost[i] = graph[0][i];
/* The starting point of all nodes is the default node No. 0 */
mst[i] = 0;
}
/* Mark No. 0 to join the spanning tree */
lowcost[0] = 0;
/* N nodes need at least n-1 edges to form the minimum spanning tree */
for (i = 1; i < n; i++)
{
min = MAXCOST;
minid = 0;
/* Find the node minid of the minimum weight edge that meets the condition */
for (j =1; j <n; j++)
{
/* The edge weight is small and not in the spanning tree */
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}
/* Output information about the spanning tree edge: start point, end point, weight */
cout<<"The starting point, end point and weight of the generated edges are: "<< mst[minid]+1<<" "<minid+1<<" "<min<<endl;
/* Accumulated weight value */
sum += min;
/* Mark the node minid to join the spanning tree */
lowcost[minid] = 0;
/* Update the weight of the current node minid to other nodes */
for (j = 1; j < n; j++)
{
/* Find smaller weights */
if (graph[minid][j] < lowcost[j])
{
/* Update weight information */
lowcost[j] = graph[minid][j];
/* The starting point of the update minimum weight edge */
mst[j] = minid;
}
}
}
/* Returns the minimum weight and */
return sum;
}
void main()
{
int i, j, m,n;
int cost;
/* Number of read nodes */
cout<<"Please enter the number of nodes in this graph: ";
cin>>m;
/* Initialize the graph, the distance between all nodes is infinite */
for (i = 0; i <m; i++)
{
for (j =i+1; j <m; j++)
{
cout<<"Please enter the weight of node"<<i+1<<" to node"<<j+1<<" edge, if there is no boundary, enter MAXCOST(100000):";
cin>>n;
graph[i][j] = n;
graph[j][i] = n;
}
graph[i][i]=MAXCOST;
}
/* Solve the minimum spanning tree */
cost = Prim(graph, m);
cout<<"The weight of the minimum spanning tree is: "<<cost<<endl;
}