__Minimum Spanning Tree__

To form an MST(Minimum Spanning Tree) follow this procedure,

1. Begin with a connected graph G.

2. E is the set of all edges of different weights, from G.

3. Sort edges of E in the ascending order of their weights.

4. Go through each member(edge) of E and see if the nodes of that edge is already connected or not.

5. If they aren’t connected, connect them and include that member of E(edge) int MST.

6. Continue this process untill you’ve got n-1 edges(in case of n nodes).

An implementation in C++ using Disjoint Set data structure, is shown

#include <cstdio> #include <algorithm> #define MAX_node 100000 using namespace std; struct edg{ int a,b,w; bool operator < (const edg &b) const{ return w<b.w; } }E[MAX_node+1]; int Prev[MAX_node+1]; int parent(int a){ if(a==Prev[a]) return a; return Prev[a]=parent(Prev[a]); } int main(){ int node,edge; while(scanf("%d%d",&node,&edge)){ int TOTAL=0; for(int i=1;i<=node;i++) Prev[i]=i;//* for(int i=0;i<edge;i++) scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);//** sort(E,E+edge);//*** for(int i=0; i<edge; i++ ){ int u=parent(E[i].a);//**** int v=parent(E[i].b); if(u!=v){ TOTAL+=E[i].w; Prev[u]=v;//***** } } printf("Total Cost of MST %d\n",TOTAL); } return 0; } /* * Making each node it's own parent ** Input edges in the format "node1 node2 weight" *** Sorting them in the ascending order of weight **** Find the current parent of a and b ***** If the nodes of that edge is not connected yet, Connect them. */

if you don’t know Maximum possible number of nodes, then just use a vector(which is a bit slower) of type ‘edg’.

**Related Problems**

MST(spoj)

Dark Roads(UVa)

Audiophobia(UVa)

Connect the Campus(UVa)

Highways(UVa)

__Maximum Spanning Tree__

To get a maximum spanning tree, the procedure is almost same. The only difference is that, you got to sort members of E in the descending order of their weights.

**Related Problems
**Heavy Cargo(UVa)

__Second Best Minimum Spanning Tree__

There may be some other better procedure to find the second best MST, but this is the one I’ve used.

1. First form an MST of graph G, and mark the edges which formes the MST.

2. Then for each member edge of the MST, Form another MST without using that particular member.

3. Thus, u need to form n-1 (in case of n nodes) ‘another’ MSTs and consider the minimun among them.

**Related Problems**

Is There A Second Way Left ?(UVa)

ACM contest and Blackout(UVa)