Graph in C - Data Structure Tutorial

Graph Definitions & Terminologies

A graph G = (V, E) consists of a set of vertices (V) and a set of edges (E) that connect pairs of vertices.

Basic Terminologies

Term	Definition
Vertex (Node)	Fundamental unit of a graph representing an entity (e.g., city, person)
Edge (Arc)	Connection between two vertices representing relationship
Directed Graph	Edges have direction (u → v is different from v → u)
Undirected Graph	Edges have no direction (u-v is same as v-u)
Weighted Graph	Edges have associated weights/costs (distance, time, cost)
Unweighted Graph	All edges have same weight (usually 1)
Degree	Number of edges connected to a vertex
In-degree	Number of edges entering a vertex (directed graph)
Out-degree	Number of edges leaving a vertex (directed graph)
Path	Sequence of vertices connected by edges
Cycle	Path that starts and ends at same vertex
Connected Graph	Path exists between every pair of vertices
Connected Component	Maximal set of connected vertices

Graph Visualizations

📊 Undirected Graph

    (0)-------(1)
     |         |
     |    (4)  |
     |   /   \ |
    (2)-------(3)

Edges: {(0,1), (0,2), (1,3), (2,3), (2,4), (3,4)}
Degree of vertex 2: 3 (connected to 0, 3, 4)

📊 Directed Graph

    (0) ----> (1)
     |         |
     |         v
     v        (3)
    (2) <-----

Edges: {(0,1), (0,2), (1,3), (3,2)}
In-degree of vertex 2: 2  (from 0 and 3)
Out-degree of vertex 0: 2  (to 1 and 2)

📊 Weighted Graph

         4
    (A)-------(B)
     |         |
   2 |         | 1
     |    3    |
    (C)-------(D)

Edge (A,B) weight = 4, Edge (C,D) weight = 3

Graph Representations

1. Adjacency Matrix

A 2D array where matrix[i][j] = 1 (or weight) if edge exists from vertex i to j.

📊 Example: Undirected Graph

    Graph:          Adjacency Matrix:
    (0)---(1)       
     |     |          | 0 | 1 | 2 | 3 |
    (2)---(3)      ---+---+---+---+---+
                     0 | 0 | 1 | 1 | 0 |
                     1 | 1 | 0 | 0 | 1 |
                     2 | 1 | 0 | 0 | 1 |
                     3 | 0 | 1 | 1 | 0 |

📊 Example: Directed Graph

    Graph:          Adjacency Matrix:
    (0)--->(1)      
     |      |       | 0 | 1 | 2 | 3 |
     v      v     ---+---+---+---+---+
    (2)<---(3)      0 | 0 | 1 | 1 | 0 |
                     1 | 0 | 0 | 0 | 1 |
                     2 | 0 | 0 | 0 | 0 |
                     3 | 0 | 0 | 1 | 0 |

adjacency_matrix.c

#include <stdio.h>
#include <stdbool.h>
#define MAX 100

typedef struct {
    int matrix[MAX][MAX];
    int vertices;
    bool directed;
    bool weighted;
} Graph;

// Initialize graph with 0 edges
void initGraph(Graph* g, int v, bool directed, bool weighted) {
    g->vertices = v;
    g->directed = directed;
    g->weighted = weighted;
    for (int i = 0; i < v; i++)
        for (int j = 0; j < v; j++)
            g->matrix[i][j] = 0;
}

// Add edge
void addEdge(Graph* g, int u, int v, int weight) {
    if (g->weighted)
        g->matrix[u][v] = weight;
    else
        g->matrix[u][v] = 1;
    
    // For undirected graph
    if (!g->directed) {
        if (g->weighted)
            g->matrix[v][u] = weight;
        else
            g->matrix[v][u] = 1;
    }
}

// Display adjacency matrix
void displayMatrix(Graph* g) {
    printf("\nAdjacency Matrix:\n   ");
    for (int i = 0; i < g->vertices; i++)
        printf("%3d", i);
    printf("\n");
    
    for (int i = 0; i < g->vertices; i++) {
        printf("%2d ", i);
        for (int j = 0; j < g->vertices; j++)
            printf("%3d", g->matrix[i][j]);
        printf("\n");
    }
}

// Calculate degree (for undirected)
int getDegree(Graph* g, int v) {
    int degree = 0;
    for (int i = 0; i < g->vertices; i++)
        if (g->matrix[v][i] != 0)
            degree++;
    return degree;
}

