Lesson 8 — Graphs — C Programming

📖

Why Graphs?

A graph models things and the connections between them: cities linked by roads, people linked by friendship, pages linked by hyperlinks. A graph has vertices (the things) and edges (the connections).

Directed graph — edges go one way, like A → B (a one-way street)
Undirected graph — edges go both ways, like A — B (a friendship)
Weighted graph — each edge carries a cost, like road distance
Traversal — visiting every reachable vertex, using BFS or DFS

0 --- 1 | | 4 vertices, 4 edges (undirected) 2 --- 3

Representation	Space	Check edge (u,v)	Best for
Matrix	O(V²)	O(1)	Dense graphs, small V
List	O(V+E)	O(degree)	Sparse graphs, most real cases

1

Adjacency Matrix

2D array

adjacency matrix — reading matrix[i][j]

matrix[i][j]

① The cell

=

1

② Edge exists between i and j

or

0

③ No edge

The adjacency matrix is a V×V grid of 0s and 1s. Row i tells you every vertex that i connects to. Simple to build and to check a single edge, but wastes memory when the graph has few edges.

Example 1 · adjacency_matrix.c

adjacency_matrix.c

C

#include <stdio.h>

#define V 4

int main() {
    int matrix[V][V] = {0};   // start with no edges
    int edges, u, v;

    printf("Enter number of edges: ");
    scanf("%d", &edges);

    for (int i = 0; i < edges; i++) {
        printf("Enter edge (u v): ");
        scanf("%d %d", &u, &v);
        matrix[u][v] = 1;   // undirected: mark both directions
        matrix[v][u] = 1;
    }

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

    return 0;
}

terminal

output

Enter number of edges: 4
Enter edge (u v): 0 1
Enter edge (u v): 0 2
Enter edge (u v): 1 3
Enter edge (u v): 2 3

Adjacency Matrix:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

💡 Directed graphs only set matrix[u][v] = 1 — skip the reverse line, since the edge only goes one way.

2

Adjacency List

Array of linked lists

Instead of a full V×V grid, each vertex keeps a linked list of only its real neighbours. This is the representation used in almost every practical graph algorithm, because it uses far less memory on sparse graphs.

0 -> 2 -> 1 -> NULL 1 -> 3 -> 0 -> NULL 2 -> 3 -> 0 -> NULL 3 -> 2 -> 1 -> NULL

Example 2 · adjacency_list.c

adjacency_list.c

C

#include <stdio.h>
#include <stdlib.h>
#define V 4

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

struct Node* head[V] = { NULL };   // one list-head per vertex

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

    // undirected: also add u to v's list
    newNode = malloc(sizeof(struct Node));
    newNode->vertex = u;
    newNode->next   = head[v];
    head[v] = newNode;
}

void printList() {
    for (int i = 0; i < V; i++) {
        printf("%d -> ", i);
        struct Node *temp = head[i];
        while (temp != NULL) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 3);

    printf("Adjacency List:\n");
    printList();

    return 0;
}

terminal

output

Adjacency List:
0 -> 2 -> 1 -> NULL
1 -> 3 -> 0 -> NULL
2 -> 3 -> 0 -> NULL
3 -> 2 -> 1 -> NULL

⚠️ Free your nodes. Every malloc() in addEdge() should eventually be matched with free(), or the program leaks memory once the graph is discarded.

3

Breadth-First Search (BFS)

Queue-based

BFS explores level by level: visit a vertex, then all its direct neighbours, then their neighbours. It uses a queue and finds the shortest path in an unweighted graph.

Example 3 · bfs.c

bfs.c

C

#include <stdio.h>
#define V 4

int matrix[V][V] = {
    {0,1,1,0},
    {1,0,0,1},
    {1,0,0,1},
    {0,1,1,0}
};

