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

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.

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

Posted by Arafat | 8:25 AM | Algorithm | 0 comments »
Subscribe to:
Post Comments (Atom)

## 0 comments

Post a Comment