1. Unregistered

# Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

write an algorithm for drawing minimum cost spanning tree(MCST) FOR the input graph
;
Its urgent

2. Unregistered

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

hi can i get this answer as soon as possible
my email id basavant4u@gmail.com

3. Unregistered

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

4. Unregistered

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Briefly,describe various file organizations

5. Rahul kuntala
Join Date
Aug 2011
Location
India
Posts
1,394

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Prim with heaps:

make a heap of values (vertex,edge,weight(edge))
initially (v,-,infinity) for each vertex
let tree T be empty
while (T has fewer than n vertices)
{
let (v,e,weight(e)) have the smallest weight in the heap
remove (v,e,weight(e)) from the heap
add v and e to T
for each edge f=(u,v)
if u is not already in T
find value (u,g,weight(g)) in heap
if weight(f) < weight(g)
replace (u,g,weight(g)) with (u,f,weight(f))
}

6. Just Guesss?
Join Date
Jul 2011
Location
Posts
1,687

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Hello friend !!

Minimum cost spanning tree Definition :

Given a connected graph G = (V, E) with realvalued edge weights c (suffix) e, an MST is a subset of the edges T ⊆ E such that T is a spanning tree whose sum of edge weights is minimized.

Trees :

A tree is an undirected graph that is connected and acyclic. Much of what makes trees so useful is the simplicity of their structure.

For instance, A tree on n nodes has n 1 edges

Let us consider an example,

In the image, We start with an empty graph and then attempt to add edges in increasing order of weight (ties are broken arbitrarily).

The minimum spanning tree found by Kruskal's algorithm.

Kruskal's algorithm:

{
sort the edges of G in increasing order by length

keep a subgraph S of G, initially empty

for each edge e in sorted order

if the endpoints of e are disconnected in S

return S
}

Note that, whenever you add an edge (u,v), it's always the smallest connecting the part of S reachable from u with the rest of G, so by the lemma it must be part of the MST.

Applications of MCST :

MST is fundamental problem with diverse applications.

Network design.

Telephone, electrical, hydraulic, TV cable, computer, road

Approximation algorithms for NP-hard problems.

Traveling salesperson problem, Steiner tree

Indirect applications.

Max bottleneck paths
LDPC codes for error correction
Image registration with Renyi entropy
Learning salient features for real-time face verification
Reducing data storage in sequencing amino acids in a protein
Model locality of particle interactions in turbulent fluid flows
Autoconfig protocol for Ethernet bridging to avoid cycles in a network

And Cluster analysis.

Good Luck !!

7. oh my friend
Join Date
Dec 2011
Posts
1,580

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Originally Posted by Unregistered
write an algorithm for drawing minimum cost spanning tree(MCST) FOR the input graph
;
Its urgent
Hello friend....

*You can find out the minimum cost spanning tree for a input graph through greedy algorithm

*This greedy algorithm can be find by using kruskal's algorithm

Greedy algorithm

==>Greedy Algorithm for finding the Minimum Spanning Tree of a Graph G =(V,E)

*The algorithm is also called Kruskal's algorithm.

* At each step of the algorithm, one of several possible choices must be made

*The greedy strategy: make the choice that is the best at the moment

KRUSKAL'S algorithm to find MCST

• Procedure MCST_G(V,E)

