I implemented a program which is supposed to find minimum spanning tree using Prim. The graph's edges are described in a file.
So first of all, the program reads this file and stocks edges in a data structure. After that, it runs the algorithm. Here is the full code :
#include <stdio.h>
#include <stdlib.h>
#define MAXVERTICES 1000
#define INFINITY 99999
#define TAILLEMAX 100
struct vertex {
int visited, predecessor;
int dist; // distance qui sépare ce noeud de la distance minimale d'un autre noeud
};
int treeEdge[MAXVERTICES][2], mstCost; // tableau des 'aretes' qui constituent l'arbre couvrant
int graphEdge[MAXVERTICES][MAXVERTICES], nodeCount; // matrice d'adjacences (couts séparant chaque sommet des autres sommets)
struct vertex node[MAXVERTICES]; // tableau de sommets numérotés de 1 à n
/* construct the input graph */
void buildGraph() {
int source, dest, weight, test;
char temp[TAILLEMAX];
FILE* fichier = NULL;
fichier = fopen("inst_v100.txt", "r");
if (fichier != NULL)
{
fgets(temp, TAILLEMAX, fichier); // sauter ligne
fscanf(fichier,"%s%d",temp,&nodeCount); // nbr de sommets
fgets(temp, TAILLEMAX, fichier);
fgets(temp, TAILLEMAX, fichier);
while (1)
{
test = fscanf(fichier,"%d%d%d",&source,&dest,&weight);
if(test==0)
break;
/* update weight of the edge */
graphEdge[source][dest] = weight;
graphEdge[dest][source] = weight;
fgets(temp, TAILLEMAX, fichier); // sauter ligne
}
}
fclose(fichier);
return;
}
/* all vertices are visited or not */
int allVisited() {
int i;
for (i = 0; i < nodeCount; i++)
if (node[i].visited == 0)
return 0;
return 1;
}
/* construct minimum spanning tree */
int buildTree() {
int i = 0, count = 0, currentNode, mindist;
while (i < nodeCount) {
node[i].visited = 0;
node[i].predecessor = 0;
node[i].dist = INFINITY;
i++;
}
node[0].visited = 1;
node[0].dist = 0;
currentNode = 0;
while (allVisited() == 0) {
for (i = 0; i < nodeCount; i++) { // pour le sommet courant, chercher la distance min qui le sépare de chaque sommet
/* Find the adjacent vertices and update the edge lenght */
if(graphEdge[currentNode][i] > 0 && node[i].visited == 0) {
if (graphEdge[currentNode][i] < node[i].dist) {
node[i].predecessor = currentNode;
node[i].dist = graphEdge[currentNode][i];
}
}
}
mindist = INFINITY;
/* trouver l'arete avec le poids minimum */
for (i = 0; i < nodeCount; i++) {
if (node[i].dist < mindist && node[i].visited == 0) {
mindist = node[i].dist;
currentNode = i;
}
}
/* Mark the vertex as visited - edge with min cost */
node[currentNode].visited = 1;
treeEdge[count][0] = node[currentNode].predecessor;
treeEdge[count][1] = currentNode;
/* calculate cost of MST */
mstCost = mstCost + graphEdge[treeEdge[count][0]][treeEdge[count][1]];
count++;
}
return count;
}
int main() {
int i, count1;
/* construct graph */
buildGraph();
count1 = buildTree();
printf("MST is composed of below edges:\n");
for (i = 0; i < count1; i++) {
printf("%d<->%d\n", treeEdge[i][0], treeEdge[i][1]);
}
printf("\n");
printf("Cost of Minimum Spanning Tree: %d\n", mstCost);
return 0;
}
Awkwardly, when the execution starts, the program sends a SIGSEV signal.
could you help me figure out the mistake i'm doing ? Thank's in advance.
Problem Solved.
In fact if you look closely, i used fgets and fscanf and it caused ambiguity. The solution was using fgets (to store the line read in a string), then sscanf to take informatio needed from that string.
It gives something like this :
fgets(the_string, MAXLENGTH, file);
sscanf(the_string,"%d",&number_wanted);
thank you very much anyway, and i hope my answer will be helpful for other people with same problem.