Innovative Matrix Algorithm to Address the Minimal Cost-Spanning Tree Problem

Abstract

K.P.O.Niluminda, E.M.U.S.B.Ekanayake

A spanning tree in a connected graph is a subgraph that forms a tree by connecting all the nodes. The multiple spanning trees may exist in the same graph. Additionally, by computing the total cost of each edge in a spanning tree, we can assign an expense to a spanning tree, which measures how unfavorable it is, and do the same for each edge. A tree with the fewest total edge costs is the Minimal Cost Spanning Tree (MCST). To obtain MCST, several techniques have been developed. Kruskal's and Prim's algorithms, which are widely respected and recognized practices, can be used to find the MCST. Prim's method is node-based as opposed to Kruskal's, which is based on arcs (edges). It is preferred to utilize Kruskal's technique when the graph is sparse, and Prim's approach when it is solid. The term "finite graph" in graph theory refers to a square matrix called an adjacency matrix. The matrix elements display the proximity of vertex pairs in a graph. When discussing an ad- jacency matrix for a weighted graph, it is sometimes referred to as the cost (weight) adjacency matrix. This work suggested a matrix technique that uses the cost adjacency matrix to determine the MCST of a given undirected connected graph. The recommended method is then used to present illustrative examples and achieve outcomes comparable to those of the Prim and Kruskal algorithms.

PDF