Chapter 6

Graphs

One of the most powerful data structures in Computer Science.

Learning Outcomes

• Understand graph concepts and terminology
• Represent graphs efficiently
• Perform graph traversals
• Build Minimum Spanning Trees
• Apply shortest path algorithms

Why Study Graphs?

• Social Networks
• Google Maps
• Flight Networks
• Computer Networks
• AI Knowledge Graphs
• Recommendation Systems

Real World Examples

Definition of a Graph

G = (V, E)

A Simple Graph

Vertices (Nodes)

A vertex represents an object or entity.

Vertices = {A, B, C, D}

Examples: Person, City, Computer

Edges

An edge represents a relationship or connection.

(A,B)
(A,C)
(B,D)
(C,D)

Examples: Friendship, Road, Communication Link

Degree of a Vertex

Degree(v)
=
Number of edges connected to v

• Degree(A) = 2
• Degree(B) = 2
• Degree(C) = 2
• Degree(D) = 2

Path

A → B → D

A sequence of connected vertices.

Length = Number of edges.

Cycle

A → B → C → A

Starts and ends at the same vertex.

Cycles are important in routing and networking.

Connected Graph

Every vertex can reach every other vertex.

Disconnected Graph

Some vertices cannot be reached.

Graph Terminologies Summary

Quick Quiz

1. What is G = (V,E)?
2. Difference between vertex and edge?
3. What is degree?
4. What is a cycle?
5. What is a connected graph?

Next Topic

6.2 Types of Graphs

• Directed Graphs
• Undirected Graphs
• Weighted Graphs
• Complete Graphs
• Bipartite Graphs
• DAGs

6.2 Types of Graphs

Graphs can be classified based on direction, weights, connectivity, cycles and structure.

Classification of Graphs

• Undirected Graph
• Directed Graph
• Weighted Graph
• Unweighted Graph
• Complete Graph
• Null Graph
• Cyclic Graph
• Acyclic Graph
• Bipartite Graph
• Tree

Undirected Graph

Edges have no direction.

A ----- B

If A is connected to B, then B is also connected to A.

Undirected Graph Example

Friendship network example.

Directed Graph (Digraph)

Edges have directions.

A → B

Connection is one-way.

Directed Graph Example

Twitter follows relationship.

In-Degree and Out-Degree

A → B → C

Undirected vs Directed Graph

Weighted Graph

Each edge has an associated cost, distance, time, or weight.

A --5-- B

Common in routing and shortest-path problems.

Weighted Graph Example

Weight may represent distance (km).

Unweighted Graph

All edges are considered equal.

A ----- B ----- C

Only connectivity matters.

Weighted vs Unweighted

Complete Graph

Every vertex is connected to every other vertex.

Kₙ

Maximum possible number of edges.

Complete Graph Example (K₄)

Every pair of vertices is connected.

Edges in a Complete Graph

Number of Edges

= n(n − 1) / 2

Null Graph

A graph with vertices but no edges.

No vertex is connected.

Connected Graph

Every vertex can be reached from every other vertex.

All vertices reachable

Only one connected component exists.

Disconnected Graph

Contains multiple connected components.

Some vertices cannot reach others.

Cyclic Graph

A graph containing at least one cycle.

A → B → C → A

Start from a vertex and return to it.

Cyclic Graph Example

Cycle: A → B → C → A

Acyclic Graph

A graph that contains no cycles.

A → B → C → D

Impossible to return to the starting vertex.

Acyclic Graph Example

Directed Acyclic Graph (DAG)

Directed Graph + No Cycles

DAG = Directed Acyclic Graph

Very important in AI, Scheduling and Compilers.

DAG Example

No directed cycle exists.

Applications of DAG

• Course prerequisite planning
• Build systems (Makefiles)
• Task scheduling
• Compiler optimization
• Neural network computation graphs

Bipartite Graph

Vertices can be divided into two disjoint sets.

U ∩ V = ∅

