20-10-2024

SYLLABUS
UNIT 1: Data Structures and Algorithms Basics (8 Hours)
Introduction: Basic terminologies, elementary data organizations, data structure operations;
abstract data types (ADT) and their characteristics.
Algorithms: Definition, characteristics, analysis of an algorithm, asymptotic notations, time
and space trade-offs.
Array ADT: Definition, operations and representations – row-major and column- major.

UNIT 2: Sorting, Searching and Hashing (10 Hours)

Sorting: Different approaches to sorting, properties of different sorting algorithms (insertion,
Shell, quick, merge, heap, counting), performance analysis and comparison.
Searching: Necessity of a robust search mechanism, searching linear lists (linear search,
binary search) and complexity analysis of search methods.
Hashing: Hash functions and hash tables, closed and open hashing, randomization methods
(division method, mid-square method, folding), collision resolution techniques.
1

SYLLABUS Text/Reference Books

UNIT 3: Stacks and Queues (8 Hours)
Stack ADT: Allowable operations, algorithms and their complexity analysis, applications of stacks–expression
1. G.A.V. Pai, Data Structures and Algorithms: Concepts, Techniques and Application, First
conversion and evaluation (algorithmic analysis), multiple stacks. Edition, McGraw Hill, 2017.
Queue ADT: Allowable operations, algorithms and their complexity analysis for simple queue and circular 2. Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed, Fundamentals of Data Structures
queue, introduction to double-ended queues and priority queues. in C, Second Edition, Universities Press, 2008.
3. Mark Allen Weiss, Data Structures and Algorithm Analysis in C, Third Edition, Pearson
UNIT 4: Linked Lists (10 Hours)
Singly Linked Lists: Representation in memory, algorithms of several operations: traversing, searching,
Education, 2007.
insertion, deletion, reversal, ordering, etc. 4. Thomas H Cormen, Algorithms Unlocked, MIT Press, 2013
Doubly and Circular Linked Lists: Operations and algorithmic analysis. 5. Reema Thareja, Data Structures using C, Third Edition, Oxford University Press, 2023
Linked representation of stacks and queues. 6. Narasimha Karumanchi, Data Structures and Algorithms Made Easy: Data Structures and
Algorithmic Puzzles Fifth Edition, Career Monk Publications, 2016.
UNIT 5: Trees and Graphs (8 Hours)
Trees: Basic tree terminologies, binary tree and operations, binary search tree (BST) and operations with time
7. Aditya Bhargava, Grokking Algorithms: An Illustrated Guide for Programmers and Other
analysis of algorithms, threaded binary trees. Curious People, First Edition, Manning Publications, 2016.
Self-balancing Search Trees: Tree rotations, AVL tree and operations, 8. K. R. Venugopal and Sudeep R. Prasad, Mastering C, Second Edition, McGraw Hill,
Graphs: Basic terminologies, representation of graphs, traversals (DFS, BFS) with complexity analysis, path 2015.
finding (Dijkstra's SSSP, Floyd's APSP), and spanning tree (Prim's and Kruskal's algorithms). 9. A. K. Sharma, Data Structures using C, Second Edition, Pearson Education, 2013.

1
 20-10-2024

Course Outcomes

On completion of the course the student will be able to

1. Identify different ADTs, their operations and specify their
complexities.
2. Apply linear data structures to address practical challenges and
analyze their complexity.
3. Implement different sorting, searching, and hashing methods and
analyze their time and space requirements.
4. Analyse non-linear data structures to develop solutions for real-
world applications.

Graph Definition Graph Example

• A graph is simply a collection of nodes plus edges • Here is a directed graph G = (V, E)
• Linked lists, trees, and heaps are all special cases of graphs • Each edge is a pair (v1, v2), where v1, v2 are vertices in V
• The nodes are known as vertices (node = “vertex”) • V = {A, B, C, D, E, F}
• Formal Definition: A graph G is a pair (V, E) where • E = {(A,B), (A,D), (B,C), (C,D), (C,E), (D,E)}
• V is a set of vertices or nodes
• E is a set of edges that connect vertices
B Disjoint Node
Node/ Vertex C
A
Edge F
D E
10/20/2024 7 10/20/2024 8

