SHORT ANSWER QUESTIONS ..... 8.

..... 8. Define expression tree : node in the trie represents a common prefix of a group of strings and the edges represent characters It , .

provides efficient searching insertion and deletion operations for strings , , .

1. What is a tree ? An expression tree is a binary tree used to represent expressions , w here each internal node represents an
operator and each leaf node represents an operand
, . 17. Define B Tree - :

In computer science a tree is a hierarchical data structure that consists of nodes connected by edges It starts
, .

with a root node and branches out into subtrees Trees are widely used to represent hierarchical relationships . 9. What is heap sort ? A B tree is a self balancing tree data structure designed to maintain sorted data and efficiently support
- -

between data . operations like searching insertion deletion and sequential access It is characterized by a variable number of , , , .

Heap sort is a comparison based sorting algorithm that uses a binary heap data structure to sort elements It
- .
keys per node and is commonly used in database and file systems .

2. List operations on trees : first builds a heap from the input data then repeatedly extracts the maximum for max heap or minimum for , ( ) (

min heap element from the heap and rebuilds the heap until all elements are sorted
) . 18. List rotations on AVL tree :

Insertion Adding a new node to the tree

: .

10. What are the applications of trees ? Left rotation

Deletion Removing a node from the tree
: .

Hierarchical data storage file systems ( ) Right rotation

Traversal Visiting all nodes in the tree in a specific order
: .

Representing organizational structures Left right rotation also known as double rotation
- ( )

Searching Finding a specific node in the tree

: .

Database indexing B trees ( - ) Right left rotation also known as double rotation
- ( )

Modification Changing the value of a node in the tree

: .

Parsing expressions and syntax trees 19. Define multi way search trees - :

Balancing Ensuring the tree remains balanced for efficient operations

: .

Implementing efficient search and sort algorithms Multi way search trees are tree data structures that allow each node to have more than two children Unlike
- .

3. Define the term binary tree :

binary trees where each node can have at most two children multi way search trees can have multiple children
, , -

11. List representations on trees :

per node improving search efficiency in certain scenarios
A binary tree is a type of tree in which each node has at most two children , ty pically referred to as the left child , .

and the right child . Array representation 20. Define splay tree :

4. What are the types of binary trees ? Linked representation using pointers ( )
A splay tree is a self adjusting binary search tree where recently accessed elements are moved closer to the
-

Binary Search Tree BST ( ) 12. Define node of a tree :

root during access operations It employs a technique called splaying to restructure the tree which helps . " " ,

improve the average case time complexity of various operations - .

AVL Tree A node of a tree is a fundamental unit that contains data and links to its child nodes if any It typically consists ( ).

of a value or data field and references to its left and right children .
21. What is a lexical search tree ?

Red Black Tree

-

13. What is a path of a tree ?

A lexical search tree is a tree based data structure used for storing and searching lexical data such as words or - ,

B Tree
- phrases in a dictionary It facilitates efficient lookup operations for words based on their alphabetical order or
.

A path of a tree is a sequence of nodes connected by edges from the root node to a leaf node It represents the . other lexical criteria
Heap
.

route from the root to a specific node in the tree .

22. Define balance factor

Define heap
:
5. :
14. What is a height balanced tree - ?

In the context of AVL trees the balance factor of a node is defined as the difference between the heights of its
A heap is a specialized binary tree based data structure that satisfies the heap property In a heap either the
,
- . ,
A height balanced tree is a type of binary tree where the height difference between the left and right subtrees
- left and right subtrees It is used to determine whether the tree is balanced or requires rebalancing operations A
parent node is greater than or equal to its child nodes max heap or the parent node is less than or equal to its
. .
( ),
of any node is limited to a certain constant It ensures that the tree remains balanced which helps maintain . , balanced tree has a balance factor of 0 while an unbalanced tree has a balance factor greater than 1 or less
child nodes min heap
,
( ).
efficient search insertion and deletion operations
, , . than 1 - .

6. What is a binary search tree ?

15. List operations on AVL tree : 23. What is a graph ?

A binary search tree BST is a binary tree in which the key values in left subtree of a node are less than the
( )
Insertion A graph is a mathematical structure consisting of a set of vertices or nodes and a set of edges that connect
node s key value and the key values in the right subtree are greater than the node s key value It enables fast
( )
' , ' .
pairs of vertices Graphs are used to model pairwise relationships between objects
searching insertion and deletion operations Deletion
. .
, , .

