Kruskal's Algorithm for Minimum Spanning Tree with MATLAB Implementation

In graph theory, Kruskal's algorithm is an efficient method for finding Minimum Spanning Trees (MST). This algorithm leverages graph properties and is implemented through an M-function visualization program. The function follows the format [Wt, Pp] = mintreek(n, W), where 'n' represents the number of vertices in the graph and 'W' denotes the weighted adjacency matrix. If no edge exists between two vertices, their weight is represented by 'inf' (infinity). The implementation uses Kruskal's greedy approach by sorting edges by weight and adding them to the MST while avoiding cycles using union-find data structure. This function displays the edges and vertices of the minimum spanning tree. Wt contains the total weight of the MST, while Pp(:,1:2) stores the two vertices connected by each MST edge. Pp(:,3) contains the corresponding edge weights, and Pp(:,4) maintains the original edge indices. In the accompanying plot, red lines visually represent the MST connections. For example, with n=6 vertices, initialize w=inf*ones(6). Set specific edge weights: w(1,[2,3,4])=[6,1,5], w(2,[3,5])=[5,3], w(3,[4,5,6])=[5,6,4], w(4,6)=2, w(5,6)=6. The algorithm processes these edges in ascending weight order, ensuring no cycles are formed. Execute [a, b] = mintreek(n, w) to compute and visualize the resulting minimum spanning tree with proper edge selection and cycle prevention mechanisms.