2
 20-10-2024

Directed vs Undirected Graphs Undirected Graph Terminology

B is adjacent to C and C is adjacent to B
• If the order of edge pairs (v1, v2) matters, the graph is directed (also called
a digraph): (v1, v2)  (v2, v1) Edge [A,B] is incident to A and to B B
Self-loop
C
v1 v2
A
F
• If the order of edge pairs (v1, v2) does not matter, the graph is called an
undirected graph: in this case, (v1, v2) = (v2, v1) D E Degree = 0

Degree = 3

v1 v2 • Degree: The total number of edges connected to a vertex is said to be the

degree of that vertex.
10/20/2024 9 10/20/2024 10

Directed Graph Terminology Directed Terminology

• Vertex u is adjacent to vertex v in a directed graph G if (u,v) is an B adjacent to C and C adjacent from B
edge in G
v
• vertex u is the initial vertex of (u,v) z B
• Vertex v is adjacent from vertex u (u, v) C
• vertex v is the terminal (or end) vertex of (u,v) w A
• Degree u F
• in-degree is the number of edges with the vertex as the terminal vertex
D E
• out-degree is the number of edges with the vertex as the initial vertex In-degree = 0
Out-degree = 0
In-degree = 2
u and v are adjacent Out-degree = 1
v and w are not adjacent

10/20/2024 11 10/20/2024 12

3
 20-10-2024

Graph Representations Adjacency Matrix

• Space and time are analyzed in terms of: • 0/1 n x n matrix, where n = # of vertices
• A(i,j) = 1 iff (i,j) is an edge
• Number of vertices = |V| and
• Number of edges = |E| 1 2 3 4 5
2 0 1 0 1 0
3 1
• There are at least two ways of representing graphs:
2 1 0 0 0 1
• The adjacency matrix representation 1
0 0 0 0 1
3
• The adjacency list representation 4 4 1 0 0 0 1
5
5 0 1 1 1 0

10/20/2024 13

Adjacency Matrix Properties Adjacency Matrix

1 2 3 4 5

2 A B C D E F
1 0 1 0 1 0
3 B
2 1 0 0 0 1 C A 0 1 0 1 0 0
1 A
3 0 0 0 0 1 B 1 0 1 0 0 0
F
4 4 1 0 0 0 1 C 0 1 0 1 1 0
5 D E
5 0 1 1 1 0 D 1 0 1 0 1 0
E 0 0 1 1 0 0
1 if [v, w] is in E
•Diagonal entries are zero. M(v, w) =
0 otherwise F 0 0 0 0 0 0
•Adjacency matrix of an undirected graph is symmetric.
Space = |V|2
A(i,j) = A(j,i) for all i and j. 10/20/2024 16

4
 20-10-2024

Adjacency Matrix for a Digraph Adjacency Matrix Example

A B C D E F
B 0 1 0 1 0 0
C A
A
B 0 0 1 0 0 0
F C 0 0 0 1 1 0
D
E D 0 0 0 0 1 0
E
0 0 0 0 0 0
1 if (v, w) is in E
M(v, w) =
F
0 otherwise 0 0 0 0 0 0

Space = |V|2
10/20/2024 17 10/20/2024 18

Adjacency Lists Linked Adjacency Lists

• Adjacency list for vertex i is a linear list of vertices adjacent from vertex i. • Each adjacency list is a chain.
• An array of n adjacency lists.
2 aList[1] 2 4
3
[2] 1 5

1 [3] 5
2 aList[1] = (2,4) [4] 5 1
3
4 aList[5] 2 4 3
aList[2] = (1,5) 5
1
aList[3] = (5)
Array Length = n
4 aList[4] = (5,1) # of chain nodes = 2e (undirected graph)
5
aList[5] = (2,4,3) # of chain nodes = e (digraph)

