Hope Foundation’s

International Institute of Information Technology, Pune

Review of Faculty Orientation Workshop

on
Data Structures

K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK

July 7, 2020 1
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Unit VI Graphs (06 Hrs)
Graph: Basic Concepts & terminology.
 Representation of graphs: Adjacency matrix, Adjacency list.
 Operations on graph: Traversing a graph.
Spanning trees: Minimum Spanning tree- Kruskal’s
Algorithm, Prim’s Algorithm and Dijkstra’s Shortest Path Algorithm.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 2
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures: CO-PO Mapping
Course Blooms Taxonomy After successful completion of the course Mapping with
PO MAPPING
Outcome Level students will be able to Syllabus Unit
Apply the knowledge of graph for solving
CO204184.6 4 the problems of spanning tree and 6 1, 2, 3, 4, 5, 9, 12
shortest path algorithm.
MAPPING LEVEL JUSTIFICATION Program Outcomes (POs)
CO6 –PO1 Every Program is based on knowledge of 1. Engineering knowledge
2 mathematics, science and engineering Unit VI Graphs
2. Problem analysis
(06 Hrs)
fundamentals Graph: Basic Conceptsof&solutions
3. Design/development terminology.
CO6 –PO2 Design and debug the program using proper
selection of data types and control structure to be 4. Conduct investigations of complex problems
2
carried out to obtain the specified solution with Representation of graphs: Adjacency matrix,
5. Modern tool usage
appropriate considerations. Adjacency list. and society
6. The engineer
CO6 –PO3 Selection of proper data structure is done based on 7. Environment and sustainability
3 given problem statement for formulating and 8. Ethics
Operations on graph: Traversing a graph.
analysing CEP. 9. Individualtrees:
and team work
CO6–PO4 Selection of proper data structures and algorithm is
Spanning Minimum Spanning tree-
10. Communication
done based on given problem statement for Kruskal’s Algorithm, Prim’s Algorithm and
2 11. Project management and finance
formulating and analysing CEP. Dijkstra’s Shortest Path Algorithm.
12. Life-long learning

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 3
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures: CO-PO Mapping
Course Blooms Taxonomy After successful completion of the course Mapping with
PO MAPPING
Outcome Level students will be able to Syllabus Unit
Apply the knowledge of graph for solving
CO204184.6 4 the problems of spanning tree and 6 1, 2, 3, 4, 5, 9, 12
shortest path algorithm.
MAPPING LEVEL JUSTIFICATION Program Outcomes (POs)
CO6 –PO5 Modern tools like turbo C, Codeblocks, GCC 1.Unit VI Graphs
Engineering knowledge (06 Hrs)
3 are used for development of programs. ProblemBasic
2.Graph: Concepts & terminology.
analysis
CO6 –PO9 Development of algorithm using proper data 3. Design/development of solutions
structures may be divided into team and after the 4.Representation
Conduct investigations of complex
of graphs: problems
Adjacency matrix,
2 completion of entire code it could be integrated 5. Modern tool usage
Adjacency list.
for the required final output. 6. The engineer and society
7. Environment and sustainability
CO6 –PO12 Integration and implementation of modular 8.Operations
Ethics on graph: Traversing a graph.
programs using proper algorithm and data
9.Spanning trees:
Individual and Minimum Spanning tree-
team work
1 structures will be useful throughout the life.
Kruskal’s
10. Algorithm, Prim’s Algorithm and
Communication
Dijkstra’s
11. Shortest Path
Project management andAlgorithm.
finance
12. Life-long learning

K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK

Jul y 7, 2020 4
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures: Books
TEXT BOOKS
T1: Ellis Horowitz, Sartaj Sahni, “Fundamentals of Data Structures”, Galgotia Books Source.
T2: Richard. F. Gilberg, Behrouz A. Forouzan, “Data Structures: A Pseudocode Approach with C,” Cengage
Learning, second edition.
REFERENCE BOOKS
R1: Seymour Lipschutz, “Data Structure with C, Schaum’s Outlines”, Tata McGrawHill.
R2: E Balgurusamy, “Programming in ANSI C”, Tata McGraw-Hill, Third Edition.
R3: Yedidyah Langsam, Moshe J Augenstein, Aaron M Tenenbaum “Data structures using C and C++” PHI
Publications, 2nd Edition.
R4: Reema Thareja, “Data Structures using C”, Second Edition, Oxford University Press, 2014
ADDITIONAL MATERIAL
MOOC / NPTEL:
1. NPTEL Course “Programming & Data Structure” https://nptel.ac.in/courses/106/105/106105085/
2. NPTEL Course “Data Structure & Algorithms” https://nptel.ac.in/courses/106/102/106102064/

