DSA Tutorial

🛠️ Graph Implementation in C (DSA)

Graphs can be implemented using two main techniques: Adjacency Matrix and Adjacency List. Both have their own pros and cons depending on the structure and size of the graph.

📋 1. Adjacency Matrix

This method uses a 2D array to represent edges between every pair of vertices. Easy to implement but consumes more space for sparse graphs.

#include <stdio.h>
#define V 5

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

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

    return 0;
}
  

🔗 2. Adjacency List

Uses an array of linked lists. Each index represents a vertex, and its list contains all connected vertices. Very efficient for sparse graphs.

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

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

struct Graph {
    int V;
    struct Node** adjList;
};

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

struct Graph* createGraph(int V) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjList = malloc(V * sizeof(struct Node*));

    for (int i = 0; i < V; i++)
        graph->adjList[i] = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    newNode = createNode(src); // Undirected Graph
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        struct Node* temp = graph->adjList[v];
        printf("Vertex %d:", v);
        while (temp) {
            printf(" → %d", temp->dest);
            temp = temp->next;
        }
        printf("\\n");
    }
}

int main() {
    int V = 5;
    struct 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;
}
  

🧪 Which One to Use?

• Adjacency Matrix → Use when graph is dense or quick edge lookup is needed
• Adjacency List → Use when graph is sparse and memory is limited

📌 Common Operations

• Add Vertex
• Add Edge
• Delete Edge
• Check Connection
• Graph Traversals (DFS, BFS)