5
 20-10-2024

Adjacency List Adjacency List for a Digraph

For each v in V, L(v) = list of w such that (v, w) is in E
For each v in V, L(v) = list of w such that [v, w] is in E
a b A a Bb D
B
A B list of C B
B D neighbors A C
C B C
A A C D E
F
C B D E D
F D E
D E E
E D A C E
E C D F
A is a source
F E is a sink
Space = a |V| + 2 b |E| Space = a |V| + b |E|
F is disconnected from the rest
10/20/2024 21 10/20/2024 22

Basic Terminology in a Graph Basic Terminology in a Graph

• Vertex: An individual data element of a graph is called Vertex. • Simple Graph: A graph is said to be simple if there are no parallel and self-loop edges.
• Edge: An edge is a connecting link between two vertices. An Edge is also known as Arc. • Directed acyclic graph (DAG): A directed acyclic graph (DAG) is a graph that is directed
• Mixed Graph: A graph with undirected and directed edges is said to be a mixed graph. and without cycles connecting the other edges. This means that it is impossible to traverse
• Origin: If an edge is directed, its first endpoint is said to be the origin of it. the entire graph starting at one edge.
• Destination: If an edge is directed, its first endpoint is said to be the origin of it and the • Weighted Graph: A weighted graph is a graph in which a number (known as the weight)
other endpoint is said to be the destination of the edge. is assigned to each edge. Such weights might represent for example costs, lengths or
• Adjacency: Two node or vertices are adjacent if they are connected through an edge. capacities, depending on the problem.
• Path: The Path represents a sequence of edges between the two vertices. • Complete Graph: A complete graph is a graph in which each pair of vertices is joined by
• Degree: The total number of edges connected to a vertex is said to be the degree of that an edge. A complete graph contains all possible edges.
vertex. • Connected graph: A connected graph is an undirected graph in which every unordered
• In-Degree: In-degree of a vertex is the number of edges which are coming into the vertex. pair of vertices in the graph is connected. Otherwise, it is called a disconnected graph.
• Out-Degree: Out-degree of a vertex is the number of edges which are going out from the • Minimum Spanning Tree (MST): A minimum spanning tree (MST) is a subset of the
vertex. edges of a connected, edge-weighted (un)directed graph that connects all the vertices,
without any cycles and with the minimum possible total edge weight.

6
 20-10-2024

Path and simple path

Adjacent
• A path from v1 to vk is a sequence of nodes v1, v2, …, vk that are connected
by edges (v1, v2), (v2, v3), …, (vk-1, vk)
• Two nodes u and v are said to be adjacent if (u, v)  E
• A path is called a simple path if every node appears at most once.

v
(u, v)
v2 v3
u - v2, v3, v4, v2, v1 is a path v1
w - v2, v3, v4, v5 is a path, also it is
u and v are adjacent
v and w are not adjacent a simple path
v4 v5

2024/10/20 25 2024/10/20 26

Cycle and simple cycle Connected graph

• A cycle is a path that begins and ends at the same node • A graph G is connected if there exists path between every pair of
• A simple cycle is a cycle if every node appears at most once, except distinct nodes; otherwise, it is disconnected
for the first and the last nodes
v2
v1 v3

v2 v5
- v2, v3, v4, v5 , v3, v2 is a cycle v1 v3 v4
- v2, v3, v4, v2 is a cycle, it is also
a simple cycle This is a connected graph because there exists path between every pair of nodes
v4 v5

2024/10/20 27 2024/10/20 28

7
 20-10-2024

Example of disconnected graph Connected component

• If a graph is disconnect, it can be partitioned into a number of graphs
such that each of them is connected. Each such graph is called a
v1 v3 v7 v8 connected component.
v2

v4 v5
v6 v2 v7 v8
v9 v1 v3

This is a disconnected graph because there does not exist path

v4 v5
between some pair of nodes, says, v1 and v7 v6 v9

2024/10/20 29 2024/10/20 30