// Calculate in-degree (for directed)
int getInDegree(Graph* g, int v) {
    int inDegree = 0;
    for (int i = 0; i < g->vertices; i++)
        if (g->matrix[i][v] != 0)
            inDegree++;
    return inDegree;
}

// Calculate out-degree (for directed)
int getOutDegree(Graph* g, int v) {
    int outDegree = 0;
    for (int i = 0; i < g->vertices; i++)
        if (g->matrix[v][i] != 0)
            outDegree++;
    return outDegree;
}

int main() {
    Graph g;
    int v, e, u, w, weight;
    
    printf("Enter number of vertices: ");
    scanf("%d", &v);
    
    initGraph(&g, v, false, false);  // undirected, unweighted
    
    printf("Enter number of edges: ");
    scanf("%d", &e);
    
    printf("Enter edges (u v):\n");
    for (int i = 0; i < e; i++) {
        scanf("%d %d", &u, &w);
        addEdge(&g, u, w, 1);
    }
    
    displayMatrix(&g);
    
    printf("\nDegrees of vertices:\n");
    for (int i = 0; i < v; i++)
        printf("Vertex %d: degree = %d\n", i, getDegree(&g, i));
    
    return 0;
}

2. Adjacency List - Detailed Explanation

🤔 What is an Adjacency List?

An Adjacency List is a way to represent a graph using a collection of linked lists. Think of it as:

An array of size V (where V = number of vertices)
Each index i in the array represents vertex i
The linked list at index i contains all vertices that are directly connected to vertex i

💡 Why Use Adjacency List?

Memory Efficient: Only stores actual edges (O(V + E) space vs O(V²) for matrix)
Fast Neighbor Access: Get all neighbors of a vertex in O(degree) time
Easy to Add Edges: Just insert a new node at the head of the list
Perfect for Sparse Graphs: Graphs with few edges (like real-world social networks)

📊 Visual Example - Building an Adjacency List Step by Step

Step 1: Start with an Empty Graph

Graph has 4 vertices: 0, 1, 2, 3

Initially, all adjacency lists are empty:

Index:    0      1      2      3
         ↓      ↓      ↓      ↓
       NULL   NULL   NULL   NULL

Step 2: Add Edge (0, 1) - Connects vertex 0 to vertex 1

Graph:              Adjacency List:
(0)---(1)           
                    Index 0:  1 → NULL    (0 is connected to 1)
                    Index 1:  0 → NULL    (1 is connected to 0)
                    Index 2:  NULL
                    Index 3:  NULL
                    
Explanation: For undirected graph, edge (0,1) means:
- Add 1 to the list of vertex 0
- Add 0 to the list of vertex 1

Step 3: Add Edge (0, 2) - Connects vertex 0 to vertex 2

Graph:              Adjacency List:
(0)---(1)
 |                  Index 0:  2 → 1 → NULL   (New node 2 added at HEAD)
 |                  Index 1:  0 → NULL
