An Introduction to Graph Data Structures in C

Graphs are a fundamental and powerful data structure in computer science, used to represent relationships between objects. They can model various real - world scenarios such as social networks, transportation networks, and electrical circuits. In this blog post, we’ll explore the basics of graph data structures in the C programming language, including how to represent graphs, perform common operations on them, and best practices for working with graphs in C.

What are Graphs?
Graph Representation in C
- Adjacency Matrix
- Adjacency List
Common Graph Operations
- Adding Edges
- Traversing Graphs
Best Practices
Conclusion
References

What are Graphs?

A graph is a non - linear data structure consisting of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices.

Vertices: These are the fundamental units of a graph. For example, in a social network graph, vertices can represent people.
Edges: Edges define the relationships between vertices. In the social network example, an edge between two vertices can represent a friendship between two people.

Graphs can be classified into two main types:

Directed Graphs: Edges have a direction. If there is an edge from vertex A to vertex B, it does not necessarily mean there is an edge from B to A.
Undirected Graphs: Edges have no direction. If there is an edge between vertex A and vertex B, it implies there is also an edge from B to A.

Graph Representation in C

Adjacency Matrix

An adjacency matrix is a two - dimensional array of size V x V, where V is the number of vertices in the graph. If there is an edge between vertex i and vertex j, then matrix[i][j] = 1 (or a non - zero value), otherwise matrix[i][j] = 0.

#include <stdio.h>
#define V 5

// Function to add an edge to the graph represented by adjacency matrix
void addEdge(int graph[V][V], int src, int dest) {
    graph[src][dest] = 1;
    graph[dest][src] = 1; // For undirected graph
}

// Function to print the adjacency matrix
void printGraph(int graph[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int 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;
}

In this code:

We first define a constant V representing the number of vertices.
The addEdge function updates the adjacency matrix to mark the presence of an edge between two vertices.
The printGraph function is used to display the adjacency matrix.

Adjacency List

An adjacency list is an array of linked lists. Each element in the array corresponds to a vertex, and the linked list associated with that element contains all the vertices adjacent to the corresponding vertex.

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

// Structure to represent an adjacency list node
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// Structure to represent an adjacency list
typedef struct AdjList {
    AdjListNode *head;
} AdjList;

// Structure to represent a graph
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// Function to create a new adjacency list node
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// Function to add an edge to the graph
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to print the adjacency list
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    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;
}

In this code:

We define a AdjListNode structure to represent nodes in the linked list.
The Graph structure contains an array of AdjList which stores the adjacency list for each vertex.
The addEdge function inserts a new node at the beginning of the linked list corresponding to the source vertex.

Common Graph Operations

Adding Edges

The process of adding edges has been shown in the above code examples. For the adjacency matrix, we simply update the corresponding position in the matrix. For the adjacency list, we create a new node and insert it into the appropriate linked list.

Traversing Graphs

Depth - First Search (DFS)

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

// Structure to represent an adjacency list node
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// Structure to represent an adjacency list
typedef struct AdjList {
    AdjListNode *head;
} AdjList;

// Structure to represent a graph
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// Function to create a new adjacency list node
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// Function to add an edge to the graph
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to perform DFS
void DFSUtil(Graph* graph, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", v);

    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl) {
        int adjVertex = pCrawl->dest;
        if (!visited[adjVertex]) {
            DFSUtil(graph, adjVertex, visited);
        }
        pCrawl = pCrawl->next;
    }
}

void DFS(Graph* graph, int start) {
    int* visited = (int*)calloc(graph->V, sizeof(int));
    DFSUtil(graph, start, visited);
    free(visited);
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    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);

    printf("DFS starting from vertex 0: ");
    DFS(graph, 0);
    return 0;
}

In this DFS code:

The DFSUtil function is a recursive helper function that marks the current vertex as visited and then recursively explores all its unvisited adjacent vertices.
The DFS function initializes the visited array and calls DFSUtil to start the traversal from the given starting vertex.

Best Practices

Memory Management: When using dynamic memory allocation in C (e.g., malloc), always remember to free the allocated memory to avoid memory leaks. For example, in the adjacency list implementation, you need to free each node in the linked list and the graph structure itself when it’s no longer needed.
Code Readability: Use meaningful variable and function names. For example, in the graph code, names like newAdjListNode and addEdge clearly indicate their purposes.
Error Handling: Check the return values of functions like malloc. If malloc fails to allocate memory, it returns NULL. Your code should handle this situation gracefully to avoid crashes.

Conclusion

Graph data structures are a versatile and powerful tool in computer science, and implementing them in C can be both rewarding and challenging. In this blog, we’ve covered the basics of graph representation using adjacency matrix and adjacency list, common operations like adding edges and traversing graphs, and best practices for working with graphs in C. By using these concepts and following the best practices, you can efficiently model and solve problems that involve relationships between objects.

References

“Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
GeeksforGeeks - A popular online platform for computer science and programming resources, especially for graph data structures and algorithms in C.

It’s important to note that while these references provide a wealth of information, always verify the accuracy and applicability of the information based on your specific needs.