Understanding Graphs in Computer Science: Concepts and C Implementation

Graphs are one of the most versatile and powerful data structures in computer science, used to model relationships between objects. From social networks to GPS navigation systems, graphs help solve complex real-world problems efficiently. In this comprehensive guide, we'll explore graph fundamentals and implement them in C with complete code examples.

What is a Graph?

A graph is a non-linear data structure consisting of nodes (vertices) connected by edges. Formally, a graph G is defined as an ordered pair G = (V, E), where:

• V is a set of vertices (nodes)
• E is a set of edges connecting pairs of vertices

A simple undirected graph with 6 vertices and 7 edges

Types of Graphs

1. Directed vs Undirected Graphs

Undirected graphs have edges without direction, representing two-way relationships. Directed graphs (digraphs) have edges with direction, representing one-way relationships.

2. Weighted vs Unweighted Graphs

Weighted graphs assign values (weights) to edges, representing costs or distances. Unweighted graphs treat all edges equally.

3. Cyclic vs Acyclic Graphs

Cyclic graphs contain at least one cycle (a path that starts and ends at the same vertex). Acyclic graphs have no cycles (like trees).

Graph Representation in C

There are two primary ways to represent graphs in programming:

1. Adjacency Matrix

A 2D array where matrix[i][j] represents the edge between vertex i and j. For unweighted graphs, 1 represents an edge and 0 represents no edge.

Adjacency Matrix Implementation in C

#include <stdio.h>
#define V 5 // Number of vertices

// Function to initialize adjacency matrix
void initMatrix(int matrix[V][V]) {
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            matrix[i][j] = 0;
        }
    }
}

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

// Function to print adjacency matrix
void printMatrix(int matrix[V][V]) {
    printf("Adjacency Matrix:\n");
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int adjMatrix[V][V];
    initMatrix(adjMatrix);
    
    // Adding edges
    addEdge(adjMatrix, 0, 1);
    addEdge(adjMatrix, 0, 4);
    addEdge(adjMatrix, 1, 2);
    addEdge(adjMatrix, 1, 3);
    addEdge(adjMatrix, 1, 4);
    addEdge(adjMatrix, 2, 3);
    addEdge(adjMatrix, 3, 4);
    
    printMatrix(adjMatrix);
    return 0;
}

Adjacency Matrix: 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0

2. Adjacency List

An array of linked lists where each array element represents a vertex and its linked list represents adjacent vertices. More space-efficient for sparse graphs.

Adjacency List Implementation in C

#include <stdio.h>
#include <stdlib.h>
#define V 5 // Number of vertices

// Node structure for adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Graph structure
struct Graph {
    struct Node* adjList[V];
};

// Function to create a new node
struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode-> vertex = v;
    newNode-> next = NULL;
    return newNode;
}

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

// Function to add edge to undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode-> next = graph->adjList[src];
    graph-> adjList[src] = newNode;
    
    // Add edge from dest to src (undirected graph)
    newNode = createNode(src);
    newNode-> next = graph-> adjList[dest];
    graph-> adjList[dest] = newNode;
}