Edges only connect vertices from different sets.

Bipartite Graph Example

Student ↔ Course registration network

Tree as a Graph

A tree is a special graph that:

• Is connected
• Contains no cycles
• Has n−1 edges

Tree Example

Every tree is a graph, but not every graph is a tree.

Summary of Graph Types

Quick Quiz

1. What is a complete graph?
2. Difference between cyclic and acyclic graphs?
3. What is a DAG?
4. Can a tree contain a cycle?
5. Give one application of a bipartite graph.

Next Topic

6.3 Graph Representation

• Adjacency Matrix
• Incidence Matrix
• Adjacency List

How do we store graphs inside a computer?

6.3 Graph Representation

A graph must be stored efficiently inside computer memory.

Three common representations:

• Adjacency Matrix
• Incidence Matrix
• Adjacency List

Sample Graph

Edges:
(A,B)
(A,C)
(B,D)
(C,D)

What is an Adjacency Matrix?

A two-dimensional matrix used to represent graph connections.

Matrix Size

= V × V

Rows = Source Vertex

Columns = Destination Vertex

Vertex Numbering

Step 1: Create Empty Matrix

Step 2: Insert Edge (A,B)

Because graph is undirected.

Step 3: Insert Remaining Edges

(A,C)
(B,D)
(C,D)

Continue updating the matrix.

Final Adjacency Matrix

Interpreting the Matrix

matrix[A][B] = 1

A is connected to B.

matrix[A][D] = 0

A is not connected to D.

Directed Graph Matrix

A → B

Not symmetric.

Weighted Graph Matrix

A --5-- B

Store edge weights instead of 1.

Advantages of Adjacency Matrix

• Simple implementation
• Fast edge lookup O(1)
• Easy traversal of dense graphs
• Suitable for mathematical operations

Adjacency Matrix Algorithm

AdjacencyMatrix(V, edges[]):
    // Initialization
    Create matrix[V][V] filled with 0

    // Add each edge
    for each edge (u, v) in edges[]:
        matrix[u][v] = 1
        matrix[v][u] = 1  // undirected graph

    // Edge Check: O(1)
    hasEdge(u, v):
        return matrix[u][v] == 1

    // Add Edge: O(1)
    addEdge(u, v):
        matrix[u][v] = 1
        matrix[v][u] = 1

    // Remove Edge: O(1)
    removeEdge(u, v):
        matrix[u][v] = 0
        matrix[v][u] = 0
    

Adjacency Matrix in C

#include <stdio.h>
#include <string.h>

#define MAX 10

int V;                        // Number of vertices
int matrix[MAX][MAX];         // Adjacency matrix

// Initialize matrix to all zeros
void initGraph(int vertices) {
    V = vertices;
    memset(matrix, 0, sizeof(matrix));
}

// Add undirected edge between u and v
void addEdge(int u, int v) {
    matrix[u][v] = 1;
    matrix[v][u] = 1;   // Remove this line for directed graph
}

// Remove edge between u and v
void removeEdge(int u, int v) {
    matrix[u][v] = 0;
    matrix[v][u] = 0;
}

// Check if edge exists: O(1)
int hasEdge(int u, int v) {
    return matrix[u][v] == 1;
}

// Print the adjacency matrix
void printMatrix() {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++)
            printf("%d ", matrix[i][j]);
        printf("\n");
    }
}

int main() {
    initGraph(4);     // Vertices: 0(A), 1(B), 2(C), 3(D)
    addEdge(0, 1);    // A-B
    addEdge(0, 2);    // A-C
    addEdge(1, 3);    // B-D
    addEdge(2, 3);    // C-D
    printMatrix();
    return 0;
}
    

Weighted Adjacency Matrix in C

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define MAX 10
#define INF INT_MAX

int V;
int wMatrix[MAX][MAX];  // Weighted adjacency matrix

void initWeightedGraph(int vertices) {
    V = vertices;
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            wMatrix[i][j] = (i == j) ? 0 : INF; // 0 on diagonal
}