24. List traversals of a graph

List tree traversals Searching
:
7. :

Depth First Search DFS

Inorder traversal Rotation single and double rotations
- ( )
( )

Breadth First Search BFS

Preorder traversal Balancing adjusting balance factors
- ( )
( )

Postorder traversal
Level order traversal 16. What is Trie ?

Trie also known as a prefix tree is a tree based data structure used for storing a dynamic set of strings Each
, , - .

25. Define the term cycle and path in a graph : order of traversal .

Cycle A cycle in a graph is a sequence of vertices and edges that starts and ends at the same vertex
: , wt i h no 33. Give uses of graphs in social networks : LONG ANSWERS QUESTIONS
repeated vertices except for the starting and ending vertex ( ).

Friend recommendations 1. Define tree Describe array and linked representation of a binary tree
. :

Path A path in a graph is a sequence of vertices and edges that connects two vertices It may visit vertices and
: .

edges multiple times but does not have any repeated cycles .
Community detection Tree In computer science a tree is a hierarchical data structure consisting of nodes connected by edges Each
: , .

node has a parent node and zero or more child nodes The topmost node is called the root node . .

26. Which data structure is used to represent a graph in an adjacency list ?

Influence propagation
Array Representation of Binary Tree In array representation the elements of the binary tree are stored in an : ,

An array of lists or a list of lists is commonly used to represent a graph in an adjacency list Each element in the
( ) .
Analysis of network structure array where each index corresponds to a node in the binary tree For a node at index i its left child is stored at
, . ,

array represents a vertex and the corresponding list contains the vertices adjacent to that vertex , .
34. Define MST Minimum Spanning Tree ( ):
index 2 i + 1 and its right child is stored at index 2 i + 2
* , * .

27. Define in degree and out degree of a vertex

- - :
A Minimum Spanning Tree MST of a weighted graph is a spanning tree with the minimum possible total edge
( )
Linked Representation of Binary Tree In linked representation each node of the binary tree is represented using : ,

weight MSTs are used in network design clustering and optimization problems
a structure that contains a data field and pointers to its left and right children These pointers establish the .

In degree The in degree of a vertex in a directed graph is the number of edges that are directed into the vertex
- : - .
. , , .

connections between nodes forming the tree structure , .

Out degree The out degree of a vertex in a directed graph is the number of edges that are directed out of the 35. What is hashing ?
- : -
2. x E plain various types of trees with diagrams :

vertex .
Hashing is the process of mapping data of arbitrary size to fixed size values typically integers known as hash - , ,

codes These hash codes are used to index into hash tables allowing for efficient data retrieval and storage Binary Tree Each node has at most two children
: .

28. What is a weighted graph ?

. , .

What is a hash function Binary Search Tree BST A binary tree where the left subtree contains nodes with keys less than the parent
( ):

A weighted graph is a graph in which each edge is assigned a numerical value known as a weight These , .
36. ?

node and the right subtree contains nodes with keys greater than the parent node
, .

weights represent the cost distance or some other measure associated with traversing the edge , , .
A hash function is a mathematical algorithm that takes an input or key and produces a fixed size output ( " ") - ,

typically a hash code The output is typically a digest of the input data used to uniquely identify or index the
Complete Binary Tree A binary tree in which every level except possibly the last is completely filled and all
: , , ,

29. Define a spanning tree :

. ,

nodes are as far left as possible

input .
.

A spanning tree of a graph is a subgraph that is a tree a connected acyclic graph and includes all the vertices ( )
Full Binary Tree A binary tree in which every node has either zero or two children
of the original graph It spans all vertices while minimizing the number of edges . .
37. Define bucket :
: .

In hashing a bucket refers to a storage location within a hash table It can hold one or more key value pairs Perfect Binary Tree A binary tree in which all internal nodes have exactly two children and all leaf nodes are at
:

30. List ways to represent a graph :

, . - ,

the same level

depending on the specific implementation ..
.

Adjacency matrix Balanced Binary Tree A binary tree in which the height of the left and right subtrees of any node differ by no
40. Define rehashing :
:

Adjacency list more than one .

