Search code examples
cmemorygraphsegmentation-faultruntime-error

I am getting segmentation error /fault when I run the below code


I am new to C. I get a segmentation error when I run the below graph traversal algorithm program in an online C compiler. I know the error is due to accessing the memory that has not been initialized or not accessible but I don't know where the error occurs.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max 5
struct vertex{
    char name;
    bool isVisited;
};
int queue[max];
int rear = -1, front = 0, queueCount = 0, vertexCount = 0;
struct vertex* adjList[max];
int adjMat[max][max];
void insert(int data){
    queue[++rear] = data;
    queueCount++;
}
int delete(){
    queueCount--;
    return queue[front++];
}
bool isEmpty(){
    return queueCount == 0;
}
void addVertex(char name){
    struct vertex* v = (struct vertex*)malloc(sizeof(struct vertex));
    v->name = name;
    v->isVisited = false;
    adjList[vertexCount++] = v;
}
void addEdge(int start, int end){
    adjMat[end][start] = 1;
    adjMat[start][end] = 1;
}
void display(int vertexIndex){
    printf("%c", adjList[vertexIndex]->name);
}
int getAdjUnvisitedVertices(int vertexIndex){
    for (int i = 0; i < vertexCount; i++){
        if (adjMat[vertexIndex][i] == 1 && adjList[i]->isVisited == false){
            return i;
        }
    }
    return -1;
}
void BFS(){
    adjList[0]->isVisited = true;
    display(0);
    insert(0);
    int unvisitedVertex;
    while (!isEmpty()){
        int tempVertex = delete();
        while (unvisitedVertex = getAdjUnvisitedVertices(tempVertex) != -1){
            adjList[unvisitedVertex]->isVisited = true;
            display(unvisitedVertex);
            insert(unvisitedVertex);
        }
    }
    for (int i = 0; i < vertexCount; i++){
        adjList[i]->isVisited = false;
    }
}
void main(){
    for (int i = 0; i < max; i++){
        for (int j = 0; j < max; j++){
            adjMat[i][j] = 0;
        }
    }
    addVertex('S');
    addVertex('A');
    addVertex('B');
    addVertex('C');
    addVertex('D');
    addEdge(0,1);
    addEdge(0,2);
    addEdge(0,3);
    addEdge(1,4);
    addEdge(2,4);
    addEdge(3,4);
    printf("Breadth First Traversal : ");
    BFS();
}

Solution

  • An infinite loop occurs here causing the array boundary exception. Reason is the assignment statement was not executed.

     while (unvisitedVertex = getAdjUnvisitedVertices(tempVertex) != -1)
    

    To ensure assignment operation take place along with the conditional operator, it needs to be parenthesised.

    while ((unvisitedVertex = getAdjUnvisitedVertices(tempVertex)) != -1)
    

    With this change result is Breadth First Traversal : SABCD