Advanced Data Structures: Graphs in C

Hello there, fellow coder! Today, we’re going to dive into the fascinating world of graphs in C. Graphs are an advanced data structure that can represent relationships between items in a more general way than other data structures like arrays, linked lists, stacks, queues, and even trees. So, buckle up and let’s get started!

What is a Graph?

A graph is a non-linear data structure that consists of nodes, often called vertices, and edges. Each edge connects a pair of vertices. Graphs are used to solve many real-life problems that involve representing networks, including computer networks, social networks, web pages, etc.

Types of Graphs

There are two main types of graphs: directed and undirected. In a directed graph, each edge has a direction. In an undirected graph, edges do not have a direction; if there’s an edge from vertex A to vertex B, there’s implicitly an edge from vertex B to vertex A.

Representing Graphs in C

There are several ways to represent a graph in C, but the two most common ways are adjacency matrix and adjacency list.

Adjacency Matrix

An adjacency matrix is a 2D array of size V x V where V is the number of vertices in the graph. Let’s look at an example:

#include<stdio.h>

#define V 5

void addEdge(int graph[V][V], int src, int dest) {
    graph[src][dest] = 1;
    graph[dest][src] = 1;
}

void printGraph(int graph[V][V]) {
    int i, j;
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = {0};

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

Code Explanation

In this code, we first define a 2D array graph of size V x V and initialize all its elements to 0. The addEdge function sets graph[src][dest] and graph[dest][src] to 1, indicating that there’s an edge between the src and dest vertices. The printGraph function prints the adjacency matrix.

Adjacency List

An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex. The adjacency list representation of a graph is more space-efficient than the adjacency matrix if the graph is sparse (i.e., the number of edges is much less than the number of vertices).

Here’s an example:

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

struct Node {
    int dest;
    struct Node* next;
};

struct List {
    struct Node *head;
};

struct Graph {
    int V;
    struct List* array;
};

struct Node* newListNode(int dest) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int V)

Code Explanation

In this code, we first define a `Node` structure that has two members: `dest` and `next`. The `dest` member stores the destination vertex and `next` points to the next node in the list.

Next, we define a `List` structure that has a single member `head`, which points to the first node in each list.

Then, we define a `Graph` structure that has two members: `V`, which stores the number of vertices in the graph, and `array`, which is an array of `List`.

The `newListNode` function creates a new node for a given destination vertex. The `createGraph` function creates a graph with `V` vertices; no edges are added yet.

Graph Traversal

Graph traversal is the process of visiting every vertex in a graph. Two of the most common graph traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).

Depth-First Search (DFS)

DFS is a graph traversal method that explores as far as possible along each branch before backtracking. Here’s a simple implementation of DFS:

void DFS(struct Graph* graph, int vertex, bool visited[]) {
visited[vertex] = true;
printf("%d ", vertex);

    struct Node* temp = graph->array[vertex].head;
    while(temp) {
        int adjVertex = temp->dest;

        if(!visited[adjVertex]) {
            DFS(graph, adjVertex, visited);
        }
        temp = temp->next;
    }
}

Code Explanation

In this code, the `DFS` function takes a graph, a vertex, and a `visited` array. It marks the current vertex as visited and prints it. Then, it recursively calls `DFS` for all adjacent vertices of the current vertex.

Breadth-First Search (BFS)

BFS is another graph traversal method that explores all the vertices at the present depth before moving on to vertices at the next depth level. BFS uses a queue data structure to keep track of vertices to visit.

Here’s a simple implementation of BFS:

void BFS(struct Graph* graph, int startVertex) {
    bool visited[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;

    List* queue = createList();

    visited[startVertex] = true;
    addToList(queue, startVertex);

    while(!isListEmpty(queue)) {
        printList(queue);
        int currentVertex = removeFromFront(queue);

        struct Node* temp = graph->array[currentVertex].head;
        while(temp) {
            int adjVertex = temp->dest;

            if(!visited[adjVertex]) {
                addToList(queue, adjVertex);
                visited[adjVertex] = true;
            }
            temp = temp->next;
        }
    }
}

Code Explanation

In this code, the BFS function takes a graph and a start vertex. It creates a visited array to keep track of visited vertices and a queue to keep track of vertices to visit. It marks the start vertex as visited and adds it to the queue. Then, it enters a while loop that continues until the queue is empty. In each iteration of the loop, it removes a vertex from the front of the queue and adds all its unvisited adjacent vertices to the back of the queue.

Wrapping Up

And that’s a wrap on our journey through graphs in C! We’ve covered a lot of ground, from the basics of what a graph is, to different ways to represent a graph in C, to graph traversal methods. I hope you’ve found this tutorial helpful and that it’s given you a solid foundation in working with graphs in C.

Frequently Asked Questions (FAQ)

Related Tutorials

1. Introduction to Data Structures in C
2. Trees in C
3. Advanced Data Structures: Binary Trees in C
4. Advanced Data Structures: Segment Trees in C
5. Advanced Data Structures: Heaps in C

Remember, practice is key when it comes to mastering data structures and algorithms. So, don’t just read these tutorials—get your hands dirty with some coding as well!