Data Structures

UNIT-VI
Mr. G. Nagaraju
Assistant Professor
Department of CSE
VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Dictionary
• A dictionary is an ordered or unordered list of key-value pairs, where
keys are used to locate values in the list.
• A dictionary is a container of elements, each element is a pair of key
and value. Where each value is associated with a corresponding key.
• Example:
• Bank account: It can be viewed as a dictionary where account number
serves as a key for identification of account objects.
• Students marks: In a class roll number serves as a key and marks
serves as values

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Visual Representation
Key values
6601 90
6609 95
6615 70
6640 50
6645 75
6670 80
6690 60
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Basic operations of Dictionary or Dictionary ADT
• A dictionary D is a dynamic set Abstract data type (ADT), it has the
following operations
• Insert(key k, value v) - inserting (key and value) into the dictionary D
• Delete(key k) – deleting (key and value) from the dictionary D with the
help of key corresponding to k
• Search(key k) – search a value x in the dictionary D with a key k of an
element x
• Member(x, D) – it return true it x is in D otherwise return false
• Size(D) – it returns the total number of elements in D.
• Max(D) – it returns the maximum value in the dictionary D.
• Min(D) – it returns minimum value in the dictionary D
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Examples
• Empty Dictionary D - {} Key value
• Insert((1,A),D) - {(1,A)} 1 A

Key value
• Insert((3,B),D) - {(1,A),(3,B)} 1 A
3 B
Key value
• Insert ((10, C),D) - {(1,A),(3,B), (10,C)}
1 A
3 B
10 C
• Delete(3, D) - {(1,A), (10,C)} Key value
1 A
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
10 C
 Examples
• Search(10,D) - returns true
• Max(D) - returns key 10
• Min(D) - returns 1
• Size(D) - returns 2 (total number of elements in the
dictionary)

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Implementation of dictionary
Dictionary is implemented using
1. Fixed length array
2. Linked list (linear list)
3. Hashing
4. Trees

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Linear list representation
• The dictionary can be represented as a linear list, it is a collection of
pairs (key and value).
• There are two methods in representation of a dictionary using linked
list. They are
1. Sorted array
2. Sorted chain

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 List node structure
• Linked list node
Struct node
{
int key;
int value;
struct node *next;
};

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Operations
• Insertion
• Deletion
• Search
• Note:
• After insertion or deletion operations list nodes key values must be in order.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Insertion
• initially dictionary is empty, it means head is NULL.
• Insert(1,150)

• Insert(5,140)

• Insert(4,110)

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Deletion

• Deletion has three cases

1. deleting first node
2. deleting last node
3. deleting in-between node

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Deletion – first node

head = head → next

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Deletion – last node

1. Temp node is moving from first node to second node from last
2. Temp->next = NULL

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Delete – In-between node

1.Temp node is moving from first node to

deleting node’s previous node
2.Temp→ next = temp→ next→ next

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Search
• It used to find the key value is available in the list or not
• It uses linear search
• key value is compared with the first node’s key value, if match occurs
it returns true, otherwise compare with the second node’s key value,
this process is repeated until key is found in the list or we reached to
the last node. If last node’s key value is not equal to the key value
then we return false, it means key is not found in the list.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Why hashing
• The sequential search algorithm takes time proportional to the data size i.e. O(n)
• Binary search improves on linear search reducing the search time to O(logn)
• With a BST an O(logn) search efficiency can be obtained, but the worst case
complexity is O(n).
• To guarantee the O(logn) search time, BST height balancing is required (i.e. AVL
trees).
• Suppose we want to store 10,000 students records (each with a 5-digit ID) in a
given container
• A linked list implementation would take O(n) time.
• A height balanced tree would give O(logn) access time.
• Using an array of size 1,00,000 would give O(1) access time but will lead to a lot of space
wastage.
• Note: using hashing we can access records in O(1). So we use hashing
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Hashing
• Hashing is a common method of accessing data records using the hash
table.
• Hash table: Hash table is a data structure in which keys are mapped to
array positions by a hash function.
• Load factor: The ratio of the number of items in a table to
the table size.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Hash function
• Hash function maps key values to array indices.
• Given key values
56, 41, 20, 34, 15, 62
Here hash function is
h(key) = key % table_size