// Add weighted undirected edge
void addWeightedEdge(int u, int v, int weight) {
    wMatrix[u][v] = weight;
    wMatrix[v][u] = weight;
}

void printWeightedMatrix() {
    printf("Weighted Adjacency Matrix:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (wMatrix[i][j] == INF) printf("INF ");
            else printf("%3d ", wMatrix[i][j]);
        }
        printf("\n");
    }
}
    

6.3 Graph Representation

How can a graph be stored inside computer memory?

• Adjacency Matrix
• Incidence Matrix
• Adjacency List

Example Graph

Vertices

A B C D

Edges

(A,B)
(A,C)
(B,D)
(C,D)

We will represent this graph in different ways.

Adjacency Matrix

A 2D matrix of size V × V.

Rows represent source vertices.

Columns represent destination vertices.

Building the Matrix

Adjacency Matrix Complexity

When is Matrix Useful?

• Dense Graphs
• Fast Edge Lookup
• Small Graphs

Best for Dense Graphs

Incidence Matrix

Rows represent vertices.

Columns represent edges.

Incidence Matrix Example

Incidence Matrix Characteristics

• Useful in graph theory
• Less common in programming
• Represents edge-vertex relationships
• Space: O(V × E)

Incidence Matrix Algorithm

IncidenceMatrix(V, E, edges[]):
    // Create V × E matrix filled with 0
    Create incMatrix[V][E] = 0

    // For each edge ej = (u, v) at index j:
    for j = 0 to E-1:
        u, v = edges[j]
        incMatrix[u][j] = 1  // vertex u is incident to edge j
        incMatrix[v][j] = 1  // vertex v is incident to edge j

    // Find all edges of a vertex u: scan row u
    getEdges(u):
        for j = 0 to E-1:
            if incMatrix[u][j] == 1: output edge j
    

Incidence Matrix in C

#include <stdio.h>
#include <string.h>

#define MAX_V 10
#define MAX_E 20

int V, E;
int incMatrix[MAX_V][MAX_E];  // incidence matrix

void initIncidenceMatrix(int vertices, int edges) {
    V = vertices;
    E = edges;
    memset(incMatrix, 0, sizeof(incMatrix));
}

// Add edge j between vertex u and v
void addEdge(int j, int u, int v) {
    incMatrix[u][j] = 1;
    incMatrix[v][j] = 1;
}

void printIncidenceMatrix() {
    printf("Incidence Matrix (V x E):\n");
    printf("  ");
    for (int j = 0; j < E; j++) printf("E%d ", j);
    printf("\n");
    char labels[] = "ABCD";
    for (int i = 0; i < V; i++) {
        printf("%c ", labels[i]);
        for (int j = 0; j < E; j++)
            printf(" %d  ", incMatrix[i][j]);
        printf("\n");
    }
}

int main() {
    // Graph: A-B(E0), A-C(E1), B-D(E2), C-D(E3)
    initIncidenceMatrix(4, 4);
    addEdge(0, 0, 1);  // E0: A-B
    addEdge(1, 0, 2);  // E1: A-C
    addEdge(2, 1, 3);  // E2: B-D
    addEdge(3, 2, 3);  // E3: C-D
    printIncidenceMatrix();
    return 0;
}
    

Adjacency List

Each vertex stores a list of its neighbors.

Adjacency List Construction

A → B → C

B → A → D

C → A → D

D → B → C

Adjacency List Visualization

A : B, C

B : A, D

C : A, D

D : B, C

Only existing edges are stored.

Adjacency List Complexity

When is Adjacency List Useful?

• Sparse Graphs
• Large Networks
• Social Networks
• Road Networks

Best for Sparse Graphs — O(V+E) space

Adjacency List Algorithm

