I write a code about implement Prim's Algorithm and build the minimum spanning tree starting from vertex 1.
Here's the input format:
The first line will be the number of cases.
Each case begins with the number of vertices.
Suppose i input like this:
2
4
0,1,0,4
1,0,3,2
0,3,0,5
4,2,5,0
6
0,7,9,0,0,6
7,0,0,2,0,0
9,0,0,0,5,0
0,2,0,0,0,3
0,0,5,0,0,4
6,0,0,3,4,0
This means i have 2 test case, and the '4' means have 4 lines of vertices.
Example:
0,1,0,4
1,0,3,2
0,3,0,5
4,2,5,0
Will be like this
|0||1||2||3|
0| 0 1 0 4
1| 1 0 3 2
2| 0 3 0 5
3| 4 2 5 0
0 to 4 need 4 distances, 2-2 need 3 distances, etc
The first output was correct, which is
0-1 1
1-2 3
1-3 2
But the second output also same with the first output, which means wrong
0-1 1
1-2 3
1-3 2
Here's my code
#include <stdio.h>
#include <limits.h>
#include<stdbool.h>
// Number of vertices in the graph
#define V 100
// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
int v;
for (v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// A utility function to print the
// constructed MST stored in parent[]
int printMST(int parent[], int n, int graph[V][V])
{
int i;
char front1;
char back2;
//printf("Edge \tWeight\n");
for (i = 1; i < V; i++)
if(graph[i][parent[i]]!=0)
{
front1 = parent[i];
front1 += 16;
back2 = i;
back2 +=16;
printf("%d-%d %d \n", parent[i], i, graph[i][parent[i]]);
}
else
break;
}
// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
int i,count,v;
// Array to store constructed MST
int parent[V];
// Key values used to pick minimum weight edge in cut
int key[V];
// To represent set of vertices not yet included in MST
bool mstSet[V];
// Initialize all keys as INFINITE
for (i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
// Always include first 1st vertex in MST.
// Make key 0 so that this vertex is picked as first vertex.
key[0] = 0;
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (count = 0; count < V-1; count++)
{
// Pick the minimum key vertex from the
// set of vertices not yet included in MST
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of
// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (v = 0; v < V; v++)
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// print the constructed MST
printMST(parent, V, graph);
}
int main()
{
printf("%c",one1);
int i,j,limit1,limit2;
int column_a=0;
int row_a=0;
char datawithco[1000];
char *pch;
int graph[V][V];
scanf("%d",&limit1);
for(i=0; i<limit1; i++)
{
scanf("%d",&limit2);
for(j=0; j<limit2; j++)
{
scanf("%s",datawithco);
pch = strtok (datawithco,",");
while (pch != NULL)
{
//printf ("%s\n",pch);
graph[row_a][column_a] = atoi(pch);
column_a++;
pch = strtok (NULL, ",");
}
column_a=0;
row_a++;
}
primMST(graph);
graph[row_a][column_a] = '\0';
}
return 0;
}
The second output should be
0-5 6
5-3 3
3-1 2
5-4 4
4-2 5
You don't reset row_a variable after completing MST for each case.
for(i=0; i<limit1; i++)
{
scanf("%d",&limit2);
for(j=0; j<limit2; j++)
{
scanf("%s",datawithco);
pch = strtok (datawithco,",");
while (pch != NULL)
{
//printf ("%s\n",pch);
graph[row_a][column_a] = atoi(pch);
column_a++;
pch = strtok (NULL, ",");
}
column_a=0;
row_a++;
}
primMST(graph);
graph[row_a][column_a] = '\0';
row_a=0; //<---added
}
Besides you never reset your graph after each case. For these particular cases that you've provided, it is fine, because the number of vertices in the 2nd case is larger than the number of vertices in the 1st case, so the cells for the 2nd case will overwrite the cells for the 1st case, otherwise the cells left from the previous case will be regarded as valid ones which is obviously wrong. So you should either add the graph reset into primMST() function or add it at the start of every case