1|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

STRICT LEGAL WARNING

By accessing or purchasing these notes, the user agrees to these legal terms.

These notes are the intellectual property of the author and are protected
under the Indian Copyright Act, 1957.
Unauthorized copying, selling, forwarding, or distributing these notes in any
form (digital or physical) is a criminal offense under the following laws:
Ja

• Section 63, Copyright Act, 1957 – Punishable by imprisonment up to 3

im

years and a fine.

il

• Section 316, BNS, 2023 – Cheating and dishonestly inducing delivery of

Pa

property.
te
l-

• Information Technology Act, 2000 – Applicable for digital piracy and

+9

unauthorized electronic distribution.

18

SECURITY NOTICE
78

Each page of these notes contains visible and hidden watermarks linked to the
07

identity of the original buyer. If these notes are found with anyone other than
54

the registered buyer:

27

• Both the sender and the receiver will be held legally accountable.
2

• A POLICE COMPLAINT and LEGAL PROCEEDINGS will be initiated against

both parties.

• No warnings or exceptions will be given.

Respect the hard work. Do not steal. Do not share.

2|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Unit – III
Graphs
This PDF is watermarked and traceable. Unauthorized sharing will result in
permanent access ban and legal action.

1. Basic Concepts
A graph is a non-linear data structure consisting of nodes (vertices) and edges (connections)
Ja

between them. It is used to represent relationships between objects, such as social networks,
road maps, or dependency graphs. In the field of sports data science, graph data structure can
im

be used to analyze and understand the dynamics of team performance and player interactions
il

on the field.
Pa
te
l-
+9
18
78
07

Components of a Graph
54

1. Vertices (Nodes): The fundamental units of a graph, represented as V.

27

2. Edges: The connections between nodes, represented as E.

2

A graph is represented as G(V, E) where:

• V = Set of vertices

• E = Set of edges

Types of Graphs

1. Null Graph: A graph is known as a null graph if there are no edges in the graph.
3|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

2. Trivial Graph: Graph having only a single vertex, it is also the smallest graph possible.

3. Undirected Graph: A graph in which edges do not have any direction. That is the nodes are
Ja

unordered pairs in the definition of every edge.

im
il
Pa
te
l-

4. Directed Graph: A graph in which edge has direction. That is the nodes are ordered pairs
+9

in the definition of every edge.

18
78
07
54
27

5. Connected Graph: The graph in which from one node we can visit any other node in the
2

graph is known as a connected graph.

4|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

6. Disconnected Graph: The graph in which at least one node is not reachable from a node is
known as a disconnected graph.

7. Regular Graph: The graph in which the degree of every vertex is equal to K is called K
Ja

regular graph.
im
il
Pa
te
l-
+9

8. Complete Graph: The graph in which from each node there is an edge to each other node.
18
78
07
54

9. Cycle Graph: The graph in which the graph is a cycle in itself, the minimum value of degree
27

of each vertex is 2.
2

10. Cyclic Graph: A graph containing at least one cycle is known as a Cyclic graph.
5|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

11. Directed Acyclic Graph: A Directed Graph that does not contain any cycle.
Ja
im
il

12. Bipartite Graph: A graph in which vertex can be divided into two sets such that vertex in
Pa

each set does not contain any edge between them.

te
l-
+9
18
78
07

13. Weighted Graph: A graph in which the edges are already specified with suitable weight is
54

known as a weighted graph.

27
2
6|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

14. Multigraph: A graph in which multiple edges may connect the same pair of vertices is
called a multigraph.
Ja
im

Properties of Graphs
il

𝑛(𝑛−1)
1. Complete Graph: If an undirected graph of n vertices consists of number of edges,
2
Pa

then that graph is called a complete graph.

te
l-
+9
18
78

2. Subgraph: A subgraph G’ of graph G is a graph such that the set of vertices and set of edges
07

of G’ are proper subset of the set of edges of G.

54
27
2

3. Connected Graph: An undirected graph is said to be connected if for every pair of distinct
vertices Vi and Vj in V(G) there is an edge Vi to Vj in G.
7|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

For example:

• V1 – V2
• V1 – V2 – V4
Ja

• V1 – V3
im

4. Degree, in-degree and out-degree: The degree of vertex is the number of edges associated
il

with the vertex. In-degree of a vertex is the number of edges that are incident on that vertex.
Pa