• (Kruskal's Algorithm)

• Input: An undirected graph G(V,E) with a cost function c on the edges

• Output: T the minimum cost spanning tree for G

• T ← 0;

• VS ←0;

• for each vertex v ∈ V do

• VS = VS ∪ {v};

• sort the edges of E in nondecreasing order of weight

• while |VS| > 1 do

• choose (v,w) an edge E of lowest cost;

• delete (v,w) from E;

• if v and w are in different sets W1 and W2 in VS do

• W1 = W1 ∪ W2;

• VS = VS - W2;

• T ← T∪ (v,w);

• return T

Minimum Cost spanning Tree

-->Consider a network of computers connected through bidirectional links. Each link is associated with a positive cost: the cost of sending a message on each link.

-->This network can be represented by an undirected graph with positive costs on each edge.

-->In bidirectional networks we can assume that the cost of sending a message on a link does not depend on the direction

-->Suppose we want to broadcast a message to all the computers from an arbitrary computer.

-->The cost of the broadcast is the sum of the costs of links used to forward the message.

-->Finding a fixed connected subgraph, containing all the vertices such that the sum of the costs of the edges in the subgraph is minimum. This subgraph is a tree as it does not contain any cycles.

-->Such a tree is called the spanning tree since it spans the entire graph G.

-->A given graph may have more than one spanning tree

-->The minimum-cost spanning tree (MCST) is one whose edge weights add up to the least among all the spanning trees

good luck

all the best

8. kitkat
Join Date
Oct 2011
Posts
1,629

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

hai,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
the first algorithm for finding a minimum spanning tree was developed by Czech scientist otakar bourvka in the year 1926 the purpose was an efficient electrical coverage of Moravia.
there are now two algorithms commonly used ,prim's algorithm
kruskal's algorithm
these are called as greedy algorithms that run in polynomial time , so the problem of finding such trees is in FP, AND A RELATED DECISIONS PROBLEMS such as determining whether a particular edge is i the MST or determining the minimum total weight exceeds a certain values are in P.
krusal's algorithm
this is an algorithm that finds in graph theory that finds a minimum spanning tree for a connected weighted graph it also finds the subset of the edges that forms a tree that includes very vertex,where the total weight of all the edges in the tree is minimized ,
spinning tree
let P be a connected ,weighted graph and let y be the sub graph of P produced by the algorithm .Y cannot have a cycle , since the last edge added to that cycle would have been with in one sub tree and not between two different trees.Y cannot be disconnected ,since the first encountered edge that joins two components of Y would have been added by the algorithm.thus, Y is a spanning tree of P.
MINIMALITY
we show that the following proposition P is true by the introduction: if F is the set of edges chosen at any of the algorithm,then there is some minimum spanning tree that contains F.
* clearly p is true at the beginning ,when F is empty: any minimum spanning tree will do , and there exits one because a weighted
connected graph always has minimum spanning tree .
*now assume P is true for some non -final edge set F and let T be a minimum spanning tree that contains F.if the next chosen edge E is also in t, than P is true for F+e.otherwise ,T+ e has a cycle C and there is another edge F that is in C but not F.than T-f+e is a tree , and it has the same weight as T , since T has minimum weight and the weight of f cannot be less than the weight of e ,otherwise the algorithm would have chosen f instead of e.so T-f+e is a minimum spanning tree containing F+e and again P holds.
*therefore , by the principle of induction ,P holds when F has become a spanning tree, which is only possible if F is a minimum spanning tree itself.

so dear all the best

9. pabolu manikanta
Join Date
Sep 2011
Posts
2,326

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Hi Dude.....

Spanning Tree:
A Spanning Tree is the connected ascylic sub graph obtained from the graph........
There will connection from one node to every other node with out forming cycles.

Minimum Cost Spanning Tree:
Minimum cost spanning tree is there will be asigned costs to every node,that is the distance from one node to another node,the distance is represented as the cost and when the spanning tree is traveled then it should select the path which is optimal and cost is minimum.it is called minimum cost spanning tree.....

To find the minimum cost spanning tree there are two algorithms present for implementing the minimum cost spanning tree..They are.....
Kruskal's algorithm
Prim's Algorithm

*Prim's algorithm:
Here both the nodes and edges are considered,
start with the one of the node as starting point of the traversal,and add the chepest node and with out forming cycles traverse all the nodes in the given input graph.
This is known as the Prim's Algorithm......

Implementation:
#include<iostream.h>
#inlcude<Conio.h>
#inlcude<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u;
main()
{
int m,c;
cout<<"enter no of verstices";
Cin>>n;
cout<<Enter no of edges";
cin>>m;
for(k=1;k<=m;k++)
{
cin>>i>>j>>c;
cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<n;j++)
if (cost[i][j]=o)
cost[i][j]=3199;
cout<<"order of visited vertices";
k=1;
while(k<n)
{
n=3199;
if(k==1)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(cost[i][j]<m)
{
m=cost[i][j];
u=i;
}
}
else
{
for(j=n;j>=1;j--)
if(cost[v][j]<m&&visited[j]!=1&&visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
m=cost[v][j];
u=j;
}
}
cost[v][u]=3199;
v=u;
cout<<v<<" ";
k++;
visit[v]=0;
visited[v]=1;
}
}

*Kruskal's algorithm:
Here we consider the edges of the graph given.
Start with the chepest edge and traverse the whole graph by considering each and every edge in the graph with out forming the cycles,consider the edge which is chepest and traverse......
This is known as the kruskal's Algorithm......

Implementation:
#include<iostream.h>
#include(conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;
main()
{
input dup1,dup2;
cout<<"enter no of vertices";
cin>>n;
cout<<"enter no of edges";
cin>>m;
cout<<"edge cost";
for(k=1;k<=m;k++)
{
cin>>i>>j>>c;
cost[i][j]=c;
cost[j][i]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]=0)
cost[i][j]=31999;
visit=1;
while(visit<n)
{
v=31999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]!=31999 && cost[i][j]!=v && cost[i][j]!=-1)
{
int count=0;
for(p=1;p<=n;p++)
{
if(visited[p]==i||visited[p]=j)
count++
}
if(count>=2)
{
for(p=1;p<=n;p++)
if(cost[i][p]!=31999 && p!=j);
dup1=p;
for(p=1;p<=n;p++)
if(cost[j][p]!=31999 && p!=i)
dup2=p;
if(cost[dup1][dup2]==-1)
continue;
}
l=i;
k=j;
v=visit[i][j];
}
cout<<"edge from"
cost[l][k]=-1;
cost[k][l]=-1;
visit++;
int count=0;
count1=0;
for(i=1;i<=n;i++)
{
if(visited[i]==1)
count++;
if(visited[i]==k)
count1++;
}
if(count==0)
visited[++vst]=1;
if(count1==0)
visited[++vst]=k;
}
}