Subgraph
Complete graph
• A subgraph of a graph G =(V, E) is a graph H = (U, F) such that
• A graph is complete if each pair of distinct nodes has an edge U  V and F  E.

v2 v2
v1 v3 v3

Complete graph with 3 nodes Complete graph with 4 nodes v4 v5 v4 v5

G H

2024/10/20 31 2024/10/20 32

8
 20-10-2024

Directed graph (digraph)

Weighted graph
• All previous graphs are undirected graph
• If each edge in G is assigned a weight, it is called a weighted graph
• If each edge in E has a direction, it is called a directed edge
• A directed graph is a graph where every edges is a directed edge

Chennai New Delhi

1000
Chennai New Delhi
1000
3500
2000
Directed edge
2000 3500

Hyderabad
Hyderabad
2024/10/20 33 2024/10/20 34

More on directed graph Multigraph

x y • A graph cannot have duplicate edges.
• Multigraph allows multiple edges and self edge (or loop).
• If (x, y) is a directed edge, we say
• y is adjacent to x
• y is successor of x
• x is predecessor of y
• In a directed graph, directed path, directed cycle can be defined similarly

Self edge Multiple edge

2024/10/20 35 2024/10/20 36

9
 20-10-2024

Graph Traversing Techniques Graph Traversing Techniques

BFS
(Use Queue,
followed by stack
for backtrack)

Write all nodes

and visit the next
node in queue
DFS
(Apply Stack)

Write one node available in stack

and visit the node in queue, Use
stack for backtrack.
2024/10/20 37 2024/10/20 38
38

Shortest path Formal definition of shortest path

• Consider a weighted directed graph • Given a weighted directed graph G.
• Each node x represents a city x • Let P be a path of G from x to y.
• Each edge (x, y) has a number which represent the cost of traveling from city x
to city y • cost(P) = ePweight(e)
• Problem: find the minimum cost to travel from city x to city y • The shortest path is a path P which minimizes cost(P)
• Solution: find the shortest path from x to y v2
v1 2 v3
5
4 3 Shortest Path
4
8 v5
v4
2024/10/20 39 2024/10/20 40

10
 20-10-2024

Dijkstra’s Algorithm Dijkstra’s Algorithm

• Classic algorithm for solving shortest path in weighted graphs (with only positive edge • Dijkstra's Algorithm basically starts at the node that you choose (the source
weights) node) and it analyzes the graph to find the shortest path between that node
• Similar to breadth-first search, but uses a priority queue instead of a FIFO queue: and all the other nodes in the graph.
• Always select (expand) the vertex that has a lowest-cost path to the start vertex • The algorithm keeps track of the currently known shortest distance from
• a kind of “greedy” algorithm each node to the source node and it updates these values if it finds a shorter
• Correctly handles the case where the lowest-cost (shortest) path to a vertex is not the one path.
with fewest edges
• Once the algorithm has found the shortest path between the source node and
another node, that node is marked as "visited" and added to the path.
• Consider a graph G, each edge (u, v) has a weight w(u, v) > 0.
• The process continues until all the nodes in the graph have been added to the
• Suppose we want to find the shortest path starting from v1 to any node vi
path.
• Let VS be a subset of nodes in G
• This way, we have a path that connects the source node to all other nodes
• Let cost[vi] be the weight of the shortest path from v1 to vi that passes through nodes in VS following the shortest path possible to reach each node.
only.
2024/10/20 41 2024/10/20 42

Dijkstra’s Algorithm Example for Dijkstra’s Algorithm Simulation

The following is the step that we will follow to implement Dijkstra's
Algorithm:
• Step 1: First, we will mark the source node with a current distance of 0 and set
the rest of the nodes to INFINITY.
• Step 2: We will then set the unvisited node with the smallest current distance
as the current node, suppose X.
• Step 3: For each neighbor N of the current node X: We will then add the
current distance of X with the weight of the edge joining X-N. If it is smaller
than the current distance of N, set it as the new current distance of N.
• Step 4: We will then mark the current node X as visited.
• Step 5: We will repeat the process from 'Step 2' if there is any node unvisited
left in the graph.
2024/10/20 43 2024/10/20 44