Out-degree of the vertex is total number of edges that are going away from the vertex.
te

Vertices Degree In-degree Out-degree

l-

V1 2 1 1
V2 3 2 1
+9

V3 2 1 1
18

V4 3 1 2
78
07

5. Self-loop: An edge that connects the same vertex, to itself.

54

6. Path: A path is denoted using sequence of vertices and there exists an edge from one vertex
to the next vertex. Path of the following graph is 1-2-3-4-5
27
2

7. Cycle: A closed walk through the graph with repeated vertices, mostly having the same
starting and ending vertex is called a cycle.
8|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

8. Component: The maximal connected subgraph of a graph is called component of a graph.

Following are 3 components of a graph:
Ja
im
il
Pa
te
l-

Comparison between Graph and Tree

+9

Feature Graph Tree

18

Definition A collection of nodes (vertices) A special type of graph with a

78

connected by edges. hierarchical structure.

Structure Can be cyclic or acyclic. Always acyclic (no loops/cycles).
07

Hierarchy No strict parent-child relationship. Has a strict parent-child relationship.

54

Connectivity Can be connected or disconnected. Always connected (except for forest).

27

Edges Can have multiple edges and Only one edge between any two nodes
loops. (no loops).
2

Root Node No root node. Has a root node at the top.

Traversal DFS, BFS. DFS (Preorder, Inorder, Postorder),
BFS (Level Order).
Usage Networks, social media, shortest Hierarchical data, file systems,
path problems, etc. databases, etc.
9|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Applications of Graphs

1. Google Maps & GPS Navigation → Graphs help find the shortest route between
locations using algorithms like Dijkstra’s.

2. Social Networks (Facebook, LinkedIn, Twitter) → Users are nodes, and connections
are edges, helping in friend suggestions and network analysis.

3. Computer Networks & Internet Routing → Graphs model network topology for
routing protocols like OSPF & BGP.

4. AI & Game Development (Pathfinding) → Games use A* and BFS/DFS for character
Ja

movement and decision-making.

im

5. Task Scheduling & Dependency Management → Graphs (DAGs) help schedule

il

tasks in project management & CPU scheduling.

Pa

1.1 Storage Representation

te

There are multiple ways to store a graph: The following are the most common representations.
l-

• Adjacency Matrix
+9

• Adjacency List
18

1.2 Adjacency Matrix

78

Adjacency Matrix is a square matrix used to represent a finite graph by storing the relationships
07

between the nodes in their respective cells. For a graph with V vertices, the adjacency matrix
54

A is a V × V matrix or 2D array.
27

Properties of Adjacency Matrix

2

• Diagonal Entries: The diagonal entries A[i][j] are usually set to 0 (in case of
unweighted) and INF in case of weighted, assuming the graph has no self-loops.

• Undirected Graphs: For undirected graphs, the adjacency matrix is symmetric. This
means A[i][j] = A[j][i] for all i and j.

1. Adjacency Matrix for Undirected and Unweighted graph:

• A[i][j] = 1, there is an edge between vertex i and vertex j.

• A[i][j] = 0, there is NO edge between vertex i and vertex j.

10 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

2. Adjacency Matrix for Undirected and Weighted graph:

• A[i][j] = INF, when there is no edge between vertex i and j

Ja

• A[i][j] = w, when there is an edge between vertex i and j having weight = w.

im
il
Pa
te
l-
+9
18

3. Adjacency Matrix for Directed and Unweighted graph:

78

• A[i][j] = 1, there is an edge from vertex i to vertex j

07

• A[i][j] = 0, No edge from vertex i to j.

54
27
2

4. Adjacency Matrix for Directed and Weighted graph:

• A[i][j] = INF, then there is no edge from vertex i to j

• A[i][j] = w, then there is an edge from vertex i having weight w

11 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

1.3 Adjacency List

Ja

An adjacency list is a data structure used to represent a graph where each node in the graph
im

stores a list of its neighboring vertices.

il

Characteristics of the Adjacency List:

Pa

• An adjacency list representation uses a list of lists. We store all adjacent of every node
te

together.
l-

• The size of the list is determined by the number of vertices in the graph.
+9

• All adjacent of a vertex are easily available. To find all adjacent, we need only O(n)
18

time where is the number of adjacent vertices.

78

1. Adjacency List for Directed and Unweighted graph:

07
54
27
2

2. Adjacency List for Undirected and Unweighted graph:

