ASSIGNMENT WEEK – 14

Name – HIMANSHU RAJ

Register No. - EA2331201010152

Program - B.C.A.-Data Science

Subject – Data Structure & Algorithm (DSA)

Semester – II Semester

EA2331201010152
 1. Find the minimal spanning tree of the following graph using Prim's
algorithm.

Ans. Prim's Algorithm

Prim's algorithm is a greedy algorithm to find the MST for a connected, weighted
graph. It starts with an arbitrary vertex, builds a tree by including edges with the least
weight that connect the tree to the outside world, and continues until all vertices are
included in the tree.

Steps:

1. Choose a Starting Vertex: Select any vertex in the graph as the starting point.
Let's call this vertex A.
2. Create Sets: Initialize two sets:
o MST Set: This set will contain the vertices that are already included in the
MST. Initially, it will only contain vertex A.
o Non-MST Set: This set will contain all the remaining vertices in the graph
that are not yet included in the MST.
3. Find Minimum Cost Edges:
o For each vertex in the MST set, identify its adjacent vertices that are still
in the non-MST set.
o Calculate the weights of the edges connecting these vertices to the MST
set.
o Find the edge with the minimum weight among all these edges.
4. Include Minimum Weight Edge:
o Add the vertex that the minimum weight edge connects to the MST set.
o Add the minimum weight edge itself to the MST.
5. Repeat Steps 3 & 4:
o Continue iterating through steps 3 and 4 until all vertices are in the MST
set. In each iteration, you'll be adding a new vertex and its connecting
edge (with the minimum weight) to the MST.

Applying Prim's Algorithm to the Graph:

Example:

EA2331201010152
 1. Start with Vertex A: Assume you start with vertex A in the MST set and all
other vertices (B, C, D, E, F) in the non-MST set.
2. Find Minimum Cost Edges:
o Look at the edges connecting A to B, C, D, E, and F.
o Identify the edge with the least weight. Let's say it's the edge connecting
A and B.
3. Include Minimum Weight Edge:
o Add vertex B to the MST set.
o Add the edge between A and B (with the minimum weight) to the MST.
4. Repeat:
o Repeat steps 2 and 3, considering vertices in the current MST set (now
including B) and those remaining in the non-MST set.
o In each iteration, choose the edge with the minimum weight that
connects the MST to a vertex outside the MST.
o Continue adding vertices and edges to the MST until all vertices are
included.

Visualization (without the actual graph):

Iteration | MST Set | Added Edge

-----------|-----------|------------
1 |A | A-B (min. weight)
2 | A, B | B-C (min. weight)
3 | A, B, C | C-D (min. weight)
4 | A, B, C, D | D-E (min. weight)
5 | A, B, C, D, E | E-F (min. weight) // All vertices included in MST

Result:

By following these steps, you'll identify the edges that form the MST, which is the
subset of edges that connect all vertices in the graph with the minimum total weight.

Note:

The specific order in which you choose the minimum weight edges might vary
depending on the graph's structure, but the resulting MST will always have the same
total weight.

2. Construct the minimum spanning tree (MST) for the given graph using
Kruskal’s Algorithm.

EA2331201010152
Ans. Kruskal's Algorithm

Kruskal's Algorithm is another greedy algorithm to find the MST for a connected,
weighted graph. It works by sorting all the edges in non-decreasing order of their
weights and then including edges one by one into the growing MST. The key is to
avoid creating cycles while adding edges.

Steps:

1. Sort Edges: Sort all edges in the graph by their weights in non-decreasing
order.
2. Initialize Disjoint-Set Forests: Create a data structure called a disjoint-set
forest (or union-find data structure) to keep track of connected components in
the graph. Initially, each vertex has its own set (forest with a single-vertex tree).
3. Iterate Through Edges: Process the edges in the sorted order (from least
weight to highest):
o For the current edge:
▪ Identify the two vertices that it connects (represented by their sets
in the disjoint-set forest).
▪ Check if adding this edge would create a cycle. In Kruskal's
algorithm, cycles are formed when connecting two vertices that
already belong to the same set (meaning they are already
connected in the growing MST).
▪ If adding the edge wouldn't create a cycle:
▪ Use the disjoint-set forest to perform a union operation on
the sets of the two vertices connected by the edge. This
merges their trees into a single tree, indicating that they are
now part of the same connected component in the MST.
▪ Add the current edge to the MST.
4. Stop at MST: Continue iterating through edges and performing the above
checks until you have included enough edges to connect all vertices in the
graph exactly once (forming a tree). Since you're adding edges with the least
weights first, this will be the MST.

Applying Kruskal's Algorithm to the Graph:

Example:

EA2331201010152
 1. Sort Edges: Assume you have a list of edges with their weights for the graph in
the image. Sort this list in ascending order of weight.
2. Disjoint-Set Forest: Initialize a disjoint-set forest data structure to represent
initially separate sets for each vertex.
3. Process Edges:
o Iterate through the sorted list of edges:
▪ For each edge, check if adding it would create a cycle using the
disjoint-set forest.
▪ If it wouldn't create a cycle, perform a union operation on the sets
of the two vertices connected by the edge, and add the edge to the
MST.

Example (without the specific graph):

Consider these sorted edges (replace weights with actual values from your graph
image):

Edge Weight | Action (Cycle Check & Set Union)

--------------|----------------------------------
w1 | Add edge, update sets (no cycle) - MST
w2 | Add edge, update sets (no cycle) - MST
w3 | Check for cycle (depends on previous sets), If no cycle: add edge, update
sets - MST
... | ... (similar process)
wn (MST size=n-1) | Check for cycle (should not create one), If no cycle: add edge
(last edge to connect all vertices) - MST

Result:

By following these steps, you'll identify the edges that form the MST, which is the
subset of edges that connect all vertices in the graph with the minimum total weight.

Note:

The specific order in which you process edges might vary slightly depending on the
graph's structure, but the resulting MST will always have the same total weight.

EA2331201010152