Constructing Minimum Spanning Tree Based on Hierarchical Clustering

Abstract

A "graph" refers to a collection of vertices or nodes and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. Spanning Tree is a tree that connects all vertices in the graph. In a single graph, we can have many number of spanning tree. A minimum spanning tree (MST) is then a spanning tree with edge cost less than or equal to the cost of every other spanning tree. Several algorithms have been proposed to find minimum spanning tree. Considering the entire graph to construct MST is a difficult task since the number of nodes increases then the complexity also increases and is vice versa. So here we apply divide and conquer approach to split the nodes into several groups (clusters) and then MST is performed to each cluster and finally clusters are connected. Several clustering algorithms are used for distance based clustering here we prefer to take hierarchical clustering algorithm to find minimum spanning tree. Present work the authors conclude that performance of hierarchical clustering is better than that of other techniques. The experimental results of the performance outcome of the hierarchical are so better that the K mean clustering technique.