12 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

3. Adjacency List for Directed and Weighted graph:

4. Adjacency List for Undirected and Weighted graph:

Ja
im
il
Pa
te
l-

1.4 Adjacency Multi List

+9

An Adjacency Multi List is a graph representation that is a mix of adjacency list and edge
list, mainly used for undirected graphs. It efficiently stores edges while allowing easy
18

traversal of both vertices and edges.

78

The node structure is as follows:

07
54
27

Here M is a one-bit field that is used to represent whether the edge is visited or not.
2

Here the edges are (1, 2), (1, 4), (2, 3), (2, 4) and (3, 4). These edges are represented as nodes.
The vertices are 1, 2, 3, 4.
13 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

In node N1, the edge (1, 2) is specified. Third field N2 is for edge (1, 4), this link is the adjacent
edge of edge (1, 2) considering vertex V1, i.e., 1 forth-field-N3 is for edge (2, 3), this link is
Ja

the adjacent edge of edge (1, 2) considering vertex V2 i.e. 2.

im

In this way remaining nodes N2, N3, N4 and N5 are created.

il

Now vertex 1 is connected to (1, 2) and (1, 4) i.e. N1, N2.

Pa

Similarly, vertex 2 is connected to (1, 2), (2, 3) and (2, 4) i.e. N2, N3 and N4
te

Vertex 1: N1 → N2
l-

Vertex 2: N2 → N3 → N4
+9

Vertex 3: N3 → N5
18

Vertex 4: N2 → N4 → N5
78

1.5 Inverse Adjacency List

07

An Inverse Adjacency List is a variation of the adjacency list used for directed graphs.
54

Instead of storing outgoing edges (as in a standard adjacency list), it stores incoming edges for
27

each vertex.
2
14 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Q. Draw any directed graph with minimum 6 nodes and represent graph using adjacency
matrix, adjacency list, adjacency multilist and inverse adjacency list.

i) Adjacency Matrix
Ja

0 1 2 3 4 5
im

0 0 0 1 0 0 0
1 1 0 0 0 0 0
il

2 0 0 0 1 0 0
Pa

3 0 1 0 0 1 1
te

4 0 0 0 0 0 0
l-

5 0 0 0 0 0 0
+9
18

ii) Adjacency List

78
07
54
27
2

iii) Adjacency Multi List

Edge 1 1 0 Edge 3 NULL edge (1, 0)

Edge 2 0 2 NULL NULL edge (0, 2)

Edge 3 3 1 Edge 4 NULL edge (3, 1)

Edge 4 2 3 NULL NULL edge (2, 3)

15 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Edge 5 3 4 NULL NULL edge (3, 4)

Edge 6 3 5 NULL NULL edge (3, 5)

In above multilist various edges are represented. In the node of edge 1, the edge (1, 0) is
represented. For vertex 1, the incident edge is E3. Hence, we enter ‘Edge 3’ in the fourth field.
For vertex 0, the incident edge is E1 itself. So, we need not have to mention this self-defining
edge. So, we enter NULL in fifth field.

Again, for Edge 2, for vertex 0 the incident edge is 1 – 0 (Edge 1) but this edge is already
defined. Hence, we mention NULL in 4th field of Edge 2.
Ja

iv) Inverse Adjacency List

im
il
Pa
te
l-
+9
18
78
07
54
27
2

2. Traversals

2.1 Depth First

DFS (Depth-First Search) is a graph traversal algorithm that explores as far as possible along
each branch before backtracking. It uses recursion (or a stack in an iterative approach) to visit
nodes.

DFS for a Graph (Recursive):

Recursive DFS Algorithm

16 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

1. Maintain a boolean visited array to track visited nodes.

2. Start DFS from a source node and call dfsRec().

3. In dfsRec() function:

o Mark the node as visited.

o Process the node (e.g., print/store).

o Recursively call dfsRec() for all unvisited neighbors.

4. Backtrack when all neighbors are visited.

Ja

Recursive DFS C++ Function

im