AdjacencyList(V, edges[]):
    // Create array of lists, one per vertex
    Create list adj[V]

    // Add each edge
    for each edge (u, v) in edges[]:
        adj[u].append(v)
        adj[v].append(u)   // undirected

    // Add Edge: O(1)
    addEdge(u, v):
        adj[u].append(v)
        adj[v].append(u)

    // Remove Edge: O(degree)
    removeEdge(u, v):
        adj[u].remove(v)
        adj[v].remove(u)

    // Get all neighbors of u: O(degree(u))
    getNeighbors(u):
        return adj[u]
    

Adjacency List in C (Array of Arrays)

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

#define MAX_V 10
#define MAX_NEIGHBORS 10

int V;
int adjList[MAX_V][MAX_NEIGHBORS];
int degree[MAX_V];   // number of neighbors per vertex

void initGraph(int vertices) {
    V = vertices;
    for (int i = 0; i < V; i++) degree[i] = 0;
}

// Add undirected edge u-v
void addEdge(int u, int v) {
    adjList[u][degree[u]++] = v;
    adjList[v][degree[v]++] = u;
}

// Print adjacency list
void printAdjList() {
    char labels[] = "ABCD";
    printf("Adjacency List:\n");
    for (int i = 0; i < V; i++) {
        printf("%c: ", labels[i]);
        for (int j = 0; j < degree[i]; j++)
            printf("%c ", labels[adjList[i][j]]);
        printf("\n");
    }
}

int main() {
    initGraph(4);
    addEdge(0, 1);  // A-B
    addEdge(0, 2);  // A-C
    addEdge(1, 3);  // B-D
    addEdge(2, 3);  // C-D
    printAdjList();
    return 0;
}
    

Adjacency List Using Linked List (C)

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

// Node in the linked list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// Graph structure
typedef struct Graph {
    int V;
    Node** adjList;   // array of linked list heads
} Graph;

// Create a new graph
Graph* createGraph(int V) {
    Graph* g = malloc(sizeof(Graph));
    g->V = V;
    g->adjList = malloc(V * sizeof(Node*));
    for (int i = 0; i < V; i++) g->adjList[i] = NULL;
    return g;
}

// Create a new adjacency list node
Node* newNode(int v) {
    Node* n = malloc(sizeof(Node));
    n->vertex = v;  n->next = NULL;
    return n;
}

// Add undirected edge u--v
void addEdge(Graph* g, int u, int v) {
    // Add v to u's list
    Node* n = newNode(v);
    n->next = g->adjList[u];
    g->adjList[u] = n;
    // Add u to v's list
    n = newNode(u);
    n->next = g->adjList[v];
    g->adjList[v] = n;
}

void printGraph(Graph* g) {
    char labels[] = "ABCD";
    for (int v = 0; v < g->V; v++) {
        printf("%c: ", labels[v]);
        Node* cur = g->adjList[v];
        while (cur) { printf("%c ", labels[cur->vertex]); cur = cur->next; }
        printf("\n");
    }
}

int main() {
    Graph* g = createGraph(4);
    addEdge(g, 0, 1); addEdge(g, 0, 2);
    addEdge(g, 1, 3); addEdge(g, 2, 3);
    printGraph(g);
    return 0;
}
    

Matrix vs List

Real-World Usage

Quick Quiz

1. What is an adjacency matrix?
2. What is an incidence matrix?
3. Why is adjacency list memory efficient?
4. Which representation is better for sparse graphs?

Next Topic

6.4 Operations on Graph

• Insert Vertex
• Insert Edge
• Delete Vertex
• Delete Edge
• Search Operations

6.4 Operations on Graph

Common operations performed on graphs.

• Insert Vertex
• Insert Edge
• Delete Vertex
• Delete Edge
• Search
• Traversal

Insert Vertex — Algorithm

InsertVertex(G, v):
    // For Adjacency Matrix:
    Expand matrix to (V+1) × (V+1)
    Initialize new row and column to 0
    V = V + 1

    // For Adjacency List:
    Add new empty list adj[v]
    V = V + 1
    

Complexity: Matrix O(V²) (resize) | List O(1)