Rehashing is the process of dynamically resizing a hash table when it becomes too full i e the load factor ( . .,

Incidence matrix exceeds a certain threshold It involves creating a new larger hash table and reinserting all the existing key
). , -
Binary Heap A complete binary tree where every parent node has a value less than or equal to or greater than
: (

value pairs into the new table .

or equal to the values of its children ) .

Edge list
41. What is linear probing ?
3. Define :

31. What are the applications of a graph ?

Linear probing is a collision resolution technique used in open addressing hashing When a collision occurs . ,
Height of Tree The height of a tree is the length of the longest path from the root node to a leaf node It
: .

Social networks analysis linear probing searches for the next available slot in the hash table by incrementing the index linearly until an represents the maximum number of edges in the path .

Transportation networks empty slot is found .

Level of Tree The level of a node in a tree is its distance from the root node The root node is at level 0 its
: . ,

Define quadratic probing children are at level 1 and so on

Computer networks
, .
42. :

Quadratic probing is another collision resolution technique used in open addressing hashing Instead of linearly Complete Binary Tree A binary tree in which every level except possibly the last is completely filled and all
Recommendation systems
: , , ,
.

searching for the next available slot quadratic probing uses a quadratic function to calculate the next probe ,
nodes are as far left as possible .

Circuit design position typically by incrementing the index quadratically

, .
Expression Tree A binary tree used to represent expressions : , w here each internal node represents an operator ,

Biology e g gene interaction networks

( . ., ) 43. Define separate chaining :
and each leaf node represents an operand .

32. What is BFS and DFS ? Separate chaining is a collision resolution technique where each bucket in the hash table is implemented as a Binary Search Tree BST A binary tree in which the left subtree contains nodes with keys less than the parent
( ):

linked list When a collision occurs the colliding key value pairs are stored in the same bucket as a linked list node and the right subtree contains nodes with keys greater than the parent node
, .

BFS Breadth First Search BFS is a graph traversal algorithm that starts at a selected vertex and explores all its
. , - ,
( - ):
allowing multiple items to be stored at the same hash table index Write a function to count the number of leaf nodes of a given tree
neighbors before moving on to the next level of vertices It uses a queue data structure to maintain the order of
.
.
4. :

traversal .
def count leaf nodes root _ _ ( ):

DFS Depth First Search DFS is a graph traversal algorithm that starts at a selected vertex and explores as far
( - ):
if root is None
as possible along each branch before backtracking It uses a stack data structure or recursion to maintain the
:
. ( )

return 0 leading to better performance . rules or balancedness These violations are fixed using rotations and recoloring techniques while maintaining
).

the properties of red black trees - .

if root left is None and root right is None

. . : 10. With the help of an example describe the concept of AVL tree , :

For example after inserting a node if the parent of the new node is red and the uncle is also red a color flip and
, , , ,

return 1 AVL trees are self balancing binary search trees where the height difference between the left and right subtrees
-
rotations are performed to restore red black tree properties - .

balance factor of any node is at most 1 Let s consider the following AVL tree example
( ) . ' :

return count leaf nodes root left + count leaf nodes root right
_ _ ( . ) _ _ ( . )
15. Describe AVL tree rotations with an example :

10
5. Write a function for postorder and preorder traversal of a binary tree .
AVL tree rotations are performed to restore balance after insertions or deletions that cause imbalance There .

def preorder root ( ):

/ \
are four types of rotations left rotation right rotation left right rotation double rotation and right left rotation: , , - ( ), -

5 15
(double rotation These rotations ensure that the balance factor of each node remains within the range 1 1
). [- , ].

if root :

/ \ / \
For example a right rotation is performed to balance a left heavy subtree
, - .

print root data end= ( . , " ")

3 7 12 20
16. x E plain B Tree insert and delete operations
- :

preorder root left ( . )

In this AVL tree :

B trees are balanced tree data structures designed for efficient disk access Insert and delete operations in B
- . -

preorder root right ( . ) trees involve maintaining the properties of B trees such as the maximum and minimum number of keys per - ,

The balance factor of node 10 is 0 . node and maintaining the sorted order of keys within nodes Insertion may lead to node splits while deletion
def postorder root
. ,
( ):
may lead to node merges or redistributions to maintain balance
The balance factor of nodes 5 and 15 is also 0
.
.

if root :
17. Compare B Tree and B+ Tree any four points
The balance factor of nodes 3 and 20 is 0
- ( ):
, 7, 12, .

postorder root left ( . )