(2)                Index 2:  0 → NULL       (0 added to vertex 2's list)
                    Index 3:  NULL
                    
Note: New nodes are typically added at the HEAD (beginning) of the list
because it's O(1) operation. We don't need to traverse to the end.

Step 4: Add Edge (1, 3) - Connects vertex 1 to vertex 3

Graph:              Adjacency List:
(0)---(1)
 |      |           Index 0:  2 → 1 → NULL
 |      |           Index 1:  3 → 0 → NULL   (3 added at HEAD)
(2)   (3)           Index 2:  0 → NULL
                    Index 3:  1 → NULL       (1 added to vertex 3's list)

Step 5: Add Edge (2, 3) - Final Graph

Complete Graph:      Complete Adjacency List:
    (0)---(1)
     |     |          Index 0:  2 → 1 → NULL
     |     |          Index 1:  3 → 0 → NULL
    (2)---(3)          Index 2:  3 → 0 → NULL
                       Index 3:  2 → 1 → NULL

How to read this:
- Vertex 0 is connected to: 2, 1
- Vertex 1 is connected to: 3, 0
- Vertex 2 is connected to: 3, 0
- Vertex 3 is connected to: 2, 1

🎯 How to Find if Two Vertices are Connected?

To check if vertex u and v are connected:

Go to adjacency list of vertex u (index u in the array)
Traverse the linked list
Look for vertex v in the list
If found, they're connected; otherwise, they're not

Example: Are vertex 0 and 3 connected?

Look at Index 0's list:  2 → 1 → NULL
Traverse: 2 (not 3) → 1 (not 3) → NULL (end)
Result: NOT connected directly!

But wait, they ARE connected through: 0 → 2 → 3 (path of length 2)

📐 Memory Layout in C

In Memory (Conceptual View):

Array (adjList):    [0]       [1]       [2]       [3]
                     ↓         ↓         ↓         ↓
                   Node     Node     Node     Node
                   addr     addr     addr     addr
                     ↓         ↓         ↓         ↓
                   +---+     +---+     +---+     +---+
                   | 2 |     | 3 |     | 3 |     | 2 |
                   |next|→   |next|→   |next|→   |next|→
                   +---+     +---+     +---+     +---+
                     ↓         ↓         ↓         ↓
                   +---+     +---+     +---+     +---+
                   | 1 |     | 0 |     | 0 |     | 1 |
                   |NULL     |NULL     |NULL     |NULL
                   +---+     +---+     +---+     +---+

🔧 Structure in C Code

// Node represents ONE neighbor connection
typedef struct Node {
    int vertex;           // Which vertex this node connects TO
    int weight;           // Weight of edge (for weighted graphs)
    struct Node* next;    // Pointer to next neighbor
} Node;

// Graph contains array of adjacency lists
typedef struct {
    Node* adjList[100];   // Array of pointers to linked lists
    int vertices;         // Number of vertices
    bool directed;        // true = directed, false = undirected
    bool weighted;        // true = weighted, false = unweighted
} Graph;

// adjList[i] points to the head of the linked list for vertex i

📊 Example: Directed Graph Adjacency List

For directed graphs, we only add in ONE direction:

Directed Graph:         Adjacency List:
    (0) ---> (1)       
     |         |        Index 0:  2 → 1 → NULL   (0 points to 2 and 1)
     |         |        Index 1:  3 → NULL       (1 points to 3)
     v         v        Index 2:  NULL            (2 points nowhere)
    (2)      (3)        Index 3:  2 → NULL       (3 points to 2)
    
    Edges: (0,2), (0,1), (1,3), (3,2)
    
    Note: No back-pointers needed! Edge (0,1) ≠ edge (1,0)

📊 Example: Weighted Graph Adjacency List

For weighted graphs, each node stores the weight:

Weighted Graph:         Adjacency List (vertex, weight):
         4
    (A)-------(B)       Index 0 (A):  (1,4) → (2,2) → NULL
     |       /         Index 1 (B):  (0,4) → (3,1) → NULL
   2 |     /1          Index 2 (C):  (0,2) → (3,5) → NULL
     |   /             Index 3 (D):  (1,1) → (2,5) → NULL
    (C)-------(D)
         5
    
    Reading: A connected to B(weight 4), C(weight 2)

adjacency_list.c

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

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

// Graph structure
typedef struct {
    Node* adjList[100];
    int vertices;
    bool directed;
    bool weighted;
} Graph;

// Create new node
Node* createNode(int v, int w) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->weight = w;
    newNode->next = NULL;
    return newNode;
}

// Initialize graph
void initGraph(Graph* g, int v, bool directed, bool weighted) {
    g->vertices = v;
    g->directed = directed;
    g->weighted = weighted;
    for (int i = 0; i < v; i++)
        g->adjList[i] = NULL;
}

// Add edge
void addEdge(Graph* g, int u, int v, int weight) {
    // Add edge u -> v
    Node* newNode = createNode(v, weight);
    newNode->next = g->adjList[u];
    g->adjList[u] = newNode;
    
    // For undirected graph, add edge v -> u
    if (!g->directed) {
        newNode = createNode(u, weight);
        newNode->next = g->adjList[v];
        g->adjList[v] = newNode;
    }
}

// Display adjacency list
void displayList(Graph* g) {
    printf("\nAdjacency List:\n");
    for (int i = 0; i < g->vertices; i++) {
        printf("Vertex %d: ", i);
        Node* temp = g->adjList[i];
        while (temp != NULL) {
            if (g->weighted)
                printf("(%d,%d) ", temp->vertex, temp->weight);
            else
                printf("%d ", temp->vertex);
            temp = temp->next;
        }
        printf("-> NULL\n");
    }
}

// Get degree of vertex (for undirected)
int getDegree(Graph* g, int v) {
    int degree = 0;
    Node* temp = g->adjList[v];
    while (temp != NULL) {
        degree++;
        temp = temp->next;
    }
    return degree;
}

int main() {
    Graph g;
    int v, e, u, w, weight;
    
    printf("Enter number of vertices: ");
    scanf("%d", &v);
    
    initGraph(&g, v, false, false);
    
    printf("Enter number of edges: ");
    scanf("%d", &e);
    
    printf("Enter edges (u v):\n");
    for (int i = 0; i < e; i++) {
        scanf("%d %d", &u, &w);
        addEdge(&g, u, w, 1);
    }
    
    displayList(&g);
    
    return 0;
}

Comparison: Adjacency Matrix vs Adjacency List

Operation	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Add Edge	O(1)	O(1)
Remove Edge	O(1)	O(E)
Check Edge	O(1)	O(V)
Get All Neighbors	O(V)	O(degree(v))
Best For	Dense graphs	Sparse graphs

Graph Traversals

1. Breadth First Search (BFS)

BFS explores vertices level by level, visiting all neighbors of a vertex before moving to next level. Uses a queue data structure.

🔄 BFS Algorithm

Start from source vertex, mark it visited
Enqueue the source vertex
While queue is not empty:
- Dequeue a vertex u
- For each unvisited neighbor v of u:
  - Mark v as visited
  - Enqueue v

📊 BFS Step-by-Step Example

    Graph:              BFS starting from vertex 0:
    (0)---(1)
     |     |           Step | Vertex | Queue    | Visited
     |     |           -----+--------+----------+------------
    (2)---(3)            1  |   0    | [0]      | {0}
                         2  |   0    | [1,2]    | {0,1,2}
                         3  |   1    | [2,3]    | {0,1,2,3}
                         4  |   2    | [3]      | {0,1,2,3}
                         5  |   3    | []       | {0,1,2,3}
    
    BFS Traversal: 0 → 1 → 2 → 3

bfs_traversal.c

#include <stdio.h>
#include <stdbool.h>
#define MAX 100

// Queue implementation for BFS
typedef struct {
    int items[MAX];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

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

void enqueue(Queue* q, int value) {
    if (q->rear == MAX - 1) return;
    if (q->front == -1) q->front = 0;
    q->items[++q->rear] = value;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) return -1;
    int item = q->items[q->front];
    if (q->front >= q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

// Graph with adjacency matrix
typedef struct {
    int adj[MAX][MAX];
    int vertices;
} Graph;

void initGraph(Graph* g, int v) {
    g->vertices = v;
    for (int i = 0; i < v; i++)
        for (int j = 0; j < v; j++)
            g->adj[i][j] = 0;
}

void addEdge(Graph* g, int u, int v) {
    g->adj[u][v] = 1;
    g->adj[v][u] = 1;  // Undirected
}

// BFS Traversal
void BFS(Graph* g, int start) {
    bool visited[MAX] = {false};
    Queue q;
    initQueue(&q);
    
    printf("BFS Traversal: ");
    
    // Mark start as visited and enqueue
    visited[start] = true;
    enqueue(&q, start);
    
    while (!isEmpty(&q)) {
        int current = dequeue(&q);
        printf("%d ", current);
        
        // Visit all unvisited neighbors
        for (int i = 0; i < g->vertices; i++) {
            if (g->adj[current][i] == 1 && !visited[i]) {
                visited[i] = true;
                enqueue(&q, i);
            }
        }
    }
    printf("\n");
}

int main() {
    Graph g;
    int v = 5;
    
    initGraph(&g, v);
    
    // Add edges
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    addEdge(&g, 2, 4);
    
    BFS(&g, 0);  // Output: 0 1 2 3 4
    
    return 0;
}

2. Depth First Search (DFS)

DFS explores as far as possible along each branch before backtracking. Uses a stack (or recursion).

🔄 DFS Algorithm (Recursive)

Mark current vertex as visited
Print/Process the vertex
For each unvisited neighbor:
- Recursively call DFS on the neighbor

📊 DFS Step-by-Step Example

    Graph:              DFS starting from vertex 0:
    (0)---(1)
     |     |           Step | Vertex | Stack    | Action
     |     |           -----+--------+----------+------------------
    (2)---(3)            1  |   0    | [0]      | Push 0
                         2  |   0    | [0,1]    | Push neighbor 1
                         3  |   1    | [0,1,3]  | Push neighbor 3
                         4  |   3    | [0,1,3]  | No unvisited
                         5  |   1    | [0,1]    | Pop 3
                         6  |   0    | [0]      | Pop 1
                         7  |   0    | [0,2]    | Push neighbor 2
                         8  |   2    | [0,2]    | No unvisited
    
    DFS Traversal: 0 → 1 → 3 → 2

dfs_traversal.c

#include <stdio.h>
#include <stdbool.h>
#define MAX 100

// Graph with adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* adjList[MAX];
    int vertices;
} Graph;

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

void initGraph(Graph* g, int v) {
    g->vertices = v;
    for (int i = 0; i < v; i++)
        g->adjList[i] = NULL;
}

void addEdge(Graph* g, int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = g->adjList[u];
    g->adjList[u] = newNode;
    
    newNode = createNode(u);  // Undirected
    newNode->next = g->adjList[v];
    g->adjList[v] = newNode;
}

// DFS Recursive
void DFSRecursive(Graph* g, int vertex, bool visited[]) {
    visited[vertex] = true;
    printf("%d ", vertex);
    
    Node* temp = g->adjList[vertex];
    while (temp != NULL) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            DFSRecursive(g, adjVertex, visited);
        }
        temp = temp->next;
    }
}

