Complete Notes on Graphs

With C Code, Diagrams, Algorithms, and Examples

Complete Notes on Graphs

With C Code, Diagrams, Algorithms, and Examples

Complete Notes on Graphs

With C Code, Diagrams, Algorithms, and Examples

1. Graph Terminology

Term Definition
Graph Collection of vertices (V) and edges (E)
Vertex/Node Entity
Edge Connection between vertices
Directed Graph (Digraph) Edges have direction
Undirected Graph Edges are bidirectional
Weighted Graph Edges have weights/costs
Degree Number of edges connected to a vertex
In-degree / Out-degree For directed graphs
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 connected subgraph
Tree Connected acyclic graph
Spanning Tree Subgraph that is a tree and includes all vertices

2. Graph Representations

A. Adjacency Matrix

2D array adj[V][V]
adj[i][j] = 1 if edge i→j, else 0 (unweighted)
adj[i][j] = weight for weighted

int adj[MAX][MAX];

Pros & Cons

Pros Cons
O(1) edge check O(V²) space
Fast edge addition Not good for sparse graphs

B. Adjacency List

Array of linked lists
head[i] → list of neighbors of vertex i

typedef struct Node {
    int vertex;
    int weight;  // for weighted
    struct Node* next;
} Node;

Node* head[MAX];

Pros & Cons

Pros Cons
O(V + E) space O(degree) edge check
Best for sparse graphs Slower edge lookup

C. Edge List (for Kruskal)

typedef struct {
    int u, v, w;
} Edge;
Edge edges[MAX_EDGES];

3. Graph Traversal

A. Depth-First Search (DFS)

Explore as far as possible along each branch.

Recursive DFS

void DFS(int u) {
    visited[u] = 1;
    printf("%d ", u);
    for (Node* v = head[u]; v != NULL; v = v->next) {
        if (!visited[v->vertex])
            DFS(v->vertex);
    }
}

Applications

  • Cycle detection
  • Topological sort
  • Strongly connected components
  • Path finding

B. Breadth-First Search (BFS)

Explore level by level using queue.

void BFS(int start) {
    Queue q;
    init(&q);
    visited[start] = 1;
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        int u = dequeue(&q);
        printf("%d ", u);
        for (Node* v = head[u]; v != NULL; v = v->next) {
            if (!visited[v->vertex]) {
                visited[v->vertex] = 1;
                enqueue(&q, v->vertex);
            }
        }
    }
}

Applications

  • Shortest path (unweighted)
  • Level order
  • Bipartite check

4. Connected Components

void findComponents() {
    int component = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            component++;
            printf("Component %d: ", component);
            DFS(i);  // or BFS
            printf("\n");
        }
    }
}

5. Spanning Tree

A subgraph that is a tree and connects all vertices.

  • Number of edges = V - 1
  • No cycles

6. Minimum Cost Spanning Tree (MST)

Spanning tree with minimum total edge weight

A. Prim’s Algorithm (Greedy)

Grow MST from a starting vertex
Always pick minimum weight edge connecting a visited to unvisited vertex

Uses Priority Queue (Min-Heap)

void primMST() {
    int parent[V], key[V];
    bool inMST[V];
    PriorityQueue pq;

    for (int i = 0; i < V; i++) {
        key[i] = INF;
        inMST[i] = false;
    }

    key[0] = 0;
    insert(&pq, 0, 0);
    parent[0] = -1;

    while (!isEmpty(&pq)) {
        int u = extractMin(&pq);
        inMST[u] = true;

        for (Node* v = head[u]; v != NULL; v = v->next) {
            int vertex = v->vertex;
            int weight = v->weight;
            if (!inMST[vertex] && weight < key[vertex]) {
                key[vertex] = weight;
                parent[vertex] = u;
                insert(&pq, vertex, weight);
            }
        }
    }

    // Print MST
    for (int i = 1; i < V; i++)
        printf("%d - %d : %d\n", parent[i], i, key[i]);
}

Time: O((V + E) log V)

B. Kruskal’s Algorithm (Greedy + Union-Find)

Sort all edges → Pick smallest edge that doesn’t form cycle

int parent[MAX];

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unionSets(int x, int y) {
    parent[find(x)] = find(y);
}

void kruskalMST(Edge edges[], int E) {
    Edge result[V-1];
    int e = 0, i = 0;

    // Sort edges by weight
    qsort(edges, E, sizeof(Edge), cmp);

    for (int i = 0; i < V; i++) parent[i] = i;

    while (e < V-1 && i < E) {
        Edge next = edges[i++];
        int x = find(next.u);
        int y = find(next.v);
        if (x != y) {
            result[e++] = next;
            unionSets(x, y);
        }
    }

    // Print result
    for (int i = 0; i < e; i++)
        printf("%d - %d : %d\n", result[i].u, result[i].v, result[i].w);
}

Time: O(E log E)

