C Graphs

A graph is a collection of nodes (also called vertices) connected by edges. Unlike trees, graphs have no strict parent-child hierarchy — any node can connect to any other node. Graphs model real-world networks like road maps, social networks, computer networks, and airline routes.

Graph Terminology

Types of Graphs

Undirected Graph

Edges have no direction — if A connects to B, then B also connects to A.

A --- B
|     |
C --- D

Edges: A-B, A-C, B-D, C-D
If you can go from A to B, you can also go from B to A.

Directed Graph (Digraph)

Edges have a direction — an arrow shows which way you can travel.

A --> B
|     |
v     v
C     D

A can go to B and C.
B can go to D.
C and D have no outgoing edges.

Weighted Graph

Each edge carries a value (distance, cost, time).

A ---5--- B
|         |
3         2
|         |
C ---8--- D

Shortest path from A to D: A→B(5)→D(2) = 7
(Not A→C(3)→D(8) = 11)

Graph Representations in C

A graph can be stored in memory in two common ways.

1. Adjacency Matrix

A 2D array of size V×V (V = number of vertices). The value at matrix[i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

Graph:
  0 --- 1
  |     |
  2 --- 3

Adjacency Matrix (4 vertices: 0,1,2,3):

     0  1  2  3
  0 [0][1][1][0]
  1 [1][0][0][1]
  2 [1][0][0][1]
  3 [0][1][1][0]

matrix[0][1] = 1  → edge between 0 and 1 ✓
matrix[0][3] = 0  → no edge between 0 and 3 ✓

#include <stdio.h>
#define V 4

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

void printMatrix()
{
    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");
    }
}

2. Adjacency List

Each vertex stores a linked list of all vertices it connects to. This uses less memory for sparse graphs (graphs with few edges).

Graph (same as above):
0: [1] -> [2] -> NULL
1: [0] -> [3] -> NULL
2: [0] -> [3] -> NULL
3: [1] -> [2] -> NULL

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

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

struct Node* adjList[V];

void addEdge(int src, int dest)
{
    // Add dest to src's list
    struct Node *n = malloc(sizeof(struct Node));
    n->vertex = dest;
    n->next = adjList[src];
    adjList[src] = n;

    // Add src to dest's list (undirected)
    n = malloc(sizeof(struct Node));
    n->vertex = src;
    n->next = adjList[dest];
    adjList[dest] = n;
}

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

Graph Traversal Algorithms

Traversal means visiting every vertex of a graph. Two standard algorithms exist.

1. Depth-First Search (DFS)

DFS explores as deep as possible along each branch before backtracking. It uses a stack (or recursion) to track the path.

DFS from vertex 0 on graph: 0-1, 0-2, 1-3

Visit 0 → go deep to 1 → go deep to 3 → backtrack → go to 2
DFS order: 0, 1, 3, 2

#include <stdio.h>
#define V 4

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

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

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

int main()
{
    for (int i = 0; i < V; i++) visited[i] = 0;

    printf("DFS from 0: ");
    dfs(0);   // Output: DFS from 0: 0 1 3 2
    printf("\n");
    return 0;
}

2. Breadth-First Search (BFS)

BFS visits all neighbors of a vertex before going deeper. It uses a queue and explores level by level.

BFS from vertex 0:

Level 0: visit 0
Level 1: visit neighbors of 0 → 1, 2
Level 2: visit neighbors of 1 (not 0 again) → 3
BFS order: 0, 1, 2, 3

#include <stdio.h>
#define V 4
#define MAX 100

int adj[V][V] = {
    {0,1,1,0},
    {1,0,0,1},
    {1,0,0,0},
    {0,1,0,0}
};
int visited[V];
int queue[MAX];
int front = 0, rear = 0;

void bfs(int start)
{
    visited[start] = 1;
    queue[rear++] = start;

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

        for (int i = 0; i < V; i++)
        {
            if (adj[vertex][i] == 1 && !visited[i])
            {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main()
{
    for (int i = 0; i < V; i++) visited[i] = 0;

    printf("BFS from 0: ");
    bfs(0);   // Output: BFS from 0: 0 1 2 3
    printf("\n");
    return 0;
}

DFS vs BFS Comparison

Adjacency Matrix vs Adjacency List

Real-World Applications of Graphs

Summary

A graph consists of vertices (nodes) connected by edges. Graphs can be undirected (edges go both ways), directed (edges have a direction), or weighted (edges carry a cost). The two main ways to represent a graph in C are the adjacency matrix (a 2D array) and the adjacency list (an array of linked lists). DFS explores depth-first using recursion or a stack; BFS explores level-by-level using a queue. A visited array prevents infinite loops in cyclic graphs. Graphs are one of the most powerful and widely used data structures, forming the backbone of navigation, networking, social media, and compiler design.