h(56) = 56 %10 = 6
h(41) = 41 % 10 = 1
h(20) = 20 % 10 = 0
h(34) = 34 % 10 = 4
h(15) = 15 % 10 = 5
h(62) = 62 % 10 = 2

• Hash Values: The values returned by a hash function are called hash values or hash
codes or hash sums or simply hashes.
• Insertion of data in the hash table is based on the key value. Every entry in the hash
table is associated with some key.
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Hash function
• A hash function is a mathematical formula which, when applied to a
key, produces an integer which can be used as an index for the key in
the hash table.
• Properties of a Good Hash Function
• Low cost: The cost of executing a hash function must be small, so that
using the hashing technique becomes preferable over other
approaches.
• Determinism A hash procedure must be deterministic. This means that
the same hash value must be generated for a given input value.
• Uniformity A good hash function must map the keys as evenly as
possible over its output range.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Types of Hash functions
• hash functions types are
1. Division method
2. Mid square method
3. Folding method
4. Multiplication Method

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Division method
• Division method: Mapping a key K into one of m slots by taking the
remainder of K divided by m.
h(k) = k mod m
• Example: Assume a table has 10 slots (m=10). Using division method,
insert the following elements into hash table. 56, 41, 20, 34, 15 and
62 are inserted in the order.
• h(56) = 56 %10 = 6
• h(41) = 41 % 10 = 1
• h(20) = 20 % 10 = 0
• h(34) = 34 % 10 = 4
• h(15) = 15 % 10 = 5
• h(62) = 62 % 10 = 2

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Division method
• Drawback: A potential drawback of the division method is that while
using this method, consecutive keys map to consecutive hash values.
• Advantage: This is good as it ensures that consecutive keys do not
collide, but on the other

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Mid Square Method

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Folding method
• The folding method works in the following steps
• Step 1: Divide the Key value into a number of parts. That is, divide k into parts k1,
k2, k3, ……. Where each part has the number of digits except the last part which
may have lesser digits than the other parts.
• Step 2: Add the individual parts. That is, obtain the sum of k1+k2+…+kn. The hash
value is produced by ignoring the last carr, if any.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Multiplication method
• The steps involved in the multiplication method are as follows:
• Step 1: Choose a constant A such that 0 < A < 1.
• Step 2: Multiply the key k by A.
• Step 3: Extract the fractional part of kA.
• Step 4: Multiply the result of Step 3 by the size of hash table (m).
• Hence, the hash function can be given as: h(k) = ceiling( m (kA mod 1))

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Problems with hashing
• Collision: No matter what the hash function, there is the possibility
that two different keys could resolve to the same hash address. This
situation is called collision.
• Example: in division method, table size = 10, there 15 and 25 keys are
mapped to the same hash index. This situation is called collision.
• H(15) = 15 % 10 = 5
• H(25) = 25 % 10 = 5
• Handing collisions: The following techniques can be used to handle
the collisions.
1. Separate chaining
2. Open addressing (Linear probing, Quadratic probing, Double hashing)
3. Re-hashing.
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Separate chaining
• A chain is simply a linked list of all the elements with the same hash key.
• A linked list is created at each index in the hash table.
Hash function: h(k) = k mod n
• Example: Assume a table has 8 slots (m = 8) using the chaining, insert the
following elements into the hash table, 36, 18, 72, 43, 6, 10, 5 and 15 are
inserted in the order

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Separate chaining
• A data item’s key is hashed to the index in simple hashing, and the item
is inserted into the linked list at that index.
• Other items that hash to the same index are simply added to the linked
list.
• Average length = N/M where N is size of the array and M is the number
of linked lists.
• Analysis of chaining:
1. If M is too large then too many empty chains.
2. If M is too small, then chains are too long.
• Advantages of chaining: unbounded elements can be stored (No bound
to the size of table).
• Disadvantages of chaining: too many linked lists (overhead of linked
lists).
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Open addressing
• In open addressing, when a data item can’t be placed at the hashed
indexed value, another location in the array is sought.
• We will explore three methods of open addressing, which vary in the
method used to find the next empty location.
• These methods are
1. linear probing,
2. quadratic probing
3. double hashing.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Linear Probing
• When using a linear probing method, the item will be stored in the next available slot
in the table, assuming that the table is not already full.
• This is implemented via linear search for an empty slot, from the point of collision.
• If the end of table is reached during the linear search, the search will wrap around to
the beginning of the table and continue from there.
• Example: Assume a table has 8 slots (m = 8) using the chaining, insert the following
elements into the hash table, 36, 18, 72, 43, 6, 10, 5 and 15 are inserted in the order.