1. Both B tree and B+ tree are balanced tree structures used for disk storage and retrieval
If we insert or delete a node that causes an imbalance in the tree we perform rotations to restore balance
- .
, .

postorder root right ( . )

2. B+ trees have a higher fanout factor compared to B trees leading to fewer levels in the tree and reduced
E plain the concept of a red black tree diagrammatically
- ,

print root data end= ( . , " ")

11. x - :
disk accesses .

Red black trees are a type of self balancing binary search tree where each node is augmented with an extra bit
- -
In B trees data may be stored in non leaf nodes while in B+ trees data is only stored in leaf nodes
6. x E plain sequential representation of a binary tree :
representing the color either red or black Here s a diagrammatic representation of a red black tree
3. - , - , , ,
( ). ' - :
making leaf nodes more densely packed and facilitating range queries .

In sequential representation a binary tree is stored in an array Each node of the tree is assigned a unique index , . ,

starting from 0 The children of the node at index i are stored at indices 2 i + 1 left child and 2 i + 2 right child
. * ( ) * ( ).
4. B trees maintain pointers to child nodes within internal nodes
- , w hile B+ trees only have pointers in leaf
nodes resulting in a simpler internal node structure
, .

7. Define the following terms :

5. B trees may require rebalancing operations after insertions or deletions

- , w hile B+ trees typically do not
Complete binary tree A binary tree in which every level except possibly the last is completely filled and all
: , , , require rebalancing due to their more uniform structure .

nodes are as far left as possible .

18. Write a short note on Splay tree :

Strictly binary tree A binary tree in which every non leaf node has exactly two children
: - .

Splay trees are self adjusting binary search trees that automatically reorganize themselves based on access
-

8. Write an algorithm to count leaf nodes in a tree : patterns In a splay tree whenever a node is accessed search insert or delete operation it is moved to the
. , ( , , ),

root of the tree using a series of rotations known as splay operations This helps in reducing the access time for
Initialize a count variable to 0
.
.

12. Write a short note on Trie :

frequently accessed nodes .

Traverse the tree in a depth first manner - .

With the help of an example describe a multi way search tree
Trie also known as a prefix tree is a tree like data structure used for efficient retrieval of strings Each node of
, , - .
19. , - :

At each node if it is a leaf node i e both left and right children are NULL increment the count
, ( . ., ), . the trie represents a single character of the string The root represents an empty string and each path from the . ,
A multi way search tree is a tree data structure where each node can have multiple children One common
root to a leaf node represents a unique string Tries are commonly used in dictionary applications autocomplete
- .

Repeat the process for all nodes

. ,
example of a multi way search tree is a 2 3 tree or a 2 3 4 tree
features and search engines
- - - - .
.
, .

Return the count of leaf nodes 20. Define hashing State the need for hashing Also list advantages of hashing
Describe the lexical search tree with an example
. . , .
.
13. :

Describe the need for height balanced trees Hashing is a process of mapping data of arbitrary size to fixed size values typically integers known as hash
A lexical search tree is a specialized tree used for storing and searching lexical data such as words or phrases in
- , ,
9. - :
,
codes These hash codes are used to index into hash tables facilitating efficient data retrieval and storage
a dictionary Each node of the tree represents a character and the edges represent the sequence of characters
. , .

Height balanced trees such as AVL trees and red black trees are designed to maintain balance within the tree
- , - ,
. ,

structure Balanced trees ensure that the height of the tree remains relatively small compared to the number of
.
forming words Here s an example of a lexical search tree storing words apple app apricot banana and
. ' " ", " ", " ", " ", Need for hashing :

nodes which helps in achieving efficient search insertion and deletion operations "bat ":
, , , .
Hashing allows for efficient data retrieval and storage by mapping keys to unique indices .