void bfs(int start) {
    int visited[V] = {0};
    int queue[V], front = 0, rear = 0;

    visited[start] = 1;
    queue[rear++] = start;

    printf("BFS order: ");
    while (front < rear) {
        int curr = queue[front++];
        printf("%d ", curr);

        for (int i = 0; i < V; i++) {
            if (matrix[curr][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;   // enqueue neighbour
            }
        }
    }
    printf("\n");
}

int main() {
    bfs(0);
    return 0;
}

terminal

output

BFS order: 0 1 2 3

💡 visited[] marks on enqueue, not on dequeue. That's what stops the same vertex from being added to the queue twice.

4

Depth-First Search (DFS)

Recursion

DFS goes as deep as possible down one path before backtracking. It's naturally written with recursion — the function call stack acts as the stack data structure.

Example 4 · dfs.c

dfs.c

C

#include <stdio.h>
#define V 4

int matrix[V][V] = {
    {0,1,1,0},
    {1,0,0,1},
    {1,0,0,1},
    {0,1,1,0}
};
int visited[V] = {0};

void dfs(int curr) {
    visited[curr] = 1;
    printf("%d ", curr);

    for (int i = 0; i < V; i++) {
        if (matrix[curr][i] == 1 && !visited[i])
            dfs(i);   // recurse into unvisited neighbour
    }
}

int main() {
    printf("DFS order: ");
    dfs(0);
    printf("\n");
    return 0;
}

terminal

output

DFS order: 0 1 3 2

Traversal	Structure	Order	Typical use
BFS	Queue	Level by level	Shortest path, hop count
DFS	Stack / recursion	Deep first	Cycle detection, path existence

⚠️ Watch recursion depth. On a very large graph, recursive DFS can overflow the call stack — use an explicit stack[] array for an iterative version if that's a concern.

5

Connected Components & Cycle Detection

DFS applications

Connected components — groups of vertices reachable from each other. Run DFS from every unvisited vertex; each fresh DFS call is one new component. Cycle detection reuses the same DFS, but also tracks the parent vertex to spot a back-edge.

Example 5 · connected_components.c

connected_components.c

C

#include <stdio.h>
#define V 6

// vertices 4 and 5 are isolated from 0-1-2-3
int matrix[V][V] = {
    {0,1,1,0,0,0},
    {1,0,0,1,0,0},
    {1,0,0,1,0,0},
    {0,1,1,0,0,0},
    {0,0,0,0,0,1},
    {0,0,0,0,1,0}
};
int visited[V] = {0};

void dfs(int curr) {
    visited[curr] = 1;
    for (int i = 0; i < V; i++)
        if (matrix[curr][i] == 1 && !visited[i])
            dfs(i);
}

int main() {
    int components = 0;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i);          // visit the whole component
            components++;    // one new component found
        }
    }

    printf("Connected components: %d\n", components);
    return 0;
}

terminal

output

Connected components: 2

Bonus · cycle_detect.c

cycle_detect.c

C

int dfs(int curr, int parent) {
    visited[curr] = 1;
    for (int i = 0; i < V; i++) {
        if (matrix[curr][i] == 1) {
            if (!visited[i]) {
                if (dfs(i, curr)) return 1;
            } else if (i != parent) {
                return 1;   // visited neighbour that isn't our parent = cycle
            }
        }
    }
    return 0;
}

💡 Most common graph patterns: BFS → shortest path & hop count. DFS → cycle detection, path existence, exploring every possibility. visited[] → the single habit that prevents infinite loops on any graph.

Q

Quick Quiz

Question 1 of 4

In an adjacency matrix, what does matrix[i][j] = 1 mean?

Question 2 of 4

Which representation uses less memory for a sparse graph?

Question 3 of 4

Which data structure powers a standard BFS traversal?

Question 4 of 4

What is the purpose of the visited[] array during traversal?

✓

Lesson Checklist

I know what vertices, edges, directed and undirected graphs are
I can build an adjacency matrix in C
I can build an adjacency list using linked lists in C
I understand BFS uses a queue and explores level by level
I understand DFS uses recursion and explores depth first
I know why the visited[] array is essential
I can count connected components using DFS
I can detect a cycle in an undirected graph
I know when to choose a matrix vs a list
I completed the quiz

→

Next: Lesson 9 — Trees

Coming up

🌳 Binary trees & node structs Lesson 9
🔍 Binary search trees Lesson 9
🔁 Tree traversal — inorder, preorder, postorder Lesson 9
⚖️ Balancing & height Lesson 9

Graphs & Traversal

Why Graphs?

Adjacency Matrix

adjacency matrix — reading matrix[i][j]

Adjacency List

Breadth-First Search (BFS)

Depth-First Search (DFS)

Connected Components & Cycle Detection

Quick Quiz

Lesson Checklist

Next: Lesson 9 — Trees