11
 20-10-2024

Example for Dijkstra’s Algorithm Example for Dijkstra’s Algorithm

v2 v2
v1 2 v3 v1 2 v3
5 5
4 3 4 3
4 4
8 v5 8 v5
v4 v4
v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5] v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5]
1 [v1] 0 5 ∞ ∞ ∞ 1 [v1] 0 5 ∞ ∞ ∞
2 v2 [v1, v2] 0 5 ∞ 9 ∞

2024/10/20 45 2024/10/20 46

Example for Dijkstra’s Algorithm Example for Dijkstra’s Algorithm

v2 v2
v1 2 v3 v1 2 v3
5 5
4 3 4 3
4 4
8 v5 8 v5
v4 v4
v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5] v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5]
1 [v1] 0 5 ∞ ∞ ∞ 1 [v1] 0 5 ∞ ∞ ∞
2 v2 [v1, v2] 0 5 ∞ 9 ∞ 2 v2 [v1, v2] 0 5 ∞ 9 ∞
3 v4 [v1, v2, v4] 0 5 12 9 17 3 v4 [v1, v2, v4] 0 5 12 9 17
4 v3 [v1, v2, v4, v3] 0 5 12 9 16
5 v5 [v1, v2, v4, v3, v5] 0 5 12 9 16

2024/10/20 47 2024/10/20 48

12
 20-10-2024

Example for Dijkstra’s Algorithm Example for Dijkstra’s Algorithm

v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5] cost[v6]

v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5] cost[v6]
1 [v1] 0 4 2 ∞ ∞ ∞
1 [v1] 0 4 2 ∞ ∞ ∞
2 v3 [v1, v3 ] 0 4 2 ∞ 3 ∞ 2 v3 [v1, v3 ] 0 4 2 ∞ 3 ∞

3 3 v5 [v1, v3, v5 ] 0 4 2 ∞ 3 12
4 4 v2 [v1, v3, v5, v2 ] 0 4 2 5 3 12
5 5 v4 [v1, v3, v5, v2, v4 ] 0 4 2 5 3 12
2024/10/20 6 49 2024/10/20 6 v6 [v1, v3, v5, v2, v4 ] 0 4 2 5 3 12 50

Example for Dijkstra’s Algorithm Dijkstra’s Algorithm

Algorithm shortestPath()
n = number of nodes in the graph;
for i = 1 to n
cost[vi] = w(v1, vi);
VS = { v1 };
for step = 2 to n {
find the smallest cost[vi] s.t. vi is not in VS;
v VS cost[S] cost[A] cost[B] cost[C] cost[D] cost[E]
include vi to VS;
1 [S] 0 ∞ ∞ ∞ ∞ ∞
for (all nodes vj not in VS) {
2 A [S, A] 0 6 ∞ ∞ 8 7
if (cost[vj] > cost[vi] + w(vi, vj))
3 E [S, A, E] 0 6 15 ∞ 8 7 cost[vj] = cost[vi] + w(vi, vj);
4 D [S, A, E, D] 0 6 15 12 8 7 }
5 C [S, A, E, D, C] 0 6 15 11 8 7 }
2024/10/20 6 B [S, A, E, D, C, B] 0 6 15 11 8 7 51 2024/10/20 52

13
 20-10-2024

Dijkstra’s Algorithm Floyd Warshall Algorithm