Unbalanced trees may degenerate into linked lists resulting in worst case time complexity for operations 14. How are insert and delete operations carried out by a red black tree Explain with an example - ? :
, - .
It provides a faster alternative to linear search for large datasets
Height balanced trees prevent this scenario by ensuring that the height difference between subtrees is minimal
.
- ,
In a red black tree insert and delete operations may cause violations of red black tree properties e g color
- , - ( . .,
Hashing is useful in cryptography for generating hash codes for secure data transmission and storage . 24. What is a hash table Explain in detail ? . structure such as an array Each bucket in the hash table contains a reference to the corresponding slot in the
, .

auxiliary structure .

Advantages of hashing : A hash table is a data structure that implements associative arrays or mappings of keys to values It uses a hash .

function to compute an index hash code into an array of buckets or slots from which the desired value can be
( ) , Example :

Efficient retrieval Hashing enables constant time access to data elements

: - .
found .

Suppose we have a hash table with 4 buckets 0 to 3 and an auxiliary array to store overflow elements After ( ) .

Memory optimization Hashing allows for efficient storage of large datasets reducing memory usage compared
: ,
Key components of a hash table include : hashing keys and encountering collisions the hash table may look like this , :

to other data structures .

Hash function Maps keys to hash codes : . Index 0 > k1 -- [ , v1] - > k2 [ , v2] - > Aux k6
( : [ , v6])
Fast search operations Hash tables facilitate fast search operations especially for large datasets by directly
: , ,

accessing elements using their hash codes . Buckets or slots Stores key value pairs : - . Index 1 > k3 -- [ , v3] - > Aux k7( : [ , v7])

21. What is chaining Explain with a diagram ? . Collision resolution Techniques used to handle collisions when multiple keys hash to the same index
: . Index 2 > None --

Chaining is a collision resolution technique used in hash tables where each bucket index of the hash table ( ) Hash tables offer fast retrieval and insertion times making them suitable for applications requiring efficient data , Index 3 > k4 -- [ , v4] - > k5 [ , v5] - > Aux k8
( : [ , v8])

stores a linked list of key value pairs - . storage and retrieval .

30. Define graph How to represent it Explain with a diagram . ? :

Diagram : 25. Write a short note on Linear probing :

A graph is a mathematical structure used to represent pairwise relationships between objects It consists of a .

Index 0 > k1 -- [ , v1] - > k2 [ , v2] - > None Linear probing is a collision resolution technique used in open addressing hash tables It involves sequentially . set of vertices nodes and a set of edges connections that link pairs of vertices
( ) ( ) .

probing through the hash table until an empty slot is found .

Index 1 > k3 -- [ , v3] - > None Representation :

If a collision occurs at index i linear probing tries index i+1 i+2 and so on , , , , w rapping around to the beginning if
Index 2 > None --
necessary .
Adjacency Matrix An adjacency matrix is a 2D array where the value at index i j represents whether there is
: [ ][ ]

an edge between vertex i and vertex j .

Index 3 > k4 -- [ , v4] - > k5 [ , v5] - > k6 [ , v6] - > None Linear probing can suffer from clustering , w here consecutive occupied slots form clusters leading to degraded ,

performance Adjacency List An adjacency list is a collection of lists or arrays where each list array represents the vertices
: /

22. With the help of an example describe separate chaining , .

.

adjacent to a particular vertex .

Separate chaining is a collision resolution technique where each bucket of the hash table contains a separate 26. Compare separate chaining and open addressing .

Diagram :

data structure e g linked list array to handle collisions

( . ., , ) .
Separate chaining :

Example :
Uses linked lists or other data structures to handle collisions .

Consider a hash table with 4 buckets (0 t o 3 After hashing keys to their respective buckets the hash table may
). ,
Each bucket contains a separate data structure to store collided elements .

look like this :

Offers flexibility in terms of handling collisions but may incur memory overhead due to pointer storage .

Index 0 > k1 -- [ , v1] - > k2 [ , v2] - > None

Open addressing :

Index 1 > k3 -- [ , v3] - > None

Stores collided elements directly within the hash table .

Index 2 > None -- 31. What is topological sort Explain with an example ? :

Uses techniques like linear probing quadratic probing or double hashing to find alternative slots for collided
, ,

Index 3 > k4 -- [ , v4] - > k5 [ , v5] - > k6 [ , v6] - > None elements .
Topological sort is an ordering of the vertices in a directed acyclic graph DAG such that for every directed ( )

edge u v vertex u comes before vertex v in the ordering

( , ), .

23. Describe quadratic probing with an example .

Typically results in better cache performance but can suffer from clustering issues .
Example :

Quadratic probing is a collision resolution technique used in open addressing hash tables It involves .
27. What is rehashing Describe with a diagram ? :

incrementing the hash index by a quadratic function of the probe number until an empty slot is found . Consider the following graph :

Rehashing is the process of dynamically resizing a hash table to accommodate more elements It involves .

Example :
creating a new larger hash table and rehashing all existing elements into the new table
, .
A topological sort of this graph can be : 5, 7, 3, 11, 8, 2, 9, 10

Suppose we have a hash table with 10 slots and a hash function that generates indices After hashing keys and .
28. Differentiate between hashing and rehashing .
This ordering satisfies the condition that for every directed edge ( u, v), u comes before v .

encountering collisions we use quadratic probing to resolve them , :

Hashing Hashing is the process of mapping data of arbitrary size to fixed size values hash codes
: - ( ).
32. What is DFS Describe in detail ? :

Index : 0 1 2 3 4 5 6 7 8 9

Rehashing Rehashing is the process of dynamically resizing a hash table to accommodate more elements by
:
DFS Depth First Search is a graph traversal algorithm that explores as far as possible along each branch before
( - )

Keys k1 k2 k3 k4 k5 k6 k7 k8 k9 k10
:
creating a new larger hash table and rehashing existing elements into it
, .
backtracking It traverses a graph in a depthward motion going from the start vertex to the next vertex until it
. ,

reaches a leaf node then backtracks , .

If k1 k3 and k6 hash to the same index quadratic probing will be used to find alternative indices for the collided
, , ,
29. Describe coalesced chaining with an example .

keys . Algorithm :

Coalesced chaining is a variant of chaining where all overflow elements are stored in a single auxiliary data

Start at the initial vertex and mark it as visited . C : 3 In this matrix :

Recursively visit all adjacent vertices that are not visited . D : 6  The entry 1 indicates that there is an edge between the corresponding vertices .

Repeat the process until all vertices are visited .

E : 8
 The entry 0 indicates that there is no edge between the corresponding vertices .

Example :
F : 9
36. What is an adjacency multi list How to represent it Explain with an example - ? ? :

ii Floyd Warshall algorithm

Consider the following graph An adjacency multi list is a data structure used to represent a graph where each vertex maintains a list of
( ) - :
: -

The Floyd Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all adjacent vertices Additionally for weighted graphs each edge may also contain weight information
Starting from vertex A a possible DFS traversal is A > B > D > E > C > F
- . , , .

pairs of vertices in a weighted graph including negative edge weights but not negative cycles
, : - - - - -

Representation
, ( ).

During the traversal each visited vertex is marked and when all adjacent vertices are visited the algorithm
:

Algorithm
, , ,

backtracks Each vertex is represented by a node in the multi list

:
. - .

Initialize a distance matrix with the weights of the edges between vertices
Short note on Inverse adjacency list of a graph Each node maintains pointers to its adjacent vertices or edges and optionally weight information
.
33. : . ( ) , , .

For each vertex k

The inverse adjacency list of a graph is a data structure used to represent a graph s reverse edges efficiently Example
:
' . :

While the adjacency list stores the outgoing edges for each vertex the inverse adjacency list stores the , Update the distance matrix by considering all pairs of vertices i j and whether a shorter path exists through
Consider the following graph
( , )

incoming edges for each vertex . vertex k .

:

In the inverse adjacency list each vertex maintains a list of vertices from which there is an incoming edge , . Repeat step 2 until all vertices are considered .
The adjacency multi list representation of this graph would be - :

This data structure is useful in various graph algorithms especially for tasks like finding predecessors of a vertex , Example :
A > BC
- [ , ]

or reversing the direction of edges in a graph .

B > ACDE
Consider the following weighted graph :
- [ , , , ]

34. Describe the following algorithms with examples .

C > ABE
The initial distance matrix would be :
- [ , , ]

i Dijkstra s algorithm D > BE

A B C D E F
( ) ' :
- [ , ]

Dijkstra s algorithm is a single source shortest path algorithm that finds the shortest path from a source vertex
' - A 0 5 ∞ ∞ ∞ ∞ E > BCD
B ∞ 0 4 ∞ ∞ ∞
- [ , , ]
to all other vertices in a weighted graph .

C ∞ ∞ 0 3 ∞ ∞ In this representation :
Algorithm
D ∞ ∞ ∞ 0 2 ∞
:

Each vertex is represented by a letter

E ∞ ∞ ∞ ∞ 0 1
.
1. Initialize distances from the source vertex to all other vertices as infinity and the distance to the source
vertex as 0 . F ∞ ∞ ∞ ∞ ∞ 0 Each vertex maintains a list of its adjacent vertices .

2. Create a priority queue or min heap to store vertices and their tentative distances ( - ) .
After applying the Floyd Warshall algorithm the distance matrix would be updated with the shortest path
- ,
37. With the help of an example describe BFS Breadth First Search , ( - ):

distances between all pairs of vertices .

3. While the priority queue is not empty : BFS is a graph traversal algorithm that explores all the neighbor vertices at the present depth prior to moving on
35. With the help of a diagram describe the adjacency matrix representation of a graph
, :
to the vertices at the next depth level .

 Extract the vertex with the smallest tentative distance from the priority queue .

An adjacency matrix is a square matrix used to represent a graph The rows and columns of the matrix .
Example :

 For each neighbor of the extracted vertex : represent the vertices of the graph and the entries in the matrix indicate whether an edge exists between the
,

corresponding vertices . Consider the following graph :

 Update the neighbor s tentative distance if a shorter path is found ' .

Example : Starting from vertex A BFS visits each vertex level by level exploring all the vertices at the current level before
, ,

 Update the priority queue with the new distance .

moving to the vertices at the next level .

The adjacency matrix representation of this graph would be :

4. Repeat until all vertices are visited .

BFS traversal order A B C D E : , , , ,

ABCDE
Example :
38. Describe the term MST Minimum Spanning Tree ( ) wt i h an example :

A 0 1 1 0 0
Consider the following weighted graph :
MST is a subgraph of a weighted connected graph that includes all the vertices of the original graph and ,

B 1 0 1 1 1
connects them with the minimum possible total edge weight In other words it s a spanning tree with the
Running Dijkstra s algorithm from vertex A would result in the following shortest distances . , '

minimum sum of edge weights

' :

C 1 1 0 0 1
.

A 0
Example
:

D 0 1 0 0 1
:

B : 5

E 0 1 1 1 0
Consider the following weighted graph :

An MST for this graph would be : Step 2 Select edge AB weight 2

: ( )

In this MST : Step 3 Select edge CB weight 3

: ( )

 All vertices of the original graph are included .

The resulting MST is the same as obtained using Prim s algorithm ' :

 The sum of edge weights is minimized .

 There are no cycles .

Both Prim s and Kruskal s algorithms guarantee the construction of a minimum
' ' .

Prim s Algorithm' :

Prim s algorithm is a greedy algorithm used to find the minimum spanning tree MST of a connected
' ( ) ,

undirected graph .

Algorithm :

Start with an arbitrary vertex source vertex and mark it as visited ( ) .

Repeat the following steps until all vertices are visited :

a Choose the minimum weight edge that connects a visited vertex to an unvisited vertex
. .

b Add the selected edge and the unvisited vertex to the MST
. .

c Mark the selected vertex as visited

. .

Detailed Explanation :

Prim s algorithm grows the MST one vertex at a time by selecting the shortest edge that connects a vertex in
'

the MST to a vertex outside the MST .

It maintains a set of visited vertices and an array to track the minimum weight edge connecting each visited
vertex to an unvisited vertex .

The algorithm continues until all vertices are visited resulting in a minimum spanning tree , .

Example :

Consider the following weighted graph :

Starting from vertex A Prim s algorithm selects the minimum weight edges in each step to form the MST
, ' :

Step 1 Select edge AB weight 2

: ( )

Step 2 Select edge AC weight 1

: ( )

Step 3 Select edge CB weight 3

: ( )

The resulting MST is :

Kruskal s Algorithm ' :

Kruskal s algorithm is another greedy algorithm used to find the minimum spanning tree MST of a connected
' ( ) ,

undirected graph .

Algorithm :

Sort all the edges of the graph in non decreasing order of their weights - .

Initialize an empty set to store the MST .

Iterate through the sorted edges and add each edge to the MST if it does not form a cycle .

Repeat step 3 until the MST contains V 1 edges where V is the number of vertices in the graph - ( ).

Detailed Explanation :

Kruskal s algorithm grows the MST by adding the edges with the smallest weights as long as they do not create
'

a cycle .

It uses a disjoint set data structure e g union find to efficiently check for cycles
- ( . ., - ) .

The algorithm ensures that the MST contains the smallest possible total weight .

Example :

Consider the same weighted graph :

Kruskal s algorithm selects the edges in ascending order of their weights

' :

Step 1 Select edge AC weight 1

: ( )