Analysis of Linear Probing:

if load factor is too small then
too many empty cells

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Quadratic Probing
• If the collision occurs instead of moving one cell, i2 cells from the point of collision,
where I is the number of attempt to resolve the collision.
• Example: assume a hash table has 10 slots. Using quadratic probing, insert the following
elements in the given order.
89, 18, 49, 58 and 69 are inserted into a hash table.

Advantages of quadratic probing

compared to linear probing access becomes
inefficient at a higher load factor.

Disadvantages of Quadratic Probing

Insertion sometimes fails although the table
still has free fields.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Double Hashing
• Double hashing requires that the size of the hash table is a prime number.
• Double hashing uses the idea of applying a second hash function to the key
when a collision occurs.
• The primary hash function determines the home address. If the home
address is occupied, apply a second hash function to get a number c. ( c
relatively prime to N). this c is added to the home address to produce an
overview addresses: If occupied, proceed by adding c to the overflow
address, until an empty slot is found.
• Primary hash function is similar to direct hashing.
Hash1(key) = key % table_size
A popular secondary hash function is
Hash2(key) = R – (key % R)
where R is a prime number that is smaller than the size of the table.
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Double Hashing
• Example: assume a table has 10 slots. Primary hash function is
H1(key) = key mod 10 and second hash function is
H2(key) = 7 – (key mod 7)
• With double hashing, insert the following elements in the
given order.
• 89, 18, 49, 58 and 69 are inserted into a hash table

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Advantages of double hashing
1. Compared to linear probing access becomes inefficient at a higher
load factor
2. Resolution sequences for different elements are different even if
the first hash function hashes the elements to the same field.
3. If the hash functions are chosen appropriately, insertion never fails
if the table has at least one free field.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Rehashing
• Rehashing means hashing again
• Basically, when the load factor increases to more than its pre-defined value
(default value of load factor is 0.75), the complexity increases.
• So to overcome this, the size of the array is increased (doubled) and all the
values are hashed again and stored in the new double sized array to
maintain a low load factor and low complexity.
• Example: store key values 6, 7, 8 into the hash table size 3.
H(k) = k mod table_size
• H(6) = 0, h(7) = 1, h(8) = 2
• Now load factor = 1, suppose we want to insert some more keys into the
hash table then we should increase hash table size.
• New hash table size mustDr.be the nearer value of 2*previous table size
G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Rehashing

• New table size = 3*2 = 6 prime number nearer 6 is 7. so we should