Insert Vertex in C

// --- Adjacency Matrix approach ---
#include <stdio.h>
#include <string.h>
#define MAX 10
int V = 0;
int matrix[MAX][MAX];

void insertVertex() {
    // New vertex gets index V
    for (int i = 0; i <= V; i++) {
        matrix[V][i] = 0;  // new row
        matrix[i][V] = 0;  // new column
    }
    V++;   // increment vertex count
    printf("Vertex inserted. Total vertices: %d\n", V);
}

// --- Adjacency List approach ---
#define MAX_V 10
int adjList[MAX_V][MAX_V];
int degree[MAX_V];
int Vlist = 0;

void insertVertexList() {
    degree[Vlist] = 0;  // empty adjacency list
    Vlist++;
    printf("Vertex inserted. Total vertices: %d\n", Vlist);
}
    

Insert Edge — Algorithm

InsertEdge(G, u, v):
    // For Adjacency Matrix:
    matrix[u][v] = 1
    matrix[v][u] = 1    // undirected only
    // Complexity: O(1)

    // For Adjacency List:
    adj[u].append(v)
    adj[v].append(u)    // undirected only
    // Complexity: O(1)
    

Insert Edge in C

#include <stdio.h>
#define MAX 10

int V;
int matrix[MAX][MAX];

// Insert edge in Adjacency Matrix: O(1)
void insertEdgeMatrix(int u, int v) {
    if (u >= V || v >= V) {
        printf("Invalid vertices!\n");
        return;
    }
    matrix[u][v] = 1;
    matrix[v][u] = 1;   // remove for directed graph
    printf("Edge (%d, %d) inserted.\n", u, v);
}

// --- Adjacency List approach ---
int adjList[MAX][MAX];
int degree[MAX];

// Insert edge in Adjacency List: O(1)
void insertEdgeList(int u, int v) {
    adjList[u][degree[u]++] = v;
    adjList[v][degree[v]++] = u;
    printf("Edge (%d, %d) inserted.\n", u, v);
}
    

Delete Edge — Algorithm

DeleteEdge(G, u, v):
    // For Adjacency Matrix:
    matrix[u][v] = 0
    matrix[v][u] = 0    // undirected only
    // Complexity: O(1)

    // For Adjacency List:
    adj[u].remove(v)
    adj[v].remove(u)    // undirected only
    // Complexity: O(degree(u) + degree(v))
    

Delete Edge in C

#include <stdio.h>
#define MAX 10

int V;
int matrix[MAX][MAX];

// Delete edge from Adjacency Matrix: O(1)
void deleteEdgeMatrix(int u, int v) {
    matrix[u][v] = 0;
    matrix[v][u] = 0;
    printf("Edge (%d, %d) deleted.\n", u, v);
}

// --- Adjacency List ---
int adjList[MAX][MAX];
int degree[MAX];

// Delete edge from Adjacency List: O(degree)
void deleteEdgeList(int u, int v) {
    // Remove v from u's list
    for (int i = 0; i < degree[u]; i++) {
        if (adjList[u][i] == v) {
            adjList[u][i] = adjList[u][--degree[u]];
            break;
        }
    }
    // Remove u from v's list
    for (int i = 0; i < degree[v]; i++) {
        if (adjList[v][i] == u) {
            adjList[v][i] = adjList[v][--degree[v]];
            break;
        }
    }
    printf("Edge (%d, %d) deleted.\n", u, v);
}
    

Delete Vertex — Algorithm

DeleteVertex(G, v):
    // For Adjacency Matrix:
    // Set entire row v and column v to 0
    for i = 0 to V-1:
        matrix[v][i] = 0
        matrix[i][v] = 0
    // (Then optionally shift rows/columns)
    V = V - 1
    // Complexity: O(V)

    // For Adjacency List:
    // Remove v from every neighbor's list
    for each u in adj[v]:
        adj[u].remove(v)
    adj[v] = empty
    V = V - 1
    // Complexity: O(V + E)
    

