## Minimum Spanning Tree (MST)

A minimum spanning tree (MST) is a tree that connects all nodes of a connected, undirected graph with the minimum possible total edge weight. MSTs have many applications, including in network design, clustering, and scheduling.

## Kruskal Algorithm for Finding Minimum Spanning Tree

Kruskal’s Algorithm is a greedy algorithm that can be used to find the minimum spanning tree of a connected, weighted graph. The algorithm starts with an empty set of edges and iteratively adds the next smallest edge that does not create a cycle until all nodes are connected.

### Steps for finding Minimum Spanning Tree using Kruskal’s Algorithm:

- Sort the edges of the graph in non-decreasing order of their weights.
- Create a new empty set of edges.
- Iterate through the sorted edges, and for each edge:

a. If adding the edge to the set of edges does not create a cycle, add the edge to the set of edges.

b. If adding the edge to the set of edges creates a cycle, discard the edge and move to the next edge. - Stop iterating when all nodes are connected or when there are no more edges to consider.

The algorithm can be implemented using a disjoint-set data structure to keep track of which nodes are in the same connected component. Initially, each node is in its own set, and each set is represented by a tree with a single node. The algorithm then merges sets as it adds edges to the set of edges, making sure to avoid creating cycles.

The time complexity of Kruskal’s Algorithm is O(E log E), where E is the number of edges in the graph. This is because the algorithm sorts the edges and performs E union-find operations. In practice, the algorithm is very efficient and is commonly used to find MSTs in real-world applications.

**Conclusion**

Kruskal’s Algorithm is a popular and efficient greedy algorithm for finding the minimum spanning tree of a connected, weighted graph. The algorithm iteratively adds the next smallest edge that does not create a cycle until all nodes are connected. The algorithm can be implemented using a disjoint-set data structure to keep track of which nodes are in the same connected component. Kruskal’s Algorithm has a time complexity of O(E log E) and is widely used in practice for finding MSTs.

- Q-1.
- What do you understand by time and space complexity? What is asymptotic notation? Why it is important? Discuss using suitable example.
- Q-2.
- What is recurrence? Discuss in detail the master method for solving a recurrence.
- Q-3
- What is a Travelling Salesman problem? Discuss the greedy algorithm for solving the Travelling Salesman Problem.
- Q-4
- What do you understand by height balanced tree? What is a splay tree? Discuss the insertion/deletion operation on splay tree.
- Q-5
- What is Minimum Spanning Tree? Discuss the Steps for finding Minimum Spanning Tree using Kruskal’s Algorithm.
- Q-6
- What is a Graph? Discuss the depth first traversal of a graph and its computational complexity. Also discuss the topological sort using depth first traversal.
- Q-7
- What is a flow network? Explain Ford-Fulkerson Algorithm for Maximum Flow Problem.
- Q-8
- What is bitonic sequence? What is merging network? Explain.