Module 20: Graph

Learning Objectives

By the end of this module, you will be able to:

• Understand graphs and their components.
• Learn graph representations using adjacency matrices and adjacency lists.
• Perform graph traversals using BFS and DFS.
• Understand topological sorting.
• Learn shortest path algorithms including Dijkstra, Bellman-Ford, and Floyd-Warshall.
• Learn Minimum Spanning Tree (MST) algorithms: Prim's and Kruskal's.
• Understand the Union-Find (Disjoint Set Union) data structure.
• Solve graph-based interview problems.

Introduction

A Graph is a non-linear data structure consisting of vertices (nodes) connected by edges.

Unlike trees, graphs can contain cycles, multiple paths, and disconnected components.

Graphs are widely used in:

• Google Maps
• Social Networks
• Computer Networks
• GPS Navigation
• Recommendation Systems
• Artificial Intelligence
• Flight Routes
• Web Crawlers

What is a Graph?

A graph consists of:

• Vertices (Nodes)
• Edges (Connections)

Example

textCopy
1      A
2     / \
3    B---C
4     \
5      D

Vertices

textCopy
1A B C D

Edges

textCopy
1(A,B)
2
3(A,C)
4
5(B,C)
6
7(B,D)

Types of Graphs

Undirected Graph

Edges have no direction.

textCopy
1A ----- B

Directed Graph

Edges have direction.

textCopy
1A -----> B

Weighted Graph

Edges have weights.

textCopy
1A --5--> B

Unweighted Graph

Edges have no weights.

textCopy
1A ------ B

Cyclic Graph

Contains one or more cycles.

textCopy
1A → B → C
2
3↑       ↓
4
5└───────┘

Acyclic Graph

Contains no cycles.

Example

textCopy
1A
2
3↓
4
5B
6
7↓
8
9C

Graph Terminology

Graph Representation

There are two common ways to represent graphs:

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix

A matrix stores whether an edge exists between two vertices.

Example Graph

textCopy
1A ---- B
2
3|      |
4
5C ---- D

Matrix

textCopy
1      A B C D
2
3A     0 1 1 0
4
5B     1 0 0 1
6
7C     1 0 0 1
8
9D     0 1 1 0

Program

cCopy
1#include <stdio.h>
2
3#define V 4
4
5int graph[V][V] = {
6    {0,1,1,0},
7    {1,0,0,1},
8    {1,0,0,1},
9    {0,1,1,0}
10};
11
12int main()
13{
14    for(int i = 0; i < V; i++)
15    {
16        for(int j = 0; j < V; j++)
17        {
18            printf("%d ", graph[i][j]);
19        }
20
21        printf("\n");
22    }
23
24    return 0;
25}

Advantages

• Simple implementation
• Fast edge lookup

Disadvantages

• Wastes memory for sparse graphs

Space Complexity

textCopy
1O(V²)

Adjacency List

Stores neighbors of each vertex.

Example

textCopy
10 → 1 → 2
2
31 → 0 → 3
4
52 → 0 → 3
6
73 → 1 → 2

Advantages

• Memory efficient
• Ideal for sparse graphs

Space Complexity

textCopy
1O(V + E)

Graph Traversal

Traversal means visiting every vertex exactly once.

Two popular methods:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Breadth-First Search (BFS)

BFS visits vertices level by level.

Uses

• Queue
• Visited Array

Example

textCopy
1      A
2     / \
3    B   C
4       /
5      D

Traversal

textCopy
1A
2
3↓
4
5B C
6
7↓
8
9D

Output

textCopy
1A B C D

Program

cCopy
1#include <stdio.h>
2
3#define MAX 100
4
5int queue[MAX];
6int front = 0, rear = 0;
7
8void enqueue(int x)
9{
10    queue[rear++] = x;
11}
12
13int dequeue()
14{
15    return queue[front++];
16}

Time Complexity

textCopy
1O(V + E)

Applications

• Shortest Path (Unweighted Graph)
• Web Crawling
• Social Networks
• Broadcasting

Depth-First Search (DFS)

DFS explores one path completely before backtracking.

Uses

• Stack
• Recursion

Example

textCopy
1      A
2     / \
3    B   C
4       /
5      D

Possible Traversal

textCopy
1A B C D

Recursive Program

cCopy
1void DFS(int node)
2{
3    visited[node] = 1;
4
5    printf("%d ", node);
6
7    for(each neighbor)
8    {
9        if(!visited[neighbor])
10        {
11            DFS(neighbor);
12        }
13    }
14}

Time Complexity

textCopy
1O(V + E)

Applications

• Cycle Detection
• Topological Sorting
• Maze Solving
• Connected Components

BFS vs DFS

Topological Sort

Topological Sorting applies only to Directed Acyclic Graphs (DAGs).

Example

textCopy
1A → B → D
2
3↓
4
5C

Valid Order

textCopy
1A C B D

Applications

• Task Scheduling
• Course Scheduling
• Build Systems
• Dependency Resolution

Time Complexity

textCopy
1O(V + E)

Dijkstra Algorithm

Finds the shortest path from one source to all other vertices.

Requirements

• Weighted Graph
• No negative edge weights

Example

textCopy
1A --2--> B
2
3A --4--> C
4
5B --1--> C

Shortest Path

textCopy
1A → B → C
2
3Cost = 3

Uses

• Min Heap
• Priority Queue

Time Complexity

Applications

• GPS Navigation
• Google Maps
• Routing