function Dijkstra(Graph, source): • Floyd Warshall is a dynamic programming algorithm used to solve all pair shortest path
dist[source] = 0 // Distance from source to source is set to 0 problems.
for each vertex v in Graph // Initializations • Dynamic Programming is an approach used in data structure and algorithms for solving
if v ≠ source problems efficiently, this approach is known for providing the most optimized result.
dist[v] = infinity // Unknown distance function from source to each node set to infinity
• Dynamic programming solves a class of problems using overlapping sub problems,
add v to Q // All nodes initially in Q
memorization, and optimal substructure property.
while Q is not empty // The main loop • Floyd Warshall algorithm is the shortest path algorithm, similar to Dijkstra’s
v = vertex in Q with min dist[v] // In the first run-through, this vertex is the source node algorithm and Bellman ford’s algorithm.
remove v from Q • The only difference is Dijkstra’s and Bellman Ford’s algorithms are single source shortest
path algorithms, whereas Floyd Warshall is all pair shortest path algorithm, it can compute
for each neighbor u of v // where neighbour u has not yet been removed from Q. the shortest path between every pair of vertices in the graph.
alt = dist[v] + length(v, u)
• Floyd Warshall Algorithm is unique compared to other algorithms because it can handle
if alt < dist[u] // A shorter path to u has been found
negative edge weights.
dist[u] = alt // Update distance of u // In general time complexity is O(V + E(log V)
return dist[] // The time complexity is O(V²) being V the number of vertexes. • The algorithm can also work with graphs that have cycles.
end function //And the space complexity O(V). • Furthermore, it is an efficient algorithm that can solve problems involving a large number
2024/10/20 53
of2024/10/20
nodes in the graph. 54

Floyd Warshall Algorithm Floyd Warshall Algorithm Example

Step-01: Remove all the self loops and parallel edges
1. Initialize a distance matrix D wherein D[i][j] represents the shortest distance
(keeping the lowest weight edge) from the graph.
between vertex i and vertex j. In the given graph, there are neither self edges nor
2. Set the diagonal entries of the matrix to 0, & all other entries to infinity (∞). parallel edges.
3. For every area (u, v) inside the graph, replace the gap matrix to mirror the
weight of the brink: D[u][v] = weight(u,v). Step-02: Write the initial distance matrix.
4. For every vertex in the graph, all pairs of vertices (i,j) and check if the path It represents the distance between every pair of
vertices in the form of given weights.
from i to j through k is shorter than the current best path.
For diagonal elements (representing self-loops),
i. If it is, update the matrix: D[i][j] = min(D[i][j], D[i][k] D[k][j]). distance value = 0.
5. After all iterations, the matrix D will contain the shortest course distances For vertices having a direct edge between them,
between all pairs of vertices. distance value = weight of that edge.
For vertices having no direct edge between them,
distance value = ∞.
2024/10/20 55 2024/10/20 56

14
 20-10-2024

Floyd Warshall Algorithm Example Floyd Warshall Algorithm Example

Step 3: Minimize the shortest paths between any 2 pairs in the previous operation.

Step 4: For any 2 vertices (i,j), one should actually minimize the distances between
this pair using the first K nodes, so the shortest path will be:
min (dist[i][k] + dist[k][j], dist[i][j]).

dist[i][k] represents the shortest path that only uses the first K vertices, dist[k][j]
represents the shortest path between the pair k,j. As the shortest path will be a
concatenation of the shortest path from i to k, then from k to j.
2024/10/20 57 2024/10/20 58

Floyd Warshall Algorithm Example Floyd Warshall Algorithm Example

A B C D

A 0 6 5 ∞

B 3 0 ∞ 2

C ∞ 4 0 ∞

D ∞ ∞ 7 0

2024/10/20 59 2024/10/20 60

15
 20-10-2024

Floyd Warshall Algorithm Example Floyd Warshall Algorithm Example

A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D
A 0 6 5 ∞ A 0 6 5 ∞ A 6 A 0 6 5 8 A 5 A 0 6 5 8 A 8 A 0 6 5 8
B 3 B 3 0 8 2 B 3 0 8 2 B 3 0 8 2 B 8 B 3 0 8 2 B 2 B 3 0 8 2
C ∞ C ∞ 4 0 ∞ C 4 C 7 4 0 6 C 7 4 0 6 C 7 4 0 6 C 6 C 7 4 0 6
D ∞ D ∞ ∞ 7 0 D ∞ D ∞ ∞ 7 0 D 7 D 14 11 7 0 D 14 11 7 0 D 14 11 7 0