void DFSRec(vector<int> adj[], bool visited[], int node) {

il

// Step 1: Mark node as visited

Pa

visited[node] = true;
te
l-

// Step 2: Process node (print/store)

+9

cout << node << " ";

18

// Step 3: Recursively visit all unvisited neighbors

78

for (int neighbor : adj[node]) {

07

if (!visited[neighbor]) {
DFSRec(adj, visited, neighbor);
54

}
27

}
2

// Function to handle multiple components

void DFS(vector<int> adj[], int V) {
bool visited[V] = {false}; // Initialize visited array

for (int i = 0; i < V; i++) { // Loop for disconnected graphs

if (!visited[i]) {
17 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

DFSRec(adj, visited, i);

}
}
}
Let us understand the working of Depth First Search with the help of the
following Illustration: for the source as 0.

Step 1: Start with a visited[] array to mark which spots (nodes) we've seen.
Ja
im
il
Pa
te
l-

Step 2: Iteration 1: DFSRec(adj, visited, 0), Marks visited[0] = true.

+9
18
78
07
54
27

Step 3: Iteration 2: DFSRec(adj, visited, 1), Marks visited[1] = true.

2
18 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 4: Iteration 3: DFSRec(adj, visited, 2), Marks visited[2] = true

Step 5: Iteration 4: DFSRec(adj, visited, 3), Marks visited[3] = true

Ja
im
il
Pa
te
l-
+9
18

Step 6: Iteration 4: DFSRec(adj, visited, 3), Marks visited[3] = true

78
07
54
27
2

Step 7: Backtracking from 4

19 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 8: Backtracking from 2

Ja
im
il
Pa
te
l-
+9

Step 9: Backtracking from 1

18
78
07
54
27
2

Step 10: DFS from source: 0

0→1→2→3→4
20 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

DFS for a Graph (Non-Recursive/Iterative):

Ja

Non-Recursive DFS Algorithm

im

1. Initialize a boolean visited array to track visited nodes.

il

2. Use a stack to manage the traversal order.

Pa

3. Push the starting node onto the stack and mark it as visited.
te

4. While the stack is not empty:

l-

o Pop a node and process it.

+9

o Push all unvisited neighbors onto the stack and mark them as visited.
18

5. Repeat until all nodes are visited.

78

Non-Recursive DFS C++ Function

07

void DFSIterative(vector<int> adj[], int V, int start) {

54

stack<int> s; // Stack for DFS

27

bool visited[V] = {false}; // Visited array

2

s.push(start); // Push starting node

visited[start] = true; // Mark it as visited

while (!s.empty()) {
int node = s.top(); // Get the top node
s.pop(); // Remove it from stack
cout << node << " "; // Process the node
21 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

// Push unvisited neighbors onto the stack

for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
s.push(neighbor);
visited[neighbor] = true; // Mark as visited
}
}
}
Ja

}
im

Example: For the graph given below, find DFS stepwise.

il
Pa
te
l-
+9
18

We first create adjacency list for given graph:

78
07
54
27
2
22 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 1: Start with vertex a, mark it visited by writing 1 to index ‘a’ of visited array. Then print
a as an output.

Stack Visited Array Output

a 1 a
b
c
d
e
Ja

f
im

g
il
Pa

Step 2: Find adjacent of a, and mark it visited. Push it onto the stack. Later b will be popped
te

and printed.
l-

Stack Visited Array Output

+9
18

a 1 a, b
78

b 1
b c
07

d
54

e
f
27

g
2

Step 3: Find adjacent of b. The a is already visited, hence ignore. Next node will be c. Insert c
onto the stack, mark it as visited. Push it. Later c will be popped and printed.
23 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Stack Visited Array Output

a 1 a, b, c
b 1
c c 1
d
e
f
g
Ja
im

Step 4: Find adjacent of c. Push d, mark it visited. Later d will be popped and printed.
il

Stack Visited Array Output

Pa
te

a 1 a, b, c, d
l-

b 1
d c 1
+9

d 1
18

e
78

f
g
07
54

Step 5: Find adjacent of d. Push f, mark it as visited. Later f will be popped and printed
27

Stack Visited Array Output

2

a 1 a, b, c, d, f
b 1
f c 1
d 1
e
f 1
g
24 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 6: Find adjacent of f. Push e, mark it as visited. Later e will be popped and printed

Stack Visited Array Output

a 1 a, b, c, d, f, e
b 1
e c 1
d 1
e 1
f 1
Ja

g
im
il

Step 7: Find adjacent of e. Push g, mark it as visited. Later g will be popped and printed
Pa

Stack Visited Array Output

te

a 1
l-

a, b, c, d, f, e, g
b 1
+9

g c 1
18

d 1
e 1
78

f 1
07

g 1
54
27

