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

Find all connected components
Detect cycle using DFS
Implement topological sort
Find MST cost using Prim/Kruskal
Compute transitive closure
Shortest path from 0 to all
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