C Graphs - Learn Graph Data Structure in C

C Graphs – Learn Graph Data Structure in C

A graph is a non-linear data structure made up of nodes (also called vertices) and edges connecting them. In this tutorial, we will explore how to represent graphs in C and implement various graph algorithms.

🔹 What is a Graph?

A graph consists of a finite set of vertices (or nodes) and a set of edges (or arcs) that connect pairs of vertices. There are two main types of graphs:

Directed Graph: Edges have a direction, i.e., they point from one vertex to another.
Undirected Graph: Edges have no direction, i.e., they simply connect two vertices.

📝 Example 1: Graph Representation in C (Adjacency Matrix)

In this example, we represent a graph using an adjacency matrix. The matrix is a 2D array where each element represents an edge between two vertices.

#include <stdio.h>

#define MAX_VERTICES 5

// Function to display the adjacency matrix of the graph
void displayGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    printf("Graph (Adjacency Matrix):\n");
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    // Adjacency matrix for an undirected graph
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 0, 1},
        {1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0}
    };
    
    // Display the graph
    displayGraph(graph);

    return 0;
}

Try It Now

🔹 Graph Traversals (BFS and DFS)

Graph traversal refers to the process of visiting all the vertices in a graph. There are two primary traversal methods:

Depth-First Search (DFS): Explores as far down a branch as possible before backtracking.
Breadth-First Search (BFS): Explores all the neighbors of a vertex before moving on to the next level.

📝 Example 2: Depth-First Search (DFS)

DFS is implemented using recursion or a stack. It starts at the root (or any arbitrary node), explores as far as possible along each branch, and then backtracks.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5

// Function to perform DFS traversal
void dfs(int graph[MAX_VERTICES][MAX_VERTICES], int visited[MAX_VERTICES], int vertex) {
    printf("%d ", vertex);
    visited[vertex] = 1;
    
    // Recur for all adjacent vertices
    for (int i = 0; i < MAX_VERTICES; i++) {
        if (graph[vertex][i] == 1 && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

int main() {
    // Adjacency matrix for an undirected graph
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 0, 1},
        {1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0}
    };

    int visited[MAX_VERTICES] = {0};

    // Perform DFS starting from vertex 0
    printf("DFS Traversal: ");
    dfs(graph, visited, 0);
    printf("\n");

    return 0;
}

Try It Now

📝 Example 3: Breadth-First Search (BFS)

BFS uses a queue data structure to explore vertices level by level. It is implemented iteratively.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5

// Queue structure for BFS
struct Queue {
    int items[MAX_VERTICES];
    int front;
    int rear;
};

void initQueue(struct Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(struct Queue* q) {
    return q->front == -1;
}

void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX_VERTICES - 1) {
        printf("Queue Full\n");
    } else {
        if (q->front == -1) {
            q->front = 0;
        }
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Empty\n");
        return -1;
    } else {
        int item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        return item;
    }
}

// Function to perform BFS traversal
void bfs(int graph[MAX_VERTICES][MAX_VERTICES], int visited[MAX_VERTICES], int start) {
    struct Queue q;
    initQueue(&q);

    visited[start] = 1;
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        int vertex = dequeue(&q);
        printf("%d ", vertex);
        
        // Visit all the adjacent vertices
        for (int i = 0; i < MAX_VERTICES; i++) {
            if (graph[vertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }
}

int main() {
    // Adjacency matrix for an undirected graph
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 0, 1},
        {1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0}
    };

    int visited[MAX_VERTICES] = {0};

    // Perform BFS starting from vertex 0
    printf("BFS Traversal: ");
    bfs(graph, visited, 0);
    printf("\n");

    return 0;
}

Try It Now

🎯 Key Takeaways

A graph consists of vertices and edges, and can be represented using an adjacency matrix or an adjacency list.
Graph traversal can be done using DFS (Depth-First Search) or BFS (Breadth-First Search).
Both traversal methods are useful for exploring and searching graphs.

📝 Practice Time!

Try modifying the graph representation or traversal methods. Experiment with directed graphs and create your own graph algorithms like detecting cycles or finding the shortest path!