// Function to print adjacency list
void printGraph(struct Graph* graph) {
    printf("Adjacency List:\n");
    for(int i = 0; i < V; i++) {
        struct Node* temp = graph-> adjList[i];
        printf("Vertex %d: ", i);
        while(temp) {
            printf("%d -> ", temp-> vertex);
            temp = temp-> next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph* graph = createGraph();
    
    // Adding edges
    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;
}

Adjacency List: Vertex 0: 4 -> 1 -> NULL Vertex 1: 4 -> 3 -> 2 -> 0 -> NULL Vertex 2: 3 -> 1 -> NULL Vertex 3: 4 -> 2 -> 1 -> NULL Vertex 4: 3 -> 1 -> 0 -> NULL

Graph Traversal Algorithms

Traversal algorithms visit all vertices in a graph systematically. The two fundamental approaches are:

1. Breadth-First Search (BFS)

BFS explores all neighbor nodes at the present depth before moving to nodes at the next depth level. It uses a queue data structure.

BFS Implementation in C

#include <stdio.h>
#include <stdlib.h>
#define V 5

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

// Graph structure
struct Graph {
    int adjMatrix[V][V];
};

// Function to create a queue
struct Queue* createQueue() {
    struct Queue* q = malloc(sizeof(struct Queue));
    q-> front = -1;
    q-> rear = -1;
    return q;
}

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

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

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

// BFS function
void bfs(struct Graph* graph, int startVertex) {
    struct Queue* q = createQueue();
    int visited[V] = {0};
    
    visited[startVertex] = 1;
    enqueue(q, startVertex);
    
    printf("BFS traversal: ");
    while(!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);
        
        for(int i = 0; i < V; i++) {
            if(graph-> adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
}

int main() {
    struct Graph* graph = malloc(sizeof(struct Graph));
    
    // Initialize adjacency matrix
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            graph-> adjMatrix[i][j] = 0;
        }
    }
    
    // Add edges
    graph-> adjMatrix[0][1] = 1;
    graph-> adjMatrix[0][4] = 1;
    graph-> adjMatrix[1][0] = 1;
    graph-> adjMatrix[1][2] = 1;
    graph-> adjMatrix[1][3] = 1;
    graph-> adjMatrix[1][4] = 1;
    graph-> adjMatrix[2][1] = 1;
    graph-> adjMatrix[2][3] = 1;
    graph-> adjMatrix[3][1] = 1;
    graph-> adjMatrix[3][2] = 1;
    graph-> adjMatrix[3][4] = 1;
    graph-> adjMatrix[4][0] = 1;
    graph-> adjMatrix[4][1] = 1;
    graph-> adjMatrix[4][3] = 1;
    
    bfs(graph, 0);
    return 0;
}

BFS traversal: 0 1 4 2 3

2. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack data structure (often implemented via recursion).

DFS Implementation in C

#include <stdio.h>
#include <stdlib.h>
#define V 5

// Graph structure
struct Graph {
    int adjMatrix[V][V];
};

// DFS utility function
void dfsUtil(struct Graph* graph, int vertex, int visited[V]) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    
    for(int i = 0; i < V; i++) {
        if(graph-> adjMatrix[vertex][i] == 1 && !visited[i]) {
            dfsUtil(graph, i, visited);
        }
    }
}

// DFS function
void dfs(struct Graph* graph, int startVertex) {
    int visited[V] = {0};
    printf("DFS traversal: ");
    dfsUtil(graph, startVertex, visited);
}

int main() {
    struct Graph* graph = malloc(sizeof(struct Graph));
    
    // Initialize adjacency matrix
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            graph-> adjMatrix[i][j] = 0;
        }
    }
    
    // Add edges
    graph-> adjMatrix[0][1] = 1;
    graph-> adjMatrix[0][4] = 1;
    graph-> adjMatrix[1][0] = 1;
    graph-> adjMatrix[1][2] = 1;
    graph-> adjMatrix[1][3] = 1;
    graph-> adjMatrix[1][4] = 1;
    graph-> adjMatrix[2][1] = 1;
    graph-> adjMatrix[2][3] = 1;
    graph-> adjMatrix[3][1] = 1;
    graph-> adjMatrix[3][2] = 1;
    graph-> adjMatrix[3][4] = 1;
    graph-> adjMatrix[4][0] = 1;
    graph-> adjMatrix[4][1] = 1;
    graph-> adjMatrix[4][3] = 1;
    
    dfs(graph, 0);
    return 0;
}

DFS traversal: 0 1 2 3 4

Applications of Graphs

Graphs have numerous real-world applications across various domains:

• Social Networks: Friend connections (vertices are people, edges are relationships)
• Transportation Networks: Roads, flights, or public transport systems
• Web Crawling: Web pages as vertices and hyperlinks as edges
• Recommendation Systems: Product or content recommendations based on connections
• Computer Networks: Modeling network topology and routing
• Dependency Resolution: Package managers resolving software dependencies

Conclusion

Graphs are fundamental data structures that model relationships between entities. Understanding graph representations (adjacency matrix and adjacency list) and traversal algorithms (BFS and DFS) provides a strong foundation for solving complex problems in computer science. The C implementations shown here demonstrate how these concepts can be practically applied. Whether you're developing the next social network app or optimizing delivery routes, graph algorithms will likely be part of your solution toolkit.

As you continue your journey with graphs, explore more advanced algorithms like Dijkstra's shortest path, Prim's and Kruskal's minimum spanning trees, and topological sorting. Each builds upon these fundamental concepts we've covered today.