K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK

Jul y 7, 2020 5
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures: Topic – Book – Pages Mapping
Reference / text book with
Sr. No. Topic
page no.

UNIT VI: Graphs

6.1  Basic Concepts & terminology
 Sequential representation of graphs :
T2(481-490),
Adjacency matrix, Linked representation of a graph
R1(8.1-8.7,8.17-8.24)
 Operations on graph
 Traversing a graph
6.2 Spanning trees;
 Minimum Spanning tree
 Kruskal’s Algorithm
R1(8.47-8.59)-Old Edition
 Prim’s Algorithm
 Dijkstra's Shortest Path Algorithm

K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK

Jul y 7, 2020 6
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures: Unit 6
Contents
Basic concepts & Terminology
Adjacency matrix, Adjacency lists
Operations on graph, Traversing a graph
Spanning of tree, Minimum Spanning tree
Kruskal’s and Prim’s Algorithm
Dijkstra’s Shortest Path Algorithm

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 7
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Basic concept
A Graph is a non-linear data structure consisting of nodes and
edges.
G = (V, E)
Where V = a set of vertices and E = a set of edges
A Graph consists of a finite set of vertices(or nodes) and set of
Edges which connect a pair of nodes.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 8
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Terminology
Vertex − Each node of the graph is represented as a vertex.
Edge − Edge represents a path between two vertices
Adjacency − Two node or vertices are adjacent if they are connected to each
other through an edge.
Path − Path represents a sequence of edges between the two vertices.
Degree of a Node is the number of edges the node is used to define
Can also define in-degree and out-degree
 In-degree: Number of edges pointing to a node
 Out-degree: Number of edges pointing from a node

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 9
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Terminology
Cycle: a path that starts and ends on the same vertex
Simple path: a path that does not cross itself
Length of a path: Number of edges in the path
An undirected graph is connected if every pair of vertices has a path between it
A directed graph is strongly connected if every pair of vertices has a path
between them, in both directions

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 10
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Types of Graphs:
Weighted or unweighted :
Directed or undirected
Cyclic or acyclic

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 11
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Types of Graphs
Weighted graph: edges have a weight
 Weight typically shows cost of traversing
Unweighted graph: edges have no weight
 Edges simply show connections
Undirected Graphs: each edge can be traversed in either direction
Directed Graphs: each edge can be traversed only in a specified direction
A Cyclic graph contains cycles
An acyclic graph contains no cycles

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 12
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Applications of graphs
To represent networks. The networks may include paths in a city or telephone network or circuit
network.
In social networks like linkedIn, Facebook. For example, in Facebook, each person is
represented with a vertex(or node). Each node is a structure and contains information like person
id, name, gender, etc.
Electrical Engineering − extensively used in designing circuit connections.
Computer Network − The relationships among interconnected computers in the network
follows the principles of graph theory.
Science − The molecular structure and chemical structure of a substance, the DNA structure of
an organism, etc., are represented by graphs.
Linguistics − The parsing tree of a language and grammar of a language uses graphs.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 13
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Applications of graphs
Electronic circuits CS16

Networks (roads, flights, communications)

JFK
LAX STL
HNL DFW
FTL

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 14
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Adjacency Matrix
0 0

1 2
1
3
0 1 1 1 2
1 0 1 1 

1 1 0 1 0 1 0
   
1 1 1 0 1 0 1

0 0 0


Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 15
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Adjacency Lists
0 1 2 3
0
1 0 2 3
1 2 2 0 1 3
3 0 1 2
3

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 16
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Operations on Graphs:
Add/Remove Vertex :
Add/Remove Edge
Traverse a graph

Insertion and deletion of nodes and edges in a graph is implemented by using