10. rockingsan
Join Date
Nov 2011
Posts
550

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Hello
>A subgraph that spans (reaches out to ) all vertices of a graph is called a spanning subgraph.
>A subgraph that is a tree and that spans (reaches out to ) all vertices of the original graph is called a spanning tree.
> Among all the spanning trees of a weighted and connected graph, the one (possibly more) with the least total weight is called a minimum spanning tree (MST).

Following is an algorithm for minimum cost spanning tree:>>

Tree MST = empty tree; Heap h = new Heap();
//any node can be the root of the MST
h.put((dummyRoot  anyNode), 0);
while (h is not empty) {
get minimum
priority (= length) edge (tf);
if (f is not lifted) {
make f a lifted node;
for each edge (fn)
if (n is not lifted)
h.put((fn), length(f,n));
}
}

11. VEENAMBRUTHA
Join Date
Jan 2012
Posts
829

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Originally Posted by Unregistered
write an algorithm for drawing minimum cost spanning tree(MCST) FOR the input graph
;
Its urgent
The Algorithm For Drawing Minimum Cost Spanning Tree :

One of the Algorithm is Kruskals Algorithm :

Kruskals_MST := module()

option package;

export Kruskals_Algorithm;

Kruskals_Algorithm := proc (network_def::list, make_graph::truefalse)

local edgelist :: list, edge :: list, cmp_weights, mst :: set,
mst_edges :: posint, i :: posint, vertices :: set, vertex,
vertex_count :: posint, C :: table, rep_target, rep_value, G,
tot_cost :: posint;

# Obtain list of edges sorted by weight
cmp_weights := proc(a,b) return ( is(a[3] < b[3]) ) end proc:
edgelist := sort(network_def, cmp_weights);

# Obtain list of vertices
vertices := {}:
for edge in edgelist do vertices := vertices union { edge[1], edge[2] } end do:
vertex_count := nops(vertices);
mst_edges := vertex_count - 1; # number of edges in MST = vertices - 1

# Initialize cycle-detecting table
C := table;
for vertex in vertices do C[vertex] := vertex end do;

# printf("vertex_count = %d, edges = %d\n", vertex_count, nops(edgelist));

# Generate MST
mst := {};
for i to nops(edgelist) while (nops(mst) < mst_edges) do;
edge := edgelist[i]:
if (C[edge[1]] <> C[edge[2]]) then
mst := mst union { edge };
rep_target := C[edge[2]];
rep_value := C[edge[1]];
for vertex in vertices do;
if (C[vertex]=rep_target) then
C[vertex] := rep_value
end if;
end do;
end if;
end do:

# Sanity check
if (nops(mst) <> mst_edges) then
printf("*** Did not construct MST, %d <> %d ***\n",
nops(mst), mst_edges);
printf("*** Error in input? Not connected graph? ***\n");
return;
end if;

# At this point, shortest paths for graph is determined.

printf("\nMinimum Spanning Tree:\n\n");
tot_cost := 0;
for edge in mst do;
printf ("%A - %A (%d)\n", edge[1], edge[2], edge[3]);
tot_cost := tot_cost + edge[3];
end;
printf("Total cost = %d\n", tot_cost);
printf("\n");

# create graph G if requested
if (make_graph) then
new(G):
for edge in mst do connect({edge[1]},{edge[2]},G) end do;
return(draw(G));
end if;

return mst;

end proc: # Kruskals_Algorithm

end module: # Kruskals_MST

with(Kruskals_MST);

good luck !!!!

Join Date
Mar 2012
Posts
4

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

At first read the vedic mathematics rules by vedic mathematics book .
Minimum cost spanning tree you will got easily calculations by these 13 rules which generated in sanskrit language .

13. PRINCE-AKG
Join Date
Jul 2011
Posts
525

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

Originally Posted by Unregistered
write an algorithm for drawing minimum cost spanning tree(MCST) FOR the input graph
;
Its urgent

For better idea is to find some key property of the MST that lets us be sure that some edge is part of it, and use this property to build up the MST one edge at a time.

For simplicity, we assume that there is a unique minimum spanning tree.

You can get ideas like this to work without this assumption but it becomes harder to state your theorems or write your algorithms precisely.

Kruskal's algorithm:

sort the edges of G in increasing order by length
keep a subgraph S of G, initially empty
for each edge e in sorted order
if the endpoints of e are disconnected in S
return S
Note that, whenever you add an edge (u,v), it's always the smallest connecting the part of S reachable from u with the rest of G, so by the lemma it must be part of the MST.

Boruvka's algorithm:

make a list L of n trees, each a single vertex
while (L has more than one tree)
for each T in L, find the smallest edge connecting T to G-T
add all those edges to the MST
(causing pairs of trees in L to merge)
As we saw in Prim's algorithm, each edge you add must be part of the MST, so it must be ok to add them all at once.

14. ramkumar
Join Date
Jun 2011
Posts
8

## Re: Write an algorithm for drawing Minimum cost spanning tree(MCST) for the input graph?

You want an algorithm in divide-conquer methodology or greedy technique?... I guess Greedy technique is suited for graphs.. awaitin your reply!... Regards
Also you want me to give the time and space complexities too"?