All incident edges are also removed.

Delete Vertex in C

#include <stdio.h>
#define MAX 10

int V;
int matrix[MAX][MAX];

// Delete vertex v from Adjacency Matrix: O(V)
void deleteVertexMatrix(int v) {
    // Clear row v and column v
    for (int i = 0; i < V; i++) {
        matrix[v][i] = 0;
        matrix[i][v] = 0;
    }
    printf("Vertex %d deleted (all its edges cleared).\n", v);
}

// --- Adjacency List approach ---
int adjList[MAX][MAX];
int degree[MAX];

// Delete vertex v from Adjacency List: O(V+E)
void deleteVertexList(int v) {
    // Remove v from all neighbor lists
    for (int i = 0; i < degree[v]; i++) {
        int u = adjList[v][i];
        for (int j = 0; j < degree[u]; j++) {
            if (adjList[u][j] == v) {
                adjList[u][j] = adjList[u][--degree[u]];
                break;
            }
        }
    }
    degree[v] = 0;  // clear v's list
    printf("Vertex %d deleted.\n", v);
}
    

Searching in Graphs — Algorithm

// Search for an Edge (u, v)
SearchEdge(G, u, v):
    // Adjacency Matrix: O(1)
    if matrix[u][v] == 1: return true
    else: return false

    // Adjacency List: O(degree(u))
    for each w in adj[u]:
        if w == v: return true
    return false

// Search for a Vertex v
SearchVertex(G, v):
    // Matrix/List: O(1) if vertices are indexed
    if 0 <= v < V: return true
    else: return false
    

Searching in C

#include <stdio.h>
#define MAX 10

int V;
int matrix[MAX][MAX];

// Check if edge exists — Adjacency Matrix: O(1)
int searchEdgeMatrix(int u, int v) {
    if (u < V && v < V)
        return matrix[u][v] == 1;
    return 0;  // invalid
}

// Check if vertex is valid: O(1)
int searchVertex(int v) {
    return (v >= 0 && v < V);
}

// --- Adjacency List ---
int adjList[MAX][MAX];
int degree[MAX];

// Check if edge exists — Adjacency List: O(degree(u))
int searchEdgeList(int u, int v) {
    for (int i = 0; i < degree[u]; i++)
        if (adjList[u][i] == v) return 1;
    return 0;
}

int main() {
    V = 4;
    matrix[0][1] = matrix[1][0] = 1; // A-B
    matrix[0][2] = matrix[2][0] = 1; // A-C
    printf("Edge A-B exists: %d\n", searchEdgeMatrix(0, 1));
    printf("Edge A-D exists: %d\n", searchEdgeMatrix(0, 3));
    printf("Vertex 3 exists: %d\n", searchVertex(3));
    return 0;
}
    

6.5 Graph Traversal

Traversal means visiting every vertex of a graph systematically.

Why Do We Traverse Graphs?

• Search for a vertex
• Find paths
• Detect connectivity
• Build spanning trees
• Solve shortest-path problems

Two Traversal Techniques

Breadth First Search

(BFS)

Visit all neighbors first.

What is BFS?

Breadth First Search explores vertices level by level.

Nearest vertices first

BFS Uses a Queue

FIFO

First In First Out

The first vertex inserted is processed first.

BFS Formal Definition

"Breadth-first search is one of the simplest algorithms for searching a graph... it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k+1."

— Introduction to Algorithms (CLRS)

BFS Traversal Visualization

BFS Algorithm (Pseudocode)

BFS(graph, start):
    create a queue Q
    mark start as visited
    enqueue start into Q

    while Q is not empty:
        current = dequeue from Q
        process(current)
        
        for each neighbor of current:
            if neighbor is not visited:
                mark neighbor as visited
                enqueue neighbor into Q

BFS in C

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

#define MAX_VERTICES 100

int queue[MAX_VERTICES];
int front = 0, rear = 0;

