Kruskal Algorithm Imlementation

[Melvik12]

Hi gurues,
anyone has kruskal algorithm imlementation or can help me write it?
Thanks!

[mehdi62b]

I have something..
//*******************************************************
//[C#]
public class SDisjointSet
{
int[] inner;
public SDisjointSet(int capacity)
{
inner=new int[capacity];
}
public int this[int index]
{
get
{
if(index<1 || index>=this.inner.Length)
throw new IndexOutOfRangeException
("index is out of range");
return this.inner[index];
}
set
{
if(index<1 || index>=this.inner.Length)
throw new IndexOutOfRangeException
("index is out of range");
this.inner[index]=value;
}
}
public int Findx(int a)
{
while(inner[a]!=a){a=inner[a];}
return a;
}
public void Merge(int a,int b)
{
if(a<b)
inner[b]=a;
else
inner[a]=b;
}
}
public class Edge:IComparable
{
private int beginningNode;
public int BeginningNode
{
get{return this.beginningNode;}
}
private int endNode;
public int EndNode
{
get{return this.endNode;}
}
private int value;
public int Value
{
get{return this.value;}
}
public Edge(int beginningNode,
int endNode,int value)
{
this.beginningNode=beginningNode;
this.endNode=endNode;
this.value=value;
}
#region IComparable Members
public int CompareTo(object obj)
{
Edge edge1=obj as Edge;
return edge1==null? 1 :
this.value.CompareTo(edge1.value);
}
#endregion
}
public class Graph
{
private ArrayList edges=new ArrayList();
public ArrayList Edges
{
get{return this.SortEdges();}
}
public int NumberOfEdges
{
get{return this.edges.Count;}
}
public ArrayList Nodes
{
get
{
ArrayList temp=new ArrayList();
ArrayList nodes=new ArrayList();
foreach(Edge edgeItem in this.edges)
{
temp.Add(edgeItem.BeginningNode);
temp.Add(edgeItem.EndNode);
}
foreach(int intItem in temp)
if(!nodes.Contains(intItem))
nodes.Add(intItem);
nodes.Sort();
return nodes;
}
}
public int NumberofNodes
{
get{return this.Nodes.Count;}
}
public void Add(Edge edge)
{
foreach(Edge edgeItem in edges)
{
if(edgeItem.BeginningNode==edge.BeginningNode
&& edgeItem.EndNode==edge.EndNode)
throw new ArgumentException("not a valid edge");
}
edges.Add(edge);
}
public ArrayList SortEdges()
{
this.edges.Sort();
return this.edges;
}
}
public class Kruskal
{
private Graph graph;
//private ArrayList resultEdges;
private SDisjointSet sset;
public Kruskal(Graph graph)
{
if(graph!=null)
this.graph=graph;
else
throw new ArgumentNullException
("Graph is null");
}
public string ExecuteKruskal()
{
ArrayList nodes=graph.Nodes;
ArrayList edges=graph.Edges;
if(edges.Count<nodes.Count-1)
throw new Exception
("graph is not connected");
int max=(int)nodes[0];
foreach(int item in nodes)
if(item>max) max=item;
sset=new SDisjointSet(max+1);
foreach(int item in nodes)
sset[item]=item;
int n=graph.NumberofNodes;
ArrayList result=new ArrayList();
for(int i=0;i<n-1;)
{
Edge edge=(Edge)edges[i];

int bNode=edge.BeginningNode;
int eNode=edge.EndNode;
if(sset.Findx(bNode)!=sset.Findx(eNode))
{
sset.Merge(bNode,eNode);
i++;
result.Add(edge);
}
}
string sresult=string.Empty;
int minimumCost=0;
foreach(Edge edgeItem in result)
{
sresult+=
edgeItem.BeginningNode.ToString()+"---"+
edgeItem.EndNode.ToString()+
" with value "+edgeItem.Value+
Environment.NewLine;
minimumCost+=edgeItem.Value;
}
sresult+="The minimum cost is: "+minimumCost.ToString();
return sresult;
}
}
public class TestKruskal
{
public static string Execute()
{
Graph graph=new Graph();
graph.Add(new Edge(1,2,1));
graph.Add(new Edge(2,3,2));
graph.Add(new Edge(1,4,4));
graph.Add(new Edge(2,4,6));
graph.Add(new Edge(2,5,4));
graph.Add(new Edge(3,5,5));
graph.Add(new Edge(3,6,6));
graph.Add(new Edge(4,5,3));
graph.Add(new Edge(5,6,8));
graph.Add(new Edge(4,7,4));
graph.Add(new Edge(5,7,7));
graph.Add(new Edge(6,7,3));
Kruskal kruskal=new Kruskal(graph);
return kruskal.ExecuteKruskal();
}
}
//*****************************************************you should write your own version though!