Bellman-Ford Algorithm

Bellman-Ford also finds shortest paths.

Unlike Dijkstra, it supports negative edge weights.

Advantages

• Detects negative weight cycles.

Time Complexity

textCopy
1O(V × E)

Applications

• Network Routing
• Currency Exchange
• Financial Systems

Floyd-Warshall Algorithm

Finds the shortest paths between every pair of vertices.

Example

textCopy
1Distance Matrix
2
3↓
4
5Updated Matrix
6
7↓
8
9Shortest Distances

Time Complexity

textCopy
1O(V³)

Applications

• Traffic Networks
• Flight Systems
• Distance Tables

Minimum Spanning Tree (MST)

An MST connects all vertices with:

• Minimum total edge weight.
• No cycles.

Two popular algorithms:

• Prim's Algorithm
• Kruskal's Algorithm

Prim's Algorithm

Builds the MST by expanding one vertex at a time.

Uses

• Priority Queue
• Min Heap

Time Complexity

textCopy
1O(E log V)

Applications

• Road Networks
• Cable Networks
• Water Supply Systems

Kruskal's Algorithm

Builds the MST by selecting the smallest edges first.

Steps

1. Sort edges.
2. Pick the smallest edge.
3. Avoid cycles.
4. Repeat until MST is complete.

Time Complexity

textCopy
1O(E log E)

Uses

• Union-Find

Union Find (Disjoint Set Union)

Union-Find efficiently manages connected components.

Operations

• Make Set
• Find
• Union

Applications

• Kruskal's Algorithm
• Cycle Detection
• Dynamic Connectivity

Simple Structure

cCopy
1int parent[100];
2
3void makeSet(int n)
4{
5    for(int i = 0; i < n; i++)
6        parent[i] = i;
7}

Optimizations

• Path Compression
• Union by Rank

Average Complexity

textCopy
1Nearly O(1)

Practice Project 1: Connected Components

Problem

Count the number of connected components.

Example

textCopy
1Component 1
2
3A B C
4
5Component 2
6
7D E

Output

textCopy
12

Approach

• Run DFS or BFS from every unvisited vertex.
• Count how many times traversal starts.

Time Complexity

textCopy
1O(V + E)

Practice Project 2: Shortest Path

Problem

Find the shortest path from a source vertex.

Example

textCopy
1A → B → C

Choose

• BFS for unweighted graphs.
• Dijkstra for weighted graphs without negative edges.
• Bellman-Ford if negative weights exist.
• Floyd-Warshall for all-pairs shortest paths.

Practice Project 3: Cycle Detection

Problem

Determine whether a graph contains a cycle.

Approach

• DFS for directed or undirected graphs (with appropriate parent tracking).
• Union-Find for undirected graphs.
• Kahn's Algorithm for detecting cycles in directed graphs by checking if all vertices are processed.

Time Complexity

textCopy
1O(V + E)

Comparison of Graph Algorithms

Real-World Applications

Google Maps

Finds the shortest route between locations using graph algorithms.

Social Networks

Users are represented as vertices, and friendships are represented as edges.

Computer Networks

Routers and switches use graph algorithms for packet routing.

Flight Reservation Systems

Airports are vertices, and flight routes are edges.

Recommendation Systems

Graphs model relationships between users, products, and content to generate recommendations.

Common Interview Questions

1. What is the difference between a Tree and a Graph?
2. Compare Adjacency Matrix and Adjacency List.
3. Implement BFS.
4. Implement DFS.
5. Find connected components.
6. Detect a cycle in a graph.
7. Explain Topological Sort.
8. Compare Dijkstra and Bellman-Ford.
9. Compare Prim and Kruskal.
10. Explain Union-Find with Path Compression.

Common Mistakes to Avoid

• Using Dijkstra's algorithm on graphs with negative edge weights.
• Applying Topological Sort to graphs containing cycles.
• Forgetting to mark vertices as visited during BFS or DFS.
• Choosing an adjacency matrix for sparse graphs, leading to unnecessary memory usage.
• Ignoring path compression and union by rank in Union-Find implementations.
• Confusing Minimum Spanning Tree algorithms with shortest path algorithms.

Best Practices

• Use an adjacency list for sparse graphs and an adjacency matrix for dense graphs.
• Select BFS for shortest paths in unweighted graphs.
• Use DFS for graph traversal, cycle detection, and connected component analysis.
• Prefer Dijkstra's algorithm for positive weighted graphs and Bellman-Ford when negative weights are present.
• Use Prim's or Kruskal's algorithm for Minimum Spanning Tree problems.
• Optimize Union-Find using path compression and union by rank.

Module Summary

In this module, you learned:

• What graphs are and how they model relationships between connected entities.
• Two graph representations: Adjacency Matrix and Adjacency List.
• How to traverse graphs using Breadth-First Search (BFS) and Depth-First Search (DFS).
• How Topological Sort orders tasks in a Directed Acyclic Graph (DAG).
• The shortest path algorithms Dijkstra, Bellman-Ford, and Floyd-Warshall.
• The Minimum Spanning Tree algorithms Prim's and Kruskal's.
• How Union-Find (Disjoint Set Union) helps solve connectivity and cycle detection problems.
• Practical graph problems including connected components, shortest paths, and cycle detection.

After completing this module, you'll have a strong foundation in Data Structures and Algorithms in C and be prepared to solve advanced coding interview questions, competitive programming challenges, and real-world software engineering problems involving efficient data organization and graph-based computation.