Write an algorithm to find minimum spanning tree of a connected graph.

MinimumSpanningTree( adj, n)

Here adj is the adjacency-list representing the input graph G with n vertices. It uses linear status to keep track of the status of the vertices, edge-count as counter to keep track of the edges added so far to tree, fringe-list a linear linked list to store fringe vertics,linear array fringe-wt to keep track of the candidate edges, linear array parent to store parent of the vertex, and a flag stuck, when true indicate to further movement.

Begin
for i=2 to n by 1 do
Set status[i]=UNSEEN
endfor
Set x=1
Set status[x]=INTREE
Set edge-count=0
Set stuck=false
Create fringe-list
while((edge-count Set ptr=adj[x]
while(ptr != NULL) do //replace != with mathamatical not equal to in hardcopy
Set y=ptr->vertex
if((status[y]=fringe) and (ptr->weight < fringe-wt[y])) then
Set parent[y]=x
Set fringe-wt[y]=ptr->weight
else if (status[y]=UNSEEN) then
Set status[y] = FRINGE
Insert vertex y into fringe-list
Set parent[y] = x
Set fringe-wt[y] = ptr->weight
endif
Set ptr = ptr->link
endwhile
if ( fringe-list is empty) then
Set stuck = true
else
Traverse the fringe list to find a vertex with minimum weight
Set x = the fringe vertex incident with the edge
Remove x from the fringe vertex incident with the edge
Remove x from the frienge-list
Set status[x]=INTREE
Set edge-count = edge-count + 1
endif
endwhile
for x = 2 to n by 1 do
print x, parent[x]
endfor
End.
--------------------------------------------------------
Human do error, please email:- webmaster@piyadas-world.com if you find any. Please visit http://www.piyadas-world.com for more resource.