As all nodes are visited, and stack is empty, we stop traversing.

2

The DFS sequence is a, b, c, d, f, e, g

Applications of DFS:

1. Cycle Detection → Detects cycles in both directed and undirected graphs.

2. Topological Sorting → Used in task scheduling for dependency resolution.

3. Strongly Connected Components (SCCs) → Finds SCCs in directed graphs

(Kosaraju’s Algorithm).
25 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

4. Maze & Pathfinding → Helps navigate mazes and find paths in AI/game development.

5. Articulation Points & Bridges → Identifies critical points in a network (Tarjan’s

Algorithm).

2.2 Breadth First

Breadth-First Search (BFS) is a graph traversal algorithm that explores all neighbors of a
node before moving to the next level. It follows a queue-based approach and ensures nodes
are visited in increasing order of their distance from the starting node.

Algorithm for BFS

Ja

1. Initialize a queue and enqueue the starting node.

im

2. Mark the starting node as visited.

il
Pa

3. While the queue is not empty:

te

o Dequeue a node from the queue.

l-

o Process the node (print/store it).

+9

o Enqueue all unvisited adjacent nodes and mark them as visited.

18

4. Repeat until all reachable nodes are visited.

78

C++ Pseudocode for BFS

07

void BFS(vector<int> adj[], int start, int n) {

54

vector<bool> visited(n, false); // Mark all nodes as unvisited

queue<int> q;
27
2

visited[start] = true; // Mark start node as visited

q.push(start);

while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " "; // Process the node
26 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

// Traverse all adjacent nodes

for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true; // Mark as visited
q.push(neighbor);
}
}
}
}
Ja

Example: For the graph given below, find BFS:

im
il
Pa
te
l-
+9
18

We will first create an adjacency list for given graph:

78
07
54
27
2
27 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 1: Insert a in queue. Mark visited (a) = 1.

Queue Visited Array Output

a 1
a
b
c
d
e
f
Ja

g
im

Step 2: Delete a and print.

il
Pa

Queue Visited Array Output

te

a 1
a
l-

b
c
+9

d
18

e
78

f
g
07
54

Step 3: Find adjacent of a and insert them in a queue. Mark proper adjacent nodes as visited.
27

Queue Visited Array Output

2

a 1
b e g a
b 1
c
d
e 1
f
g 1
28 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 4: Delete b and print. Find adjacent of b and if those nodes are not visited then insert them
in the queue. Mark corresponding nodes as visited.

Queue Visited Array Output

a 1
e g c a, b
b 1
c 1
d
e 1
Ja

f
im

g 1
il
Pa

Step 5: Delete e and print. Find adjacent of e and if those nodes are not visited then insert them
in a queue. Mark corresponding nodes as visited.
te
l-

Queue Visited Array Output

+9

a 1
g c f a, b, e
18

b 1
c 1
78

d
07

e 1
54

f 1
g 1
27
2

Step 6: Delete g and print. Find adjacent of g and if those nodes are not visited then insert them
in a queue. Mark corresponding nodes as visited.
29 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Queue Visited Array Output

a 1
c f d a, b, e, g
b 1
c 1
d 1
e 1
f 1
g 1
Ja

Step 7: Delete c and print. Find adjacent of c and if those nodes are not visited then insert them
im

in a queue. Mark corresponding nodes as visited.

il

Queue Visited Array Output

Pa

a 1
te

f d a, b, e, g, c
b 1
l-

c 1
+9

d 1
e 1
18

f 1
78

g 1
07

Step 8: Delete f and print. Find adjacent of f and if those nodes are not visited then insert them
54

in a queue. Mark corresponding nodes as visited.

27

Queue Visited Array Output

2

a 1
d a, b, e, g, c, f
b 1
c 1
d 1
e 1
f 1
g 1
30 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 9: Delete d and print. Find adjacent of d and if those nodes are not visited then insert them
in a queue. Mark corresponding nodes as visited.

Queue Visited Array Output

a 1
a, b, e, g, c, f, d
b 1
c 1
d 1
e 1
Ja

f 1
im

g 1
il

Step 10: As queue is empty, and all entries in the visited array are visited, then stop. At display
Pa

we get the BFS sequence.

te

BFS Sequence is a, b, e, g, c, f, d.
l-

Applications of BFS
+9

1. Shortest Path in an Unweighted Graph → Finds the shortest path between two nodes.
18