adjacency matrix or adjacency list

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 17
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Traversing a graph
Visit the vertices of a graph in some specific order based on the
graph's topology
Graph traversal algorithms typically begin with a start vertex and
attempt to visit the remaining vertices from there.
Graph traversals must deal with a number of troublesome cases.
1. It might not be possible to reach all vertices from the start vertex.
This occurs when the graph is not connected.
2. The graph might contain cycles, and we must make sure that
cycles do not cause the algorithm to go into an infinite loop.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 18
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Traversal Methods
1) Breadth First Search(BFS)
2) Depth First Search(DFS)

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 19
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Example of BFS
static void BFS(Graph G, int v)
{ LQueue Q = new LQueue(G.nodeCount());
Q.enqueue(v);
G.setValue(v, VISITED);
while (Q.length() > 0)
{ // Process each vertex on Q
v = (Integer)Q.dequeue();
PreVisit(G, v);
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
if (G.getValue(nList[i]) != VISITED)
{ // Put neighbors on Q
G.setValue(nList[i], VISITED); Q.enqueue(nList[i]);
}
PostVisit(G, v);
}}

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 20
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Properties of BFS
Notation Gs: connected component of s
Property 1: BFS(G, s) visits all the vertices and edges of Gs
Property 2 : The discovery edges labelled by BFS(G, s) form a
spanning tree Ts of Gs
Property 3 : For each vertex v in Li
฀ The path of Ts from s to v has i edges
฀ Every path from s to v in Gs has at least i edges

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 21
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
BFS

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 22
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Analysis
Setting/getting a vertex/edge label takes O(1) time
Each vertex is labelled twice
1. once as UNEXPLORED 2. once as VISITED
Each edge is labelled twice
1. once as UNEXPLORED 2. once as DISCOVERY or CROSS
Each vertex is inserted once into a sequence Li
Method incidentEdges is called once for each vertex BFS runs in O(n + m) time
provided the graph is represented by the adjacency list structure

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 23
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Iterative BFS pseudocode
create a queue Q
mark v as visited and put v into Q
while Q is non-empty
remove the head u of Q
mark and enqueue all (unvisited) neighbours of u

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 24
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 BFS Algorithm Complexity
The time complexity of the BFS algorithm is O(V + E),
where V is the number of nodes and E is the number of
edges.
The space complexity of the algorithm is O(V).

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 25
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 BFS Algorithm Applications
1. For GPS navigation
2. Path finding algorithms
3. In Ford-Fulkerson algorithm to find maximum flow in a network
4. Cycle detection in an undirected graph
5. In minimum spanning tree

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 26
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Example of DFS
static void DFS(Graph G, int v)
{ PreVisit(G, v);
G.setValue(v, VISITED);
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
if (G.getValue(nList[i]) != VISITED)
DFS(G, nList[i]); PostVisit(G, v);
}

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 27
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Properties of DFS
Property 1 : DFS(G, v) visits all the vertices and edges in the
connected component of v
Property 2 : The discovery edges labelled by DFS(G, v) form a
spanning tree of the connected component of v

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 28
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 DFS pseudocode (recursive implementation)
DFS(G, u)
u.visited = true
for each v ∈ G.Adj[u]
if v.visited == false
DFS(G,v)
init()
{ For each u ∈ G
u.visited = false
For each u ∈ G
DFS(G, u) }

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 29
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 DFS Algorithm (iterative implementation)
1. Create a stack of nodes and visited array.
2. Insert the root in the stack.
3. Run a loop till the stack is not empty.
4. Pop the element from the stack and print the element.
5. For every adjacent and unvisited node of current node, mark the
node and insert it in the stack.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 30
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Analysis of DFS
Setting/getting a vertex/edge label takes O(1) time
Each vertex is labelled twice
1. once as UNEXPLORED 2. once as VISITED
Each edge is labeled twice
1. once as UNEXPLORED 2. once as DISCOVERY or BACK
Method incidentEdges is called once for each vertex
DFS runs in O(n + m) time provided the graph is represented by the adjacency
list structure

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 31
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures: Unit 6
DFS Algorithm Complexity
 The time complexity of the DFS algorithm is O(V + E), where V is
