Data Structures 15 - Graph Traversal

Code

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

// Define the queue size
#define QUEUE_SIZE 10

int* visitedPtr;

// Define a struct to represent the graph node queue
typedef struct GraphNodeQueue {
    int* nodes;  // Array for storing nodes
    int front;   // Front pointer of the queue
    int rear;    // Rear pointer of the queue
} GraphNodeQueue, *QueuePtr;

// Initialize the queue
QueuePtr initQueue() {
    QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct GraphNodeQueue));
    resultQueuePtr->nodes = (int*)malloc(QUEUE_SIZE * sizeof(int));
    resultQueuePtr->front = 0;
    resultQueuePtr->rear = 1;
    return resultQueuePtr;
}

// Check if the queue is empty
bool isQueueEmpty(QueuePtr paraQueuePtr) {
    if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) {
        return true;
    }
    return false;
}

// Enqueue operation
void enqueue(QueuePtr paraQueuePtr, int paraNode) {
    if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) {
        printf("Error, trying to enqueue %d. queue full.\r\n", paraNode);
        return;
    }
    paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode;
    paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
}

// Dequeue operation
int dequeue(QueuePtr paraQueuePtr) {
    if (isQueueEmpty(paraQueuePtr)) {
        printf("Error, empty queue\r\n");
        return -1;
    }
    paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;
    return paraQueuePtr->nodes[paraQueuePtr->front];
}

// Define a struct to represent the graph
typedef struct Graph {
    int** connections;  // Adjacency matrix of the graph
    int numNodes;       // Number of nodes in the graph
} *GraphPtr;

// Initialize the graph
GraphPtr initGraph(int paraSize, int** paraData) {
    int i, j;
    GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph));
    resultPtr->numNodes = paraSize;
    resultPtr->connections = (int**)malloc(paraSize * sizeof(int*));
    for (i = 0; i < paraSize; i++) {
        resultPtr->connections[i] = (int*)malloc(paraSize * sizeof(int));
        for (j = 0; j < paraSize; j++) {
            resultPtr->connections[i][j] = paraData[i][j];
        }
    }
    return resultPtr;
}

// Initialize the traversal auxiliary array
void initTranverse(GraphPtr paraGraphPtr) {
    int i;
    visitedPtr = (int*)malloc(paraGraphPtr->numNodes * sizeof(int));
    for (i = 0; i < paraGraphPtr->numNodes; i++) {
        visitedPtr[i] = 0;
    }
}

// Depth-first traversal
void depthFirstTranverse(GraphPtr paraGraphPtr, int paraNode) {
    int i;
    visitedPtr[paraNode] = 1;
    printf("%d\t", paraNode);
    for (i = 0; i < paraGraphPtr->numNodes; i++) {
        if (!visitedPtr[i]) {
            if (paraGraphPtr->connections[paraNode][i]) {
                depthFirstTranverse(paraGraphPtr, i);
            }
        }
    }
}

// Breadth-first traversal
void widthFirstTranverse(GraphPtr paraGraphPtr, int paraStart) {
    int i, j, tempNode;
    i = 0;
    QueuePtr tempQueuePtr = initQueue();
    printf("%d\t", paraStart);
    visitedPtr[paraStart] = 1;
    enqueue(tempQueuePtr, paraStart);
    while (!isQueueEmpty(tempQueuePtr)) {
        tempNode = dequeue(tempQueuePtr);
        visitedPtr[tempNode] = 1;
        i++;
        for (j = 0; j < paraGraphPtr->numNodes; j++) {
            if (visitedPtr[j])
                continue;
            if (paraGraphPtr->connections[tempNode][j] == 0)
                continue;
            printf("%d\t", j);
            visitedPtr[j] = 1;
            enqueue(tempQueuePtr, j);
        }
    }
}

// Test graph traversal
void testGraphTranverse() {
    int i, j;
    int myGraph[5][5] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 1, 1},
        {1, 0, 1, 0, 0},
        {0, 1, 1, 0, 0}
    };
    int** tempPtr;
    printf("Preparing data\r\n");
    tempPtr = (int**)malloc(5 * sizeof(int*));
    for (i = 0; i < 5; i++) {
        tempPtr[i] = (int*)malloc(5 * sizeof(int));
    }
    for (i = 0; i < 5; i++) {
        for (j = 0; j < 5; j++) {
            tempPtr[i][j] = myGraph[i][j];
        }
    }
    printf("Data ready\r\n");
    GraphPtr tempGraphPtr = initGraph(5, tempPtr);
    printf("num nodes = %d \r\n", tempGraphPtr->numNodes);
    printf("Graph initialized\r\n");

    printf("Depth first visit:\r\n");
    initTranverse(tempGraphPtr);
    depthFirstTranverse(tempGraphPtr, 4);

    printf("\r\nWidth first visit:\r\n");
    initTranverse(tempGraphPtr);
    widthFirstTranverse(tempGraphPtr, 4);
}

int main() {
    testGraphTranverse();
    return 1;
}

Summary

This code implements a graph traversal program consisting of the following main components:

1. Graph Node Queue:

   • The GraphNodeQueue struct defines a circular queue that supports basic enqueue and dequeue operations.
   • The initQueue function initializes a queue.
   • The isQueueEmpty function checks whether the queue is empty.
   • The enqueue and dequeue functions implement the enqueue and dequeue operations respectively.

2. Graph Representation and Initialization:

   • The Graph struct represents a graph, including an adjacency matrix and the number of nodes.
   • The initGraph function initializes the graph structure from a given adjacency matrix.

3. Traversal Helpers:

   • The initTranverse function initializes the auxiliary array visitedPtr, used to record whether each node has been visited.
   • The depthFirstTranverse function implements depth-first traversal, visiting all connected nodes recursively.
   • The widthFirstTranverse function implements breadth-first traversal, visiting nodes level by level using a queue.

4. Testing:

   • The testGraphTranverse function defines a 5-node graph and tests both depth-first and breadth-first traversal, printing the order in which nodes are visited.

This code demonstrates how to use basic queues and recursion to implement graph traversal, providing detailed steps and function calls that make the entire traversal process clear and straightforward.

Output

Graph initialized
Depth first visit:
4       1       0       3       2
Width first visit:
4       1       2       0       3
 
...Program finished with exit code 1
Press ENTER to exit console.