// DFS using explicit stack
void DFSIterative(Graph* g, int start) {
    bool visited[MAX] = {false};
    int stack[MAX];
    int top = -1;
    
    printf("DFS Iterative: ");
    
    // Push start vertex
    stack[++top] = start;
    
    while (top >= 0) {
        int current = stack[top--];
        
        if (!visited[current]) {
            visited[current] = true;
            printf("%d ", current);
            
            // Push all unvisited neighbors
            Node* temp = g->adjList[current];
            while (temp != NULL) {
                int adjVertex = temp->vertex;
                if (!visited[adjVertex]) {
                    stack[++top] = adjVertex;
                }
                temp = temp->next;
            }
        }
    }
    printf("\n");
}

void DFS(Graph* g, int start) {
    bool visited[MAX] = {false};
    printf("DFS Recursive: ");
    DFSRecursive(g, start, visited);
    printf("\n");
}

int main() {
    Graph g;
    int v = 5;
    
    initGraph(&g, v);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    
    DFS(&g, 0);
    DFSIterative(&g, 0);
    
    return 0;
}

BFS vs DFS Comparison

Aspect	BFS	DFS
Data Structure	Queue	Stack (or recursion)
Time Complexity	O(V + E)	O(V + E)
Space Complexity	O(V)	O(V)
Approach	Level by level	Deep exploration
Shortest Path	Finds in unweighted graphs	May not find shortest
Use Case	Shortest path, level-order	Path finding, topological sort