2. Connected Components in an Undirected Graph → Identifies distinct connected

78

components.
07

3. Bipartite Graph Checking → Determines if a graph can be colored with two colors.
54

4. Network Broadcasting → Used in computer networks for spreading information.

27

5. Web Crawling → Used by search engines to index web pages.

2

2.3 Minimum Spanning Tree

A Minimum Spanning Tree (MST) of a graph is a subset of edges that:

1. Connects all vertices in the graph.

2. Has no cycles (i.e., it forms a tree).

3. Has the minimum possible total edge weight among all spanning trees.

It applies to weighted, connected, and undirected graphs.

31 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

2.4 Greedy Algorithms for Computing Minimum Spanning Tree (MST)

The Greedy technique is an algorithmic method for obtaining optimized solution for a given
Ja

problem. For example, for obtaining the shortest path from source vertex to a destination vertex
im

within a graph – we use greedy technique.

il

The Greedy technique is applied to find out minimum spanning tree in a graph.
Pa

Two well-known greedy algorithms are used to compute an MST:

te

1. Prim’s and Kruskal’s Algorithms

l-

Prim’s Algorithm: In Prim’s Algorithm, the pair with the minimum weight is to be chosen.
+9

Then adjacent to these vertices whichever is the edge having minimum weight is selected. This
18

process will be continued till all the vertices are not covered. The necessary condition in this
case is that the circuit should not be formed.
78

Prim's Algorithm/Pseudocode for Minimum Spanning Tree

07

Prim(Graph, V):
54

// Step 1: Initialize arrays

27

key[V] = INF // key[i] = minimum weight to connect i to the MST

2

parent[V] = -1 // parent[i] = node that connects i to MST

inMST[V] = false // inMST[i] = true if i is already in MST

key[0] = 0 // Start from vertex 0

// Step 2: Loop V times to include all vertices in MST

for count = 0 to V - 1:
32 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

// Step 3: Pick the vertex u with the minimum key[] value not
in MST
u = vertex with min key[u] such that inMST[u] == false
inMST[u] = true // Include u in MST

// Step 4: Update key and parent for adjacent vertices of u

for each neighbor v of u:
weight = weight of edge (u, v)
if inMST[v] == false and weight < key[v]:
Ja

key[v] = weight
im

parent[v] = u
il

// Step 5: parent[] contains the MST

Pa

print "Edges in MST:"

te

for i = 1 to V - 1:
l-

print parent[i], "->", i, "with weight", key[i]

+9

Q. For the graph given below, construct a minimum spanning tree using Prim’s algorithm.
Show the table created during each pass of the algorithm.
18
78
07
54
27
2

In Prim’s algorithm the minimum path length is selected. We only need to make sure that the
circuit should not be formed.

Step 1: Path length = 1

33 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 2: Path length = 3

Step 3: Path length = 5

Ja
im
il

Step 4: Path length = 9

Pa
te
l-
+9
18
78

Step 5: Path length = 10

07
54
27

Step 6: Path length = 16

2

Thus, the minimum spanning tree with path length 16 is obtained.

2. Kruskal’s Algorithm: In Kruskal’s algorithm, the minimum weight is obtained. In this

algorithm, just like Prim’s, circuit should not be formed. Each time the edge of minimum
34 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

weight has to selected from the graph. It’s not necessary in this algorithm to have edges of
minimum weights to be adjacent.

Kruskal’s Algorithm/Pseudocode for Minimum Spanning Tree

Kruskal(Graph, V):
// Step 1: Create a list of all edges and sort them by weight
edges = list of all edges in the form (u, v, weight)
sort(edges by increasing weight)
Ja

// Step 2: Initialize Disjoint Set (Union-Find)

im

parent[V] = {0, 1, 2, ..., V-1} // Each node is its own parent

rank[V] = array of 0 // Used to optimize union operation
il
Pa

MST = empty list // Final list of edges in the Minimum

te

Spanning Tree
l-

// Step 3: Process each edge in sorted order

+9

for each edge (u, v, weight) in edges:

18

if findParent(u) != findParent(v): // If u and v are

in different sets
78

MST.add(edge) // Include edge in MST

07

union(u, v) // Merge the sets

54

// Step 4: MST is complete when it has (V - 1) edges

27

return MST
2

// Helper function: Find the representative parent of a node

findParent(x):
if parent[x] != x:
parent[x] = findParent(parent[x]) // Path compression
return parent[x]

