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

Abstract

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.