Selecting 1st row and 1st column Selecting 2nd row and 2nd column Selecting 3rd row and 3rd column and Selecting 4th row and 4th column and
and update the matrix and update the matrix update the matrix update the matrix

2024/10/20 61 2024/10/20 62

Floyd Warshall Algorithm Example Floyd Warshall Algorithm Example

int main() {
int A[4][4] = {{0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0}};
int n = 4; // size of the adjaceny matrix void floydWarshall(int A[n][n], int D[n][n]) { int D[4][4];
fillDistanceMatrix(A, D);
void fillDistanceMatrix(int A[n][n], int D[n][n]) { floydWarshall(A, D);
for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) {
for (int j = 0; j < n; j++) { for (int i = 0; i < n; i++) { printf("Shortest distances between all pairs of vertices:\n");
if (i == j) for (int j = 0; j < n; j++) { for (int i = 0; i < 4; i++) {
D[i][j] = 0; for (int j = 0; j < 4; j++) {
if (D[i][k] < INF && D[k][j] < INF)
else if (A[i][j] == 0) if (D[i][j] == INF)
D[i][j] = INF;
if (D[i][k] + D[k][j] < D[i][j])
D[i][j] = D[i][k] + D[k][j]; printf("%7s", "INF");
else else
D[i][j] = A[i][j]; }
printf("%7d", D[i][j]);
} } }
} } printf("\n");
} } }
return 0;
}
2024/10/20 63 2024/10/20 64

16
 20-10-2024

Floyd Warshall Algorithm: Application Floyd Warshall Algorithm

• GPS navigation systems/ Google Maps
Advantages:
• Network routing protocols/Routing data packets
• The Floyd Warshall Algorithm is easy to understand and implement.
• Flight scheduling systems
• It can handle negative edge weights and graphs with cycles.
• Traffic flow analysis
• It can solve problems involving a large number of nodes in the graph.
• Social Network Analysis
• Calculate the inversion of the real matrix
Disadvantages:
• Calculating transitive closure of directed graphs
• The algorithm has a high time complexity of O(V³).
• To check whether an undirected graph is bipartite
• The algorithm requires a large amount of memory to store the distance
• To find the shortest path in a directed graph
matrix. The space complexity is O (n^2).
• To compare two graphs to find the similarities between them.
• The algorithm does not work well for very large graphs.
• To find a maximum bandwidth path in network systems.

2024/10/20 65 2024/10/20 66

Problem: Laying Telephone Wire

Minimum Cost Spanning Trees (MCST/MST)

Prims Algorithm
Kruskals Algorithm Central office

2024/10/20 67 2024/10/20 68

17
 20-10-2024

Wiring: Naïve Approach Wiring: Better Approach

Central office Central office

Expensive!
Minimize the total length of wire connecting the customers
2024/10/20 69 2024/10/20 70

Kruskal’s Kruskal’s
Algorithm Algorithm

2024/10/20 71 2024/10/20 72

18
 20-10-2024

Kruskal’s Prim’s Algorithm

Algorithm

74
2024/10/20 73 74
2024/10/20

Prim’s Algorithm Prim’s Algorithm

2024/10/20 75 2024/10/20 76

19
 20-10-2024

Prim’s Algorithm Running time of Prim’s algorithm

Initialization of priority queue (array): O(|V|)

Update loop: |V| calls

• Choosing vertex with minimum cost edge: O(|V|)
• Updating distance values of unconnected vertices: each edge is
considered only once during entire execution, for a total of O(|E|)
updates
Overall cost:
O(|E| + |V| 2)

2024/10/20 77 2024/10/20 78

Summary Question?
• Graphs can be used to represent many real-life problems.
• There are numerous important graph algorithms. • A good question deserve a good grade…
• We have studied some basic concepts and algorithms.
• Graph Traversal
• Spanning Tree
• Minimum Spanning Tree
• Shortest Path

2024/10/20 79 2024/10/20 80

20
 20-10-2024

81

21