void enqueue(int vertex) { queue[rear++] = vertex; }
int dequeue() { return queue[front++]; }
int isQueueEmpty() { return front == rear; }

void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int start, int numVertices) {
    int visited[MAX_VERTICES] = {0};
    
    visited[start] = 1;
    enqueue(start);
    
    printf("BFS Traversal: ");
    while (!isQueueEmpty()) {
        int current = dequeue();
        printf("%d ", current);
        
        for (int i = 0; i < numVertices; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(i);
            }
        }
    }
    printf("\n");
}

Complexity Analysis

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

V = Vertices, E = Edges

Applications of BFS

• Shortest Path (Unweighted Graph)
• Social Network Analysis
• Web Crawlers
• Network Broadcasting
• GPS Navigation

BFS Quiz

1. Which data structure is used in BFS?
2. What is FIFO?
3. What is the BFS traversal of the example graph?
4. What is the time complexity of BFS?

Depth First Search

(DFS)

Go deep before exploring siblings.

DFS Formal Definition

"The strategy followed by depth-first search is, as its name implies, to search 'deeper' in the graph whenever possible. Depth-first search explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it."

— Introduction to Algorithms (CLRS)

DFS Traversal Visualization

DFS Algorithm (Pseudocode)

DFS(graph, start):
    create a stack S
    push start to S

    while S is not empty:
        current = pop from S
        
        if current is not visited:
            mark current as visited
            process(current)
            
            for each neighbor of current in reverse order:
                if neighbor is not visited:
                    push neighbor to S

DFS in C (Recursive)

#include <stdio.h>

#define MAX_VERTICES 100

int visited[MAX_VERTICES] = {0};

void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int vertex, int numVertices) {
    // Mark the current node as visited and print it
    visited[vertex] = 1;
    printf("%d ", vertex);
    
    // Recur for all the vertices adjacent to this vertex
    for (int i = 0; i < numVertices; i++) {
        if (graph[vertex][i] == 1 && !visited[i]) {
            DFS(graph, i, numVertices);
        }
    }
}

BFS vs DFS

6.6 Minimum Spanning Tree

What is a Spanning Tree?

Before understanding Minimum Spanning Trees, we must first understand Spanning Trees.

Recall: Tree

• Connected graph
• Contains no cycles
• Exactly V−1 edges
• Every pair of vertices has exactly one path

What is a Spanning Tree?

Consider the following connected graph.

The graph contains multiple paths between vertices.

Removing Cycles

A spanning tree is obtained by removing edges without disconnecting the graph.

Definition of a Spanning Tree

Which One is a Spanning Tree?

Every connected graph can have multiple spanning trees.

From Spanning Tree to Minimum Spanning Tree

A graph may have many different spanning trees.

Weighted Graph

Each edge has an associated cost (weight).

Two Possible Spanning Trees

Weight

4 + 2 + 5 + 6 + 7

=

24

Weight

1 + 2 + 4 + 5 + 6

=

18

Comparing Two Spanning Trees

Both graphs are valid spanning trees because they:

• Contain all vertices
• Have exactly V − 1 edges
• Contain no cycles

Definition of Minimum Spanning Tree

• Contains all vertices
• Contains no cycles
• Exactly V − 1 edges
• Minimum total cost

Properties of MST

Can a Graph Have Multiple MSTs?

Yes.

If different spanning trees have the same minimum total weight, they are all valid Minimum Spanning Trees.

Tree A Weight = 15

Tree B Weight = 15

Both are MSTs

Applications of Minimum Spanning Tree

• Road Network Planning
• Computer Network Design
• Electric Power Distribution
• Water Pipeline Systems
• Telecommunication Networks
• Circuit Design
• Cluster Analysis in Machine Learning

How Do We Find an MST?

Searching every possible spanning tree is inefficient.

Greedy Strategy

A Greedy Algorithm makes the best local decision at every step, hoping to obtain the global optimum.

Greedy Algorithms for MST