take the new table size is 7.
• Now new hash function
• H(key) = key mod 7
• Now all the existing values are stored in the new hash table using the
updated hash function i.e

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Graphs - terminology
• Graph: A graph is a structure made of two components:
• A set of vertices V,
• A set of edges E. Therefore,
a graph is G = (V, E), where G is a graph.
• Directed graph - every edge of the graph is an ordered pair of vertices
connected by the edge
• Undirected graph - every edge is an unordered pair of vertices connected by
the edge

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Graphs - terminology
• Incident edge: (vi, vj) is an edge, then edge(vi,vj) is said to be incident to vertices vi and vj.
• For example, in graph G1 shown in Figure, the edges incident on vertex 1 are (1,2), (1,4),
and (1,3), whereas in G2, the edges incident on vertex 1 are (1,2).
• Degree of vertex: The number of edges incident onto the vertex
• In graph G1, the degree of vertex 1 is 3, because 3 edges are incident onto it.
• Directed graph has indegree and out degree.
• Indegree of a vertex vi is the number of edges incident onto vi,
with vi as the head.
• Outdegree of vertex vi is the number of edges incident onto vi,
with vi as the tail.
• For graph G2, the indegree of vertex 2 is 1, whereas the
outdegree of vertex 2 is 2.
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Graphs - terminology
• Path: A path between vertices vp and vq is a sequence of vertices vp, vi1, vi2,…, vin, vq
such that there exists a sequence of edges (vp, vi1), (vi1, vi2), …, ( vin, vq).
• In case of a directed graph, a path between the vertices vp and vq is a sequence of
vertices vp, vi1, vi2,…, vin, vq such that there exists a sequence of edges <vp, vi1>,
< vi1, vi2>, …, <vin, vq>.
• If there exists a path from vertex vp to vq in an undirected graph, then there always
exists a path from vq to vp.
• In the case of a directed graph, if there exists a path from vertex vp to vq, then it
does not necessarily imply that there exists a path from vq to vp also.
• Simple path: A simple path is a path given by a sequence of vertices in which all vertices
are distinct except the first and the last vertices.
• Cycle: If the first and the last vertices are same, the path will be a cycle.
• Maximum number of edges (n vertices)
• Undirected graph – n(n-1)/2
• Directed graph – n(n-1)
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Graphs - terminology
• Subgraph: A graph G'=(V', E') is a subgraph of another graph G=(V, E) iff
1. V'⊆ V, and
2. E'⊆ E ∧ ( (v1, v2)∈ E' → v1, v2∈ V').
• Note: In general, a subgraph need not have all possible edges.
• Connected graph: A graph G is said to be connected if for every pair of distinct vertices (vi,
vj), there is a path from vi to vj. A connected graph is shown in figure.
• Completely connected graph: A graph G is completely connected if, for every pair of
distinct vertices (vi, vj), there exists an edge. A completely connected graph is shown in
Figure.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Representations of a Graph
• There are two ways to represent a graph.
1. Array representation (Adjacency matrix)
2. Linked list representation (Adjacency list )

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Array representation (Adjacency matrix)
• One way of representing a graph with n vertices is to use an n2 matrix (that is, a matrix
with n rows and n columns).
• If there is an edge from vi to vj then the entry in the matrix with row index as vi and
column index as vj is set to 1 (adj[vi, vj] = 1, if (vi, vj) is an edge of graph G).
• If e is the total number of edges in the graph, then there will 2e entries which will be set
to 1, as long as G is an undirected graph. Whereas if G were a directed graph, only e
entries would have been set to 1 in the adjacency matrix.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Adjacency matrix – directed graph

Directed Graph Adjacency Matrix

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Linked list representation (Adjacency list )
• Another way of representing a graph G is to maintain a list for every vertex
containing all vertices adjacent to that vertex, as shown in Figure.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Graph Traversal techniques
• Visiting all the nodes in the graph is called graph traversal and graph has
two traversal techniques. They are
1. Depth first traversal
2. Breadth first traversal

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Depth first traversal
• When a graph is traversed by visiting the nodes in the forward (deeper)
direction as long as possible, the traversal is called depth-first traversal.
• For example, for the graph shown in Figure, the depth-first traversal starting
at the vertex 0 visits the node in the orders:

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Depth first search
• Depth First Search (DFS) algorithm traverses a graph in a depth ward motion and uses a
stack to remember to get the next vertex to start a search, when a dead end occurs in
any iteration.

