CONSTRUCTION OF MINIMUM COST SPANNING TREE
CONSTRUCTION OF MINIMUM COST SPANNING TREE Let, G = (V, E) be an undirected connected weighted graph with n vertices, where V is the set of vertices, E is the set of edges and W be the set of weights (cost) associated to respective edges of the graph. Where the edge adjacent to vertices = the weight associated to the edge . The Weight Matrix M of the graph G is constructed as follows: If there is an edge between the vertices in G then Set, = Else Set, = 0 Algorithm: Input : the weight matrix for the undirected weighted graph G Output: Minimum Cost Spanning Tree T of G. Step 1 : Start Step 2 : Repeat Step 3 to Step 4 until all (n-1) elements matrix of M are either marked or set to zero or in other words all the nonzero elements are marked Step 3: Search the weight matrix M either column-wise or row-wise to find the unmarked nonzero minimum element which is the weig...