• SambasivaRao Baragada

The Minimum Spanning Tree (MST) problem is fundamental in graph theory and network optimization. Classical algorithms such as Kruskal’s and Prim’s are widely used for their simplicity and efficiency, yet their performance depends on graph density and structure. Kruskal’s global edge-sorting approach is efficient for sparse graphs, while Prim’s vertex-based expansion performs better on dense graphs. This paper proposes the Adaptive Prim–Kruskal (APK) algorithm, a hybrid method that dynamically combines Kruskal’s global selection with Prim’s local expansion. APK begins with a Kruskal-like phase to rapidly form disjoint components and switches adaptively to a Prim-style greedy expansion once connectivity reaches a threshold, determined by graph density or component count. Formal analysis ensures MST optimality by preserving the cut and cycle properties. Empirical evaluation on synthetic and real-world graphs demonstrates up to 25 – 40% runtime improvement over classical methods. The algorithm’s structure also supports natural parallel and distributed implementations, making it suitable for modern graph processing systems.

Minimum Spanning Trees, Krushkal’s algorithm, Prim’s algorithm, Hybrid approach, Adaptive Prim–Kruskal (APK) algorithm

"Adaptive Prim–Kruskal (APK): A Hybrid Density-Aware Algorithm for Minimum Spanning Tree Construction", International Journal of Emerging Technologies and Innovative Research (www.jetir.org), ISSN:2349-5162, Vol.12, Issue 10, page no.c49-c54, October-2025, Available :http://www.jetir.org/papers/JETIR2510208.pdf

"Adaptive Prim–Kruskal (APK): A Hybrid Density-Aware Algorithm for Minimum Spanning Tree Construction", International Journal of Emerging Technologies and Innovative Research (www.jetir.org | UGC and issn Approved), ISSN:2349-5162, Vol.12, Issue 10, page no. ppc49-c54, October-2025, Available at : http://www.jetir.org/papers/JETIR2510208.pdf