DSA Tutorial

🌐 Graphs in Data Structures

A graph is a collection of nodes (vertices) connected by edges. It’s used to model networks like roads, social media, or even internet structure.

🎨 Visualization

Example graph with nodes A, B, C, D, and E:

      A
     / \
    B   C
     \ / 
      D
      |
      E
  

🧩 Types of Graphs

• Directed Graph (Digraph) ➝ A → B
• Undirected Graph ➝ A — B
• Weighted Graph ➝ Edges have cost (e.g. A -5→ B)
• Unweighted Graph ➝ Edges have no cost
• Cyclic / Acyclic
• Connected / Disconnected

📦 Graph Representation in C

1. Adjacency Matrix

#include <stdio.h>

#define V 5

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 0},
        {1, 0, 0, 1, 0},
        {0, 1, 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

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

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

void addEdge(struct Node* adjList[], int u, int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = v;
    newNode->next = adjList[u];
    adjList[u] = newNode;
}

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

int main() {
    int V = 5;
    struct Node* adjList[5] = {NULL};

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

    printGraph(adjList, V);
    return 0;
}
  

🔄 Graph Traversals

To explore nodes in a graph, use:

💻 BFS in C

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

#define SIZE 100

void bfs(int graph[][SIZE], int start, int n) {
    int visited[SIZE] = {0}, queue[SIZE], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        for (int i = 0; i < n; i++) {
            if (graph[current][i] && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}
  

💻 DFS in C (Recursive)

void dfs(int graph[][SIZE], int vertex, int visited[], int n) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    for (int i = 0; i < n; i++) {
        if (graph[vertex][i] && !visited[i]) {
            dfs(graph, i, visited, n);
        }
    }
}
  

🌐 Applications of Graphs

• 📍 GPS & Maps (Shortest Path)
• 🌐 Internet Network Routing
• 👥 Social Media Recommendations
• 🔐 Access & Permission Control
• 🧬 Biology (Gene & Protein Mapping)