// Helper function: Union of two sets by rank

35 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

union(x, y):
rootX = findParent(x)
rootY = findParent(y)

if rank[rootX] < rank[rootY]:

parent[rootX] = rootY
else if rank[rootX] > rank[rootY]:
parent[rootY] = rootX
else:
Ja

parent[rootY] = rootX
im

rank[rootX]++
il

Q. Obtain Minimum Spanning Tree by Kruskal’s algorithm for the following graph:
Pa
te
l-
+9
18
78

Step 1: Select an edge gf with weight 5.

07
54
27
2

Step 2: Select an edge ed with weight 7.

36 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 3: Select an edge eh with weight 18.

Ja
im
il
Pa
te
l-
+9

Step 4: Select an edge bc with weight 20.

18
78
07
54
27
2

Step 5: Select an edge ab with weight 30.

37 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Step 6: Select an edge hg with weight 17.

Ja
im
il
Pa
te
l-
+9

Step 7: Select an edge ce with weight 29.

18
78
07
54
27

The minimum spanning tree has the weight 121.

2

Comparison between Prim’s and Kruskal’s Algorithm

Feature Prim’s Algorithm Kruskal’s Algorithm

Approach Expands MST from a node Builds MST using sorted edges
Works best for Dense graphs Sparse graphs
Data Structure Priority queue (min heap) Disjoint Set (Union-Find)
Complexity O(v2) (Adj. Matrix) / O(E log V) O (E log E)
(heap)
38 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

2. Dikjstra's Single Source Shortest Path

Dijkstra’s Algorithm is used to find the shortest path from a single source vertex to all other
vertices in a weighted graph (with non-negative weights). It works by iteratively selecting the
vertex with the minimum distance and updating the distances of its neighboring vertices.

Algorithm/Pseudocode for Dikjstra's Single Source Shortest Path

Dijkstra(Graph, source, V):

// Step 1: Initialize distance array and visited array
dist[V] = array filled with INF // dist[i] holds the
Ja

shortest distance from source to i

im

visited[V] = array filled with false // visited[i] tracks

whether node i is finalized
il

dist[source] = 0 // Distance from source to itself is 0

Pa
te

// Step 2: Repeat V-1 times (for all vertices)

for count = 0 to V - 1:
l-

// Step 3: Pick the unvisited node with the smallest distance

+9

u = node with minimum dist[u] where visited[u] == false

18

visited[u] = true // Mark this node as visited

78

// Step 4: Update distances of all adjacent unvisited

07

neighbors
54

for each neighbor v of u:

if visited[v] == false and dist[u] + weight(u, v) <
27

dist[v]:
2

dist[v] = dist[u] + weight(u, v) // Relax the edge

// Step 5: After all vertices are processed, dist[] contains

shortest distances
for i = 0 to V - 1:
print "Shortest distance from", source, "to", i, "=", dist[i]
39 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Q. Find the shortest path in the following graph from node A, using Dijkstra’s Algorithm.

Formula: dist(v) = min(dist(v), dist(u) + weight(u,v))

Ja

Consider source vertex A.

im

S = {A}, T = {B, C, D, E}
il

L(B) = min{∞, 0 + 10} = 10

Pa

L(C) = min{∞, 0 + ∞} = ∞
te

L(D) = min{∞, 0 + ∞} = ∞
l-

L(E) = min{∞, 0 + 3} = 3 → shortest distance

+9

S = {A, E}, T = {B, C, D}

18

L(B) = min{∞, 3 + 1} = 4 → shortest distance

78

L(C) = min{∞, 3 + 8} = 11
07

L(D) = min{∞, 3 + 2} = 5
54

S = {A, E, B}, T = {C, D}

27

L(E) = min{∞, 4 + 2} = 6
2

L(D) = min{∞, 3 + 2} = 5 → shortest distance

S = {A, E, B, D}, T = {C}

L(C) = min{∞, 4 + 2} = 6 → shortest distance

Thus we obtain shortest paths from node A as follows:

• d(A, B) = 4 A-E-B • d(A, D) = 5 A-E-D

• d(A, C) = 6 A-E-B-C • d(A, E) = 3 A-E
40 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

2.5 All Pairs Shortest Paths

1. Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming algorithm used to find the

shortest paths between all pairs of vertices in a weighted graph (both directed and
undirected). It works efficiently even with negative weights (but no negative cycles).