As in the example given above, DFS algorithm traverses

from S to A to D to G to E to B first, then to F and lastly to
C. It employs the following rules.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as
visited. Display it. Push it in a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex
from the stack. (It will pop up all the vertices from the
stack, which do not have adjacent vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Depth First Search - Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Depth First Search - Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Depth First Search - Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Breadth First Search
• Breadth First Search (BFS) algorithm traverses a graph in a breadth ward motion and uses
a queue to remember to get the next vertex to start a search, when a dead end occurs in
any iteration.

As in the example given above, BFS algorithm traverses

from A to B to E to F first then to C and G lastly to D. It
employs the following rules.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as
visited. Display it. Insert it in a queue.
Rule 2 − If no adjacent vertex is found, remove the first
vertex from the queue.
Rule 3 − Repeat Rule 1 and Rule 2 until the queue is
empty.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Breadth First Search - Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Breadth First Search - Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Breadth First Search - Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

 Minimum Spanning Tree
• Spanning Tree
• Given an undirected and connected graph, G = (V, E), a spanning tree of the graph G is a
tree that spans G (that is, it includes every vertex of G) and is a subgraph of G(every
edge in the tree belongs to G ).

• Minimum Spanning Tree

• The cost of the spanning tree is the sum of the weights of all the edges in the tree.
There can be many spanning trees.
• Minimum spanning tree is the spanning tree where the cost is minimum among all the
spanning trees. There also can be many minimum spanning trees.

• Applications:
1. Travelling salesman problem
2. Handwriting recognition
3. Image segmentation
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Minimum Spanning Tree

There are two famous algorithms for finding the Minimum Spanning Tree:
1. Kruskal’s Algorithm
2. Prim’s Algorithm
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Kruskal’s Algorithm
• Kruskal’s Algorithm
• Kruskal’s Algorithm builds the spanning tree by adding edges one by one
into a growing spanning tree. Kruskal's algorithm follows greedy approach
as in each iteration it finds an edge which has least weight and add it to
the growing spanning tree.

• Algorithm Steps:
1. Sort the graph edges with respect to their weights.
2. Start adding edges to the MST from the edge with the smallest weight until the
edge of the largest weight.
3. Only add edges which doesn't form a cycle , edges which connect only
disconnected components.

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Kruskal’s Algorithm - Example

Total cost = 1+2+3+5 = 11

Time complexity = O(ElogV)
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Prim’s Algorithm
• Prim’s Algorithm also use Greedy approach to find the minimum spanning
tree. In Prim’s Algorithm we grow the spanning tree from a starting
position. Unlike an edge in Kruskal's, we add vertex to the growing
spanning tree in Prim’s.

• Algorithm Steps:
1. Maintain two disjoint sets of vertices. One containing vertices that are in the
growing spanning tree and other that are not in the growing spanning tree.
2. Select the cheapest vertex that is connected to the growing spanning tree and is
not in the growing spanning tree and add it into the growing spanning tree. This
can be done using Priority Queues. Insert the vertices, that are connected to
growing spanning tree, into the Priority Queue.
3. Check for cycles. To do that, mark the nodes which have been already selected
and insert only those nodes in the Priority Queue that are not marked.
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Prim’s Algorithm - Example

Cost = 1+2+4 = 7

Complexity is
O((V+E)logV)

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Prim’s Example

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET
 Questions
• Suppose if the graph is not connected which algorithm is used for finding
minimum spanning tree.
• Which data structure is used for Breadth first search
• Which data structure is used for Depth first search.
• Find the minimum cost spanning tree for the given graph also find the cost
of the spanning tree

Dr. G. Nagaraju, Department of CSE(AIML & IOT), VNRVJIET