the number of nodes and E is the number of edges.
 The space complexity of the algorithm is O(V).

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 32
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures: Unit 6
DFS Algorithm Applications
1. For finding the path
2. For finding the strongly connected components of a graph
3. For detecting cycles in a graph

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 33
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Spanning Tree
A spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges. Hence, a spanning tree does not have cycles
and it cannot be disconnected..

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 34
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
General Properties of Spanning Tree
A connected graph G can have more than one spanning tree.
All possible spanning trees of graph G, have the same number of edges and
vertices.
The spanning tree does not have any cycle (loops).
Removing one edge from the spanning tree will make the graph disconnected,
i.e. the spanning tree is minimally connected.
Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning tree is maximally acyclic.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 35
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Mathematical Properties of Spanning
Tree
Spanning tree has n-1 edges, where n is the number of nodes
(vertices).
A complete graph can have maximum nn-2 number of spanning
trees.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 36
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Application of Spanning Tree
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 37
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Minimum Spanning Tree (MST)
In a weighted graph, a minimum spanning tree is a spanning tree
that has minimum weight than all other spanning trees of the same
graph.
In real-world situations, this weight can be measured as distance,
congestion, traffic load or any arbitrary value denoted to the edges.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 38
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Kruskal’s Algorithm
Edge with minimum weight is selected.
Cycle should not be formed.
Each time the edge of minimum weight has to be selected.
It is not necessary to have edges of minimum weights to be
adjacent.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 39
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Example of Kruskal’s Algorithm
V1 V1
1) V1 2) 3)
8 2 V1
1 1
V6 3 1 2
V2 V2 1
13 2
7 V2
3 V2
12 2 8
12 V3 V5
V5 V5 V3
V1
9 4)
10 1
V6 2
V4 3 V2

7
V5 V3

V4

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 40
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Kruskal’s Algorithm

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 41
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Prim’s Algorithm
Edge with minimum weight is selected
Select edge with minimum weight adjacent to these vertices.
Process will continue till all the vertices are included.
Cycle should not be formed.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 42
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Example:
A 12 B 1) B B
2)
17 7 1 1 1
F C 2 C
15 2
19 10
D
6
E 14 D

5) A 12 B 4) 12 B 3) B
A
1 1 1
7 7 7
2 C 2 C 2 C
F F F
E 14 D D D

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 43
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Prim’s Algorithm

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 44
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Dijkstra Algorithm
Start finding the distances from source node and find all the paths
from it to adjacent nodes.
Select minimum distance from paths available.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 45
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Example:
Find out the shortest path from A to C using Dijkstra algorithm.
Source Node = A dist(A,B) =12 minimum
A 12 B Destination Node = C dist(A,C) = 
17 7 1 dist(A,D)= 
F
15 2 C dist(A,E) = 15
19 10
dist(A,F) = 17
6
E 14 D
dist(A,C) = min{, {d(A,E)+d(E,D)+d(D,C)}}
= min{,{15 + 14 + 6}}
dist(A,C) = min{, {d(A,B) + d(B,C)}} =min {,35}
= min{, (12+1)} = 35
= min{,13} dist(A,C) =min{,{d(A,B)+d(B,D)+d(D,C)}}
dist(A,C) = min{, {d(A,F)+d(F,D)+d(D,C)}}
= 13 = min{, {17+10+6}} = min{,{12+2+6}}
= min{,33} = min{,20}
= 33 =20

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 46
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Example:
Among all these paths 13 is minimum
distance. So shortest path from A to C is 13
which is shown as follows:
A 12 B

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 47
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Dijkstra Algorithm

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 48
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Questions :
Q. 1. In each of the following examples, please choose the best data structure(s). Options are:
Array, Linked Lists, Stack, Queue, Tree, Graph. Justify your answer.
a) You have to store social network “feeds”. You do not know the size, and things may need to
be added as and when it is required.
b) To store the customer order information in a drive-in burger place. (Customers keep on
coming and they have to get their correct food at the payment/food collection window.)
c) To implement back functionality in the internet browser.
d) To store the possible moves in a chess game.

Q. 2 Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or
why not.

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 49
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Questions:
Q.3 Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume
(u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the spanning tree of
G_ ?
Answer: The given undirected graph is a complete graph on 10 vertices, so no. of edges in
Minimum spanning tree = 9
An edge is included in MST if it's cost is less than or equal to the weights of the remaining edges
and doesn't form a cycle,
Now, the minimum possible weight is 4 because it is a simple graph, so loops are not allowed.
Now, if we consider edges,(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10),we obtain the
required 9 edges each with a cost of 4
So, Total cost in MST = 9*4 = 36

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 50
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
Questions:
Q.4 Consider an undirected random graph of eight vertices. The probability that there is an edge
between a pair of vertices is 1/2. What is the expected number of unordered cycles of length
three?
(A) 1/8
(B) 1
(C) 7
(D) 8

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 51
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Data Structures
Suggestions are Welcome!

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 52
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION
 Stay safe and healthy and happy

Enjoy the new version of teaching

Jul y 7, 2020 K.K. WAGH INSTITUTE OF ENGINEERING EDUCATION AND RESEARCH, NASHIK 53
DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION