Article Published In Vol.8 (July-Aug 2020)

Generation of Minimal Spanning Tree using Weight Matrix and concept of Cut Edge

Author : Babita Bist

Minimal Spanning tree (MST) is a fundamental problem in networking design. The problem of constructing MST of an undirected connected weighted graph belongs to the group of classical combinatorial optimization problems. This paper presents minimum cost (weight) spanning tree using the algorithm which is based on the weight matrix of weighted graph and the concept of cut edge. The algorithm particularly uses only upper triangular part of weight matrix.

Keywords: Graph, Weight Graph, Spanning tree, Minimum Cost Spanning Tree, Cut Edge