I'm getting just Segmentation Fault
from my code but it's not telling me where. I'm guessing it has to do with the file but I'm not entirely sure. That is the only thing keeping me from testing and debugging the rest of the code (if this implementation of Prim's actually works and if the file is being read properly). Feel free to ask questions. Thanks in advance!
Here is my code:
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define N 10
#define INF INT_MAX
int spanning[N][N];
int main(int argc, char **argv) {
int prims(int amtrx[][N], int *n);
void printpaths(int *n);
if (argc < 2) {
printf("Missing Filename.\n");
return(1);
} else if (argc > 2) {
printf("Too many arguments.\n");
return(1);
}
FILE* f = fopen(argv[1], "r");
int *n, *stv, i, j, nsz, nedg, fr, to, vtx, wt;
vtx = 1111;
nedg = 999;
nsz = 100;
stv = 0;
n = 0;
if(f) {
fscanf(f, "%d %d %d", &nsz, &nedg, &vtx);
int amtrx[nsz][N];
for(i = 0; i < nsz; i++){
for(j = 0; j < nsz; j++){
amtrx[i][j] = INF;
}
}
for(i = 0; i < nedg; i++){
fscanf(f, "%d %d %d", &fr, &to, &wt);
amtrx[fr][to] = wt;
amtrx[to][fr] = wt;
}
*n = nsz;
*stv = vtx;
int total_cost = prims(amtrx, n);
printpaths(n);
printf("\n\nTotal cost of spanning tree: %d", total_cost);
} else {
printf("Failed to open the file\n");
}
fclose(f);
return 0;
}
int prims(int amtrx[][N], int *n) {
int cost[N][N];
int u, v, min_distance, distance[N], from[N];
int visited[N], no_of_edges, i, min_cost, j;
for(i = 0; i < *n; i++)
for(j = 0; j < *n; j++) {
if(amtrx[i][j] == 0)
cost[i][j] = INF;
else {
cost[i][j] = amtrx[i][j];
spanning[i][j] = 0;
}
}
distance[0] = 0;
visited[0] = 1;
for(i = 1; i < *n; i++) {
distance[i] = cost[0][i];
from[i] = 0;
visited[i] = 0;
}
min_cost = 0;
no_of_edges = *n - 1;
while(no_of_edges > 0) {
min_distance = INF;
for(i = 1; i < *n ; i++)
if(visited[i] == 0 && distance[i] < min_distance) {
v = i;
min_distance = distance[i];
}
u = from[v];
spanning[u][v] = distance[v];
spanning[v][u] = distance[v];
no_of_edges--;
visited[v] = 1;
for(i = 1; i < *n; i++)
if(visited[i] == 0 && cost[i][v] < distance[i]) {
distance[i] = cost[i][v];
from[i] = v;
}
min_cost = min_cost + cost[u][v];
}
return min_cost;
}
void printpaths(int *n) {
int i, j;
for(i = 0; i < *n; i++) {
printf("\n");
for(j = 0; j < *n; j++)
printf("%d\t", spanning[i][j]);
}
}
Here is what is in the input file:
6 10 0 <-- size, edges, start
0 1 16 <-- from, to, weight
0 5 21
0 4 19
1 2 5
1 3 6
1 5 11
2 3 10
3 4 18
3 5 14
4 5 33
As @kaylum said above. You should use the a debuggger when you see the Segmentation Fault
. For me, i always try to run the program with valgrind
when i see this fault. With valgrind
(Use -g
when you compile the code, firstly) you can see where is memory fault.
For your program, it figures out this line *n = nsz;
. So look at the variable n
and nsz
.
Btw, you have to allocate for 2 varibale n
and stv
instead of assigning them to 0.
stv = malloc(sizeof(int));
n = malloc(sizeof(int));
The result after allocating:
0 16 0 0 0 0
16 0 5 6 0 11
0 5 0 0 0 0
0 6 0 0 18 0
0 0 0 18 0 0
0 11 0 0 0 0
Total cost of spanning tree: 56