Key Features:

• All-Pairs Shortest Path Algorithm: Finds the shortest paths between every pair of
vertices.
Ja

• Works with Negative Weights: Unlike Dijkstra’s algorithm, it handles graphs with
im

negative weights but not negative cycles.

il

• Dynamic Programming Approach: It gradually improves path estimates by

Pa

considering intermediate vertices.

te

• Time Complexity: O(V³), where V is the number of vertices.

l-

• Space Complexity: O(V²) (stores the shortest path matrix).

+9

Algorithm/Pseudocode:
18

Algorithm FloydWarshall(dist[][], n)
78

{
07

// Step 1: Iterate over all possible intermediate vertices (k)

54

for k from 0 to n-1 do

{
27

// Step 2: Iterate over all pairs of vertices (i, j)

2

for i from 0 to n-1 do

{
for j from 0 to n-1 do
{
// Step 3: Update dist[i][j] if a shorter path exists
through vertex k
if dist[i][j] > dist[i][k] + dist[k][j] then
dist[i][j] = dist[i][k] + dist[k][j]
41 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

}
}
}

// Step 4: Return the updated distance matrix containing shortest

paths
return dist
}
Q. Find the shortest path between all the pairs of vertices from the given graph using
Ja

Floyd-Warshall Algorithm.
im
il
Pa
te
l-
+9
18
78
07

1. Create a matrix A0 of dimension n*n where n is the number of vertices. The row and the
54

column are indexed as i and j respectively. i and j are the vertices of the graph.
27

Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex. If there is
no path from ith vertex to jth vertex, the cell is left as infinity.
2

A0 =
42 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Formula: A[i][j] = min(A[i][j], A[i][k]+A[k][j])

Create a matrix A1 using matrix A0. The elements in the first column and the first row are left
as they are. Let k be the intermediate vertex in the shortest path from source to destination.
Here, k = A. The remaining cells are filled in the following way. Examples:

A1[C][B] = min(A0[C][B], A0[C][A] + A0[A][B]) = min(∞, 2+4) = 6

A1[E][B] = min(A0[E][B], A0[E][A] + A0[A][B]) = min(∞, 1+4) = 5

Ja
im

A1 =
il
Pa
te
l-

To find A2: A2 =
+9

Here, k = B
18
78
07

To find A3: A3 =
54
27

Here, k = C
2

To find A4: A4 =

Here k = D
43 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

To find A5: A5 =

Here k = E

2. Topological Ordering

This algorithm is a direct implementation of the Decrease and Conquer method. The steps
involved are as follows:
Ja

1. Identify a vertex in the given graph that has no incoming edges. Remove this vertex
im

along with all its outgoing edges. If multiple such vertices exist, choose one randomly.
il

2. Record the deleted vertices in the order they are removed.

Pa

3. The sequence of recorded vertices forms the topologically sorted order of the graph.
te

TopologicalSort_Kahn(Graph):
l-

// Step 1: Calculate in-degree of each node

+9

in_degree = dict with 0 for all nodes

18

for each node in Graph:

for each neighbor in node's adjacency list:
78

in_degree[neighbor] += 1
07
54

// Step 2: Enqueue all nodes with in-degree 0

queue = empty queue
27

for each node in Graph:

2

if in_degree[node] == 0:
queue.enqueue(node)

// Step 3: Initialize list to store topological order

topo_order = []

// Step 4: Process nodes in queue

while queue is not empty:
44 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

current = queue.dequeue()
topo_order.append(current)

// Step 5: Decrease in-degree of neighbors

for each neighbor of current:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.enqueue(neighbor)
Ja

// Step 6: Check for cycles (if all nodes were not processed)
im

if length of topo_order != total number of nodes:

il

print("Cycle detected – topological sort not possible")

Pa

else:
print(topo_order)
te

Q. Find the topological sorting of the given graph:

l-
+9
18
78
07
54

Step 1: Choose vertex ‘1’ as it has no incoming edge. Delete it along with its adjacent-edges.
27

Delete 1:
2
45 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Delete 3:

Delete 2 or 4:
Ja
im
il
Pa
te

Delete 4 or 2:
l-
+9
18
78
07

Delete 6:
54
27
2

Delete 5:

Delete 7.

The various topological sorting will be:

• 1, 3, 2, 4, 6, 5, 7
• 1, 3, 4, 2, 6, 5, 7