Kruskal's Algorithm

Instead of growing from one vertex, Kruskal grows the MST by selecting edges in increasing order.

Kruskal Example

Original Weighted Graph

Step 1 — Sort the Edges

Kruskal Algorithm — Step 1

Select the Smallest Edge

Sorted Edge: C — F (Weight = 1)

Kruskal Algorithm — Step 2

Select Edge A — D (Weight = 2)

• Smallest remaining edge
• Does not create a cycle
• Accept the edge

Running Cost = 1 + 2 = 3

Kruskal Algorithm — Step 3

Select Edge D — E (Weight = 3)

• Next smallest edge
• Still no cycle
• Include in MST

Running Cost = 6

Kruskal Algorithm — Step 4

Select Edge A — B (Weight = 4)

• Connects a new vertex
• No cycle exists
• Accept the edge

Running Cost = 10

Kruskal Algorithm — Step 5

Check Edge B — E (Weight = 5)

Kruskal Algorithm — Step 6

Select Edge B — C (Weight = 6)

• No cycle is formed
• All six vertices are now connected
• The MST is complete

Running Cost = 16

Final Minimum Spanning Tree

Total MST Cost = 16

Final Minimum Spanning Tree (MST)

The selected edges are highlighted in green. The rejected edge (B–E) is shown in red dashed.

Kruskal's Algorithm

KRUSKAL(Graph G)

1. Sort all edges in ascending order of weight

2. Create an empty Minimum Spanning Tree (MST)

3. For each edge (u, v) in sorted order

       if Find(u) ≠ Find(v)

            Add edge to MST

            Union(u, v)

4. Stop when MST contains V - 1 edges

5. Return MST

6.6.2 Prim's Algorithm

A Vertex-Based Greedy Algorithm for Minimum Spanning Trees

Kruskal vs. Prim Algorithm

Basic Idea of Prim's Algorithm

Flow of Prim's Algorithm

Prim's Algorithm Example

Starting Vertex: A

Prim's Algorithm – Step 1

Prim's Algorithm – Step 2

Prim's Algorithm – Step 3

Prim's Algorithm – Step 4

Prim's Algorithm – Step 5

Final MST Using Prim's Algorithm

Prim's Algorithm in C

#include <stdio.h>
#include <stdbool.h>
#define V 6
#define INF 999999

int minKey(int key[], bool mstSet[]) {
    int min = INF, min_index = -1;
    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;
    return min_index;
}

void primMST(int graph[V][V]) {
    int parent[V];  // Array to store constructed MST
    int key[V];     // Key values used to pick minimum weight edge
    bool mstSet[V]; // To represent set of vertices included in MST

    for (int i = 0; i < V; i++)
        key[i] = INF, mstSet[i] = false;

    key[0] = 0;     // Make key 0 so that vertex 0 is picked first
    parent[0] = -1; // First node is always root of MST

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }
}
                

6.7 Shortest Path Algorithm

Dijkstra's Algorithm

Single Source Shortest Path (SSSP) Algorithm for Weighted Graphs

Learning Objectives

What is the Shortest Path?

Applications of Dijkstra's Algorithm

MST vs. Shortest Path

Conditions for Using Dijkstra's Algorithm

Dijkstra's Algorithm & Relaxation

Dijkstra Example Graph

Source Vertex: A

Dijkstra Initialization

Dijkstra – Step 1 (Process A)

Dijkstra – Step 2 (Process D)

Dijkstra – Step 3 (Process C)

Dijkstra – Step 4 (Process B)

Final Shortest Paths from Source A

Dijkstra's Algorithm in C

#include <stdio.h>
#include <stdbool.h>
#define V 5
#define INF 999999

int minDistance(int dist[], bool sptSet[]) {
    int min = INF, min_index = -1;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++)
        dist[i] = INF, sptSet[i] = false;

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        if (u == -1) break;
        sptSet[u] = true;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INF 
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
}
                

Complexity Analysis

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.