7. Transitive Closure – Warshall’s Algorithm

Find reachability between all pairs
reach[i][j] = 1 if path exists from i to j

void warshall(int reach[V][V]) {
    // Initialize
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            reach[i][j] = adj[i][j];

    // Add vertices as intermediates
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
}

Time: O(V³)
Use: Reachability, dependency graphs

8. Shortest Path

A. Dijkstra’s Algorithm

Single source, non-negative weights

void dijkstra(int src) {
    int dist[V];
    bool visited[V];
    PriorityQueue pq;

    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[src] = 0;
    insert(&pq, src, 0);

    while (!isEmpty(&pq)) {
        int u = extractMin(&pq);
        if (visited[u]) continue;
        visited[u] = true;

        for (Node* v = head[u]; v != NULL; v = v->next) {
            int vertex = v->vertex;
            int weight = v->weight;
            if (!visited[vertex] && dist[u] + weight < dist[vertex]) {
                dist[vertex] = dist[u] + weight;
                insert(&pq, vertex, dist[vertex]);
            }
        }
    }

    // Print distances
    for (int i = 0; i < V; i++)
        printf("Distance to %d: %d\n", i, dist[i]);
}

Time: O((V + E) log V)

9. Comparison Table

Algorithm Use Time Data Structure
DFS Path, cycle O(V+E) Stack
BFS Shortest path O(V+E) Queue
Prim MST O((V+E)logV) Priority Queue
Kruskal MST O(E log E) Union-Find
Warshall All-pairs reachability O(V³) Matrix
Dijkstra Single-source shortest O((V+E)logV) Priority Queue

10. Example Graph

    0 --1--> 1
    |       / \
    4      2   3
    |     /     \
    2 --8--> 3   7
  • Adjacency List:
  • 0: 1(1), 2(4)
  • 1: 2(2), 3(3)
  • 2: 3(8)
  • 3:

11. Practice Problems

  1. Find all connected components
  2. Detect cycle using DFS
  3. Implement topological sort
  4. Find MST cost using Prim/Kruskal
  5. Compute transitive closure
  6. Shortest path from 0 to all
  7. Bipartite check using BFS

12. Key Takeaways

Concept Insight
Adjacency List Best for sparse graphs
BFS Shortest path in unweighted
DFS Cycle, path existence
Prim Grows from vertex
Kruskal Sorts all edges
Warshall All-pairs reachability
Dijkstra Non-negative weights only

End of Notes

Last updated: Nov 12, 2025

Complete Notes on Graphs

With C Code, Diagrams, Algorithms, and Examples

Complete Notes on Graphs

With C Code, Diagrams, Algorithms, and Examples

Complete Notes on Graphs

With C Code, Diagrams, Algorithms, and Examples

1. Graph Terminology

Term Definition
Graph Collection of vertices (V) and edges (E)
Vertex/Node Entity
Edge Connection between vertices
Directed Graph (Digraph) Edges have direction
Undirected Graph Edges are bidirectional
Weighted Graph Edges have weights/costs
Degree Number of edges connected to a vertex
In-degree / Out-degree For directed graphs
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 connected subgraph
Tree Connected acyclic graph
Spanning Tree Subgraph that is a tree and includes all vertices

2. Graph Representations

A. Adjacency Matrix

2D array adj[V][V]
adj[i][j] = 1 if edge i→j, else 0 (unweighted)
adj[i][j] = weight for weighted

int adj[MAX][MAX];

Pros & Cons

Pros Cons
O(1) edge check O(V²) space
Fast edge addition Not good for sparse graphs

B. Adjacency List

Array of linked lists
head[i] → list of neighbors of vertex i

typedef struct Node {
    int vertex;
    int weight;  // for weighted
    struct Node* next;
} Node;

Node* head[MAX];

Pros & Cons

Pros Cons
O(V + E) space O(degree) edge check
Best for sparse graphs Slower edge lookup

C. Edge List (for Kruskal)

typedef struct {
    int u, v, w;
} Edge;
Edge edges[MAX_EDGES];

3. Graph Traversal

A. Depth-First Search (DFS)

Explore as far as possible along each branch.

Recursive DFS

void DFS(int u) {
    visited[u] = 1;
    printf("%d ", u);
    for (Node* v = head[u]; v != NULL; v = v->next) {
        if (!visited[v->vertex])
            DFS(v->vertex);
    }
}

Applications

  • Cycle detection
  • Topological sort
  • Strongly connected components
  • Path finding

B. Breadth-First Search (BFS)

Explore level by level using queue.

void BFS(int start) {
    Queue q;
    init(&q);
    visited[start] = 1;
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        int u = dequeue(&q);
        printf("%d ", u);
        for (Node* v = head[u]; v != NULL; v = v->next) {
            if (!visited[v->vertex]) {
                visited[v->vertex] = 1;
                enqueue(&q, v->vertex);
            }
        }
    }
}