Spanning Trees

📐 Definition

A Spanning Tree of a connected, undirected graph is a subgraph that:

Contains all vertices of the original graph
Contains exactly (V - 1) edges
Is connected and acyclic (forms a tree)

Properties of Spanning Trees

Property	Description
Number of edges	Exactly V - 1 edges
Connectivity	Path exists between every pair of vertices
Acyclic	No cycles present
Spanning trees count	A complete graph with n vertices has n^(n-2) spanning trees (Cayley's formula)

📊 Spanning Tree Example

    Original Graph:          Possible Spanning Tree:
    
    (0)---(1)                (0)---(1)
     |\   /|                       |
     | \ / |                      (2)
     |  X  |                       \
    (2)---(3)                      (3)
    
    Vertices: 4, Edges in MST: 3
    (One of several possible spanning trees)

Minimum Spanning Tree (MST)

A Minimum Spanning Tree is a spanning tree with minimum total edge weight. Used in network design, clustering, etc.

1. Prim's Algorithm

Grows MST by adding the minimum weight edge that connects a vertex in MST to a vertex outside MST.

🔄 Prim's Algorithm Steps

Start with any vertex as part of MST
Find the minimum weight edge connecting MST to outside vertices
Add that edge and vertex to MST
Repeat until all vertices are included

📊 Prim's Algorithm Step-by-Step

    Weighted Graph:
         2
    (0)-------(1)
     |       / |
   4 |    1/  | 3
     |    /   |
    (2)-------(3)
         5
    
    Step-by-Step Execution:
    
    Step | MST Vertices | Edge Selected | Weight | Total Weight
    -----+--------------+---------------+--------+-------------
     1   | {0}          | (0,1)=2       | 2      | 2
     2   | {0,1}        | (1,3)=3       | 3      | 5
     3   | {0,1,3}      | (0,2)=4       | 4      | 9
     
    MST Edges: (0,1), (1,3), (0,2)
    Total Weight: 9

prims_algorithm.c

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5

// Find vertex with minimum key value
int minKey(int key[], bool mstSet[], int vertices) {
    int min = INT_MAX, minIndex;
    
    for (int v = 0; v < vertices; v++)
        if (!mstSet[v] && key[v] < min)
            min = key[v], minIndex = v;
    
    return minIndex;
}

// Print MST
void printMST(int parent[], int graph[V][V], int vertices) {
    printf("Edge\tWeight\n");
    int totalWeight = 0;
    for (int i = 1; i < vertices; i++) {
        printf("%d - %d\t%d\n", parent[i], i, graph[i][parent[i]]);
        totalWeight += graph[i][parent[i]];
    }
    printf("Total MST Weight: %d\n", totalWeight);
}

// Prim's Algorithm
void primMST(int graph[V][V], int vertices) {
    int parent[V];      // Store MST
    int key[V];         // Key values for min edge weight
    bool mstSet[V];     // Track vertices in MST
    
    // Initialize
    for (int i = 0; i < vertices; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }
    
    // Start from vertex 0
    key[0] = 0;
    parent[0] = -1;  // Root has no parent
    
    for (int count = 0; count < vertices - 1; count++) {
        // Pick min key vertex not in MST
        int u = minKey(key, mstSet, vertices);
        mstSet[u] = true;
        
        // Update key values of adjacent vertices
        for (int v = 0; v < vertices; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    
    printMST(parent, graph, vertices);
}

// Priority Queue optimized version
typedef struct {
    int vertex;
    int key;
} MinHeapNode;

typedef struct {
    MinHeapNode* array;
    int size;
    int capacity;
    int* pos;  // Position of vertex in heap
} MinHeap;

MinHeap* createMinHeap(int capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->pos = (int*)malloc(capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (MinHeapNode*)malloc(capacity * sizeof(MinHeapNode));
    return minHeap;
}

int main() {
    int graph[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };
    
    printf("Prim's MST:\n");
    primMST(graph, V);
    
    return 0;
}

2. Kruskal's Algorithm

Sorts all edges by weight and adds them to MST if they don't form a cycle. Uses Union-Find data structure.

🔄 Kruskal's Algorithm Steps

Sort all edges in non-decreasing order of weight
Initialize each vertex as its own component (Disjoint Set)
For each edge (u, v):
- If u and v are in different components:
  - Add edge to MST
  - Union the components
Stop when V-1 edges are added

📊 Kruskal's Algorithm Step-by-Step

    Weighted Graph:
         2
    (0)-------(1)
     |       / |
   4 |    1/  | 3
     |    /   |
    (2)-------(3)
         5
    
    Sorted Edges: (1,2)=1, (0,1)=2, (1,3)=3, (0,2)=4, (2,3)=5
    
    Step | Edge   | Weight | Components      | Action
    -----+--------+--------+-----------------+----------------
     1   | (1,2)  | 1      | {0},{1,2},{3}   | Add (no cycle)
     2   | (0,1)  | 2      | {0,1,2},{3}     | Add (no cycle)
     3   | (1,3)  | 3      | {0,1,2,3}       | Add (no cycle)
     4   | (0,2)  | 4      | {0,1,2,3}       | Skip (cycle!)
     5   | (2,3)  | 5      | {0,1,2,3}       | Skip (cycle!)
     
    MST Edges: (1,2), (0,1), (1,3)
    Total Weight: 6

kruskals_algorithm.c

#include <stdio.h>
#include <stdlib.h>
#define MAX_EDGES 100
#define MAX_VERTICES 100

// Edge structure
typedef struct {
    int u, v, weight;
} Edge;

// Union-Find (Disjoint Set) structure
typedef struct {
    int parent[MAX_VERTICES];
    int rank[MAX_VERTICES];
} DisjointSet;

// Initialize disjoint set
void makeSet(DisjointSet* ds, int n) {
    for (int i = 0; i < n; i++) {
        ds->parent[i] = i;
        ds->rank[i] = 0;
    }
}

// Find with path compression
int find(DisjointSet* ds, int x) {
    if (ds->parent[x] != x)
        ds->parent[x] = find(ds, ds->parent[x]);
    return ds->parent[x];
}

// Union by rank
void unionSets(DisjointSet* ds, int x, int y) {
    int xRoot = find(ds, x);
    int yRoot = find(ds, y);
    
    if (xRoot == yRoot) return;
    
    if (ds->rank[xRoot] < ds->rank[yRoot])
        ds->parent[xRoot] = yRoot;
    else if (ds->rank[xRoot] > ds->rank[yRoot])
        ds->parent[yRoot] = xRoot;
    else {
        ds->parent[yRoot] = xRoot;
        ds->rank[xRoot]++;
    }
}

// Compare edges for sorting
int compareEdges(const void* a, const void* b) {
    Edge* e1 = (Edge*)a;
    Edge* e2 = (Edge*)b;
    return e1->weight - e2->weight;
}

// Kruskal's Algorithm
void kruskalMST(Edge edges[], int numEdges, int numVertices) {
    // Sort edges by weight
    qsort(edges, numEdges, sizeof(Edge), compareEdges);
    
    DisjointSet ds;
    makeSet(&ds, numVertices);
    
    Edge mst[MAX_EDGES];
    int mstSize = 0;
    int totalWeight = 0;
    
    printf("Kruskal's MST:\n");
    printf("Edge\tWeight\n");
    
    for (int i = 0; i < numEdges && mstSize < numVertices - 1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].weight;
        
        // Check if adding this edge creates cycle
        if (find(&ds, u) != find(&ds, v)) {
            mst[mstSize++] = edges[i];
            totalWeight += w;
            unionSets(&ds, u, v);
            printf("%d - %d\t%d\n", u, v, w);
        }
    }
    
    printf("Total MST Weight: %d\n", totalWeight);
}

int main() {
    int numVertices = 4;
    Edge edges[] = {
        {0, 1, 2},
        {0, 2, 4},
        {1, 2, 1},
        {1, 3, 3},
        {2, 3, 5}
    };
    int numEdges = 5;
    
    kruskalMST(edges, numEdges, numVertices);
    
    return 0;
}

Prim's vs Kruskal's Comparison

Aspect	Prim's Algorithm	Kruskal's Algorithm
Approach	Vertex-based (grow tree)	Edge-based (add edges)
Data Structure	Priority Queue, Adjacency Matrix	Union-Find, Edge List
Time (Array)	O(V²)	O(E log E)
Time (Binary Heap)	O(E log V)	O(E log E)
Best For	Dense graphs	Sparse graphs
Works On	Connected graphs	Disconnected graphs too

Shortest Path Algorithms

Dijkstra's Algorithm

Finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights.

🔄 Dijkstra's Algorithm Steps

Initialize distances: source = 0, all others = ∞
Create a set of unvisited vertices
While unvisited vertices remain:
- Select unvisited vertex with minimum distance
- Mark it as visited
- For each neighbor: update distance if shorter path found

📊 Dijkstra's Step-by-Step Example

    Weighted Graph (Source: 0):
         4
    (0)-------(1)
     |         |
   1 |         | 2
     |    5    |
    (2)-------(3)
    
    Step-by-Step Execution:
    
    Step | Visited | Vertex | Distance from Source
    -----+---------+--------+--------------------
         |         |   0    | 0 (source)
         |         |   1    | ∞
         |         |   2    | ∞
         |         |   3    | ∞
    -----+---------+--------+--------------------
     1   | {0}     |   1    | 4 (via 0)
         |         |   2    | 1 (via 0) ← min
         |         |   3    | ∞
    -----+---------+--------+--------------------
     2   | {0,2}   |   1    | 4 (via 0)
         |         |   3    | 6 (via 2: 1+5)
    -----+---------+--------+--------------------
     3   | {0,2,1} |   3    | 6 (via 2 is shorter)
    
    Final Shortest Distances from 0:
    Vertex 0: 0
    Vertex 1: 4
    Vertex 2: 1
    Vertex 3: 6

dijkstras_algorithm.c

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#define V 6

// Find vertex with minimum distance
int minDistance(int dist[], bool sptSet[], int vertices) {
    int min = INT_MAX, minIndex;
    
    for (int v = 0; v < vertices; v++)
        if (!sptSet[v] && dist[v] <= min)
            min = dist[v], minIndex = v;
    
    return minIndex;
}

// Print shortest distances
void printSolution(int dist[], int parent[], int vertices, int src) {
    printf("Shortest paths from vertex %d:\n", src);
    printf("Vertex\tDistance\tPath\n");
    
    for (int i = 0; i < vertices; i++) {
        if (i != src) {
            printf("%d\t%d\t\t%d", i, dist[i], i);
            int p = parent[i];
            while (p != -1) {
                printf(" <- %d", p);
                p = parent[p];
            }
            printf("\n");
        }
    }
}

// Dijkstra's Algorithm
void dijkstra(int graph[V][V], int src, int vertices) {
    int dist[V];     // Shortest distances
    bool sptSet[V];  // Shortest path tree set
    int parent[V];   // To reconstruct path
    
    // Initialize
    for (int i = 0; i < vertices; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
        parent[i] = -1;
    }
    
    dist[src] = 0;
    
    // Find shortest path for all vertices
    for (int count = 0; count < vertices - 1; count++) {
        // Pick minimum distance vertex
        int u = minDistance(dist, sptSet, vertices);
        sptSet[u] = true;
        
        // Update distances of adjacent vertices
        for (int v = 0; v < vertices; v++) {
            if (!sptSet[v] && graph[u][v] && 
                dist[u] != INT_MAX && 
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;
            }
        }
    }
    
    printSolution(dist, parent, vertices, src);
}

// Priority Queue implementation for optimization
typedef struct {
    int vertex;
    int dist;
} PQNode;

typedef struct {
    PQNode* nodes;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createPQ(int capacity) {
    PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->nodes = (PQNode*)malloc(capacity * sizeof(PQNode));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void swap(PQNode* a, PQNode* b) {
    PQNode temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(PriorityQueue* pq, int idx) {
    while (idx > 0 && pq->nodes[(idx-1)/2].dist > pq->nodes[idx].dist) {
        swap(&pq->nodes[(idx-1)/2], &pq->nodes[idx]);
        idx = (idx-1)/2;
    }
}

void push(PriorityQueue* pq, int vertex, int dist) {
    pq->nodes[pq->size].vertex = vertex;
    pq->nodes[pq->size].dist = dist;
    heapifyUp(pq, pq->size);
    pq->size++;
}

PQNode pop(PriorityQueue* pq) {
    PQNode min = pq->nodes[0];
    pq->nodes[0] = pq->nodes[--pq->size];
    // Simple heapify down would go here
    return min;
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0},
        {4, 0, 8, 0, 0, 0},
        {0, 8, 0, 7, 0, 4},
        {0, 0, 7, 0, 9, 14},
        {0, 0, 0, 9, 0, 10},
        {0, 0, 4, 14, 10, 0}
    };
    
    dijkstra(graph, 0, V);
    
    return 0;
}

⚠️ Limitations of Dijkstra's Algorithm

Non-negative weights only: Does not work with negative edge weights
Bellman-Ford: Use for graphs with negative weights (but no negative cycles)
Floyd-Warshall: Use for all-pairs shortest paths

Graph Applications

🌐 Social Networks

Users as vertices, friendships as edges. Used for friend recommendations, influence analysis, and community detection.

UserA -- UserB
 |         |
UserC -- UserD

🗺️ Maps & GPS Navigation

Locations as vertices, roads as weighted edges. Shortest path algorithms find optimal routes.

Home --[5km]-- Store
 |              |
[2km]       [3km]
 |              |
Office--[4km]--Park

🌐 Network Routing

Routers as vertices, connections as edges. Algorithms like Dijkstra's find best paths for data packets.

RouterA --> RouterB
   |           |
   v           v
RouterC <-- RouterD

📦 Dependency Resolution

Tasks/packages as vertices, dependencies as edges. Topological sort determines execution order.

Build A
  |
  v
Build B --> Build C
  |
  v
Build D

🕸️ Web Crawling

Web pages as vertices, hyperlinks as edges. BFS/DFS used to discover and index web pages.

⚡ Circuit Design

Electronic components as vertices, connections as edges. Used for circuit analysis and optimization.

🔍 Recommendation Systems

Users and items as vertices, interactions as edges. Collaborative filtering uses graph algorithms.

🧬 Biological Networks

Proteins/genes as vertices, interactions as edges. Used in bioinformatics and drug discovery.

Complexity Analysis

Graph Representation Complexity

Operation	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Add Edge	O(1)	O(1)
Remove Edge	O(1)	O(V)
Check Edge Exists	O(1)	O(V)
Get All Neighbors	O(V)	O(degree(v))

Algorithm Complexity

Algorithm	Time Complexity	Space Complexity
BFS	O(V + E)	O(V)
DFS	O(V + E)	O(V)
Prim's (Array)	O(V²)	O(V²)
Prim's (Binary Heap)	O(E log V)	O(V)
Kruskal's	O(E log E)	O(V)
Dijkstra's (Array)	O(V²)	O(V)
Dijkstra's (Binary Heap)	O(E log V)	O(V)

Summary Table

Topic	Key Concept	Time Complexity	Use Case
Adjacency Matrix	2D array representation	O(1) edge check	Dense graphs
Adjacency List	Linked list per vertex	O(degree) traversal	Sparse graphs
BFS	Level-order traversal using queue	O(V + E)	Shortest path (unweighted)
DFS	Depth-first using stack/recursion	O(V + E)	Path finding, cycle detection
Spanning Tree	Tree covering all vertices	-	Network design
Prim's Algorithm	Grow MST from starting vertex	O(E log V)	MST for dense graphs
Kruskal's Algorithm	Add edges in sorted order	O(E log E)	MST for sparse graphs
Dijkstra's Algorithm	Greedy shortest path	O(E log V)	Single-source shortest path