Applications

  • Shortest path (unweighted)
  • Level order
  • Bipartite check

4. Connected Components

void findComponents() {
    int component = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            component++;
            printf("Component %d: ", component);
            DFS(i);  // or BFS
            printf("\n");
        }
    }
}

5. Spanning Tree

A subgraph that is a tree and connects all vertices.

  • Number of edges = V - 1
  • No cycles

6. Minimum Cost Spanning Tree (MST)

Spanning tree with minimum total edge weight

A. Prim’s Algorithm (Greedy)

Grow MST from a starting vertex
Always pick minimum weight edge connecting a visited to unvisited vertex

Uses Priority Queue (Min-Heap)

void primMST() {
    int parent[V], key[V];
    bool inMST[V];
    PriorityQueue pq;

    for (int i = 0; i < V; i++) {
        key[i] = INF;
        inMST[i] = false;
    }

    key[0] = 0;
    insert(&pq, 0, 0);
    parent[0] = -1;

    while (!isEmpty(&pq)) {
        int u = extractMin(&pq);
        inMST[u] = true;

        for (Node* v = head[u]; v != NULL; v = v->next) {
            int vertex = v->vertex;
            int weight = v->weight;
            if (!inMST[vertex] && weight < key[vertex]) {
                key[vertex] = weight;
                parent[vertex] = u;
                insert(&pq, vertex, weight);
            }
        }
    }

    // Print MST
    for (int i = 1; i < V; i++)
        printf("%d - %d : %d\n", parent[i], i, key[i]);
}

Time: O((V + E) log V)

B. Kruskal’s Algorithm (Greedy + Union-Find)

Sort all edges → Pick smallest edge that doesn’t form cycle

int parent[MAX];

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unionSets(int x, int y) {
    parent[find(x)] = find(y);
}

void kruskalMST(Edge edges[], int E) {
    Edge result[V-1];
    int e = 0, i = 0;

    // Sort edges by weight
    qsort(edges, E, sizeof(Edge), cmp);

    for (int i = 0; i < V; i++) parent[i] = i;

    while (e < V-1 && i < E) {
        Edge next = edges[i++];
        int x = find(next.u);
        int y = find(next.v);
        if (x != y) {
            result[e++] = next;
            unionSets(x, y);
        }
    }

    // Print result
    for (int i = 0; i < e; i++)
        printf("%d - %d : %d\n", result[i].u, result[i].v, result[i].w);
}

Time: O(E log E)

7. Transitive Closure – Warshall’s Algorithm

Find reachability between all pairs
reach[i][j] = 1 if path exists from i to j

void warshall(int reach[V][V]) {
    // Initialize
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            reach[i][j] = adj[i][j];

    // Add vertices as intermediates
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
}

Time: O(V³)
Use: Reachability, dependency graphs

8. Shortest Path

A. Dijkstra’s Algorithm

Single source, non-negative weights

void dijkstra(int src) {
    int dist[V];
    bool visited[V];
    PriorityQueue pq;

    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[src] = 0;
    insert(&pq, src, 0);

    while (!isEmpty(&pq)) {
        int u = extractMin(&pq);
        if (visited[u]) continue;
        visited[u] = true;

        for (Node* v = head[u]; v != NULL; v = v->next) {
            int vertex = v->vertex;
            int weight = v->weight;
            if (!visited[vertex] && dist[u] + weight < dist[vertex]) {
                dist[vertex] = dist[u] + weight;
                insert(&pq, vertex, dist[vertex]);
            }
        }
    }

    // Print distances
    for (int i = 0; i < V; i++)
        printf("Distance to %d: %d\n", i, dist[i]);
}

Time: O((V + E) log V)

9. Comparison Table

Algorithm Use Time Data Structure
DFS Path, cycle O(V+E) Stack
BFS Shortest path O(V+E) Queue
Prim MST O((V+E)logV) Priority Queue
Kruskal MST O(E log E) Union-Find
Warshall All-pairs reachability O(V³) Matrix
Dijkstra Single-source shortest O((V+E)logV) Priority Queue

10. Example Graph

    0 --1--> 1
    |       / \
    4      2   3
    |     /     \
    2 --8--> 3   7
  • Adjacency List:
  • 0: 1(1), 2(4)
  • 1: 2(2), 3(3)
  • 2: 3(8)
  • 3:

11. Practice Problems

  1. Find all connected components
  2. Detect cycle using DFS
  3. Implement topological sort
  4. Find MST cost using Prim/Kruskal
  5. Compute transitive closure
  6. Shortest path from 0 to all
  7. Bipartite check using BFS

12. Key Takeaways

Concept Insight
Adjacency List Best for sparse graphs
BFS Shortest path in unweighted
DFS Cycle, path existence
Prim Grows from vertex
Kruskal Sorts all edges
Warshall All-pairs reachability
Dijkstra Non-negative weights only

End of Notes

Last updated: Nov 12, 2025