By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,739 Members | 1,523 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,739 IT Pros & Developers. It's quick & easy.

Kruskal Algorithm

P: 2
hey guys,im doing Kruskal algorithm in C#..works fine...but it takes so long on large input?
i tried using textreader instead of streamreader..still nothin

any way to make it faster?



///////there is a class Edge that implements IComparable

static public SortedList union;/*Taken Vertices*/
static void Main(string[] args)
{

const string filename = @"c:\text_.txt";
Console.Title = "Kruskal Algorithm";
ArrayList graph; /*Initial Graph*/
object vertex1, vertex2;
int cost;
int total_cost = 0;
#region Read File..Fill Graph
StreamReader sr = new StreamReader(filename);
string line = sr.ReadLine();
string[] splitted = new string[2];
char[] splitter = { ' ' };
splitted = line.Split(splitter);
int num_vertices = int.Parse(splitted[0]);
int num_edges = int.Parse(splitted[1]);
graph = new ArrayList(num_edges);
union = new SortedList(num_vertices);

string fileContent;
string[] firstLineParsed = line.Split(new char[] { ' ' });
char[] chars = new char[] { '\n', ' ' };
fileContent = sr.ReadToEnd();
string[] s = fileContent.Split(chars);
for (int i = 0; i < num_edges * 3; i += 3)
{
vertex1 = s[i];
vertex2 = s[i+1];
cost = int.Parse(s[i+2]);
Edge e = new Edge(vertex1, vertex2, cost);
graph.Add(e);
if (!union.ContainsKey(vertex1))
{
union.Add(vertex1, vertex1);
}
if (!union.ContainsKey(vertex2))
{
union.Add(vertex2, vertex2);
}
}
#endregion
graph.Sort();


foreach (Edge e in graph)
{
if (find(ref e.vertex_1) != find(ref e.vertex_2))
{
total_cost += e.cost;
}
}
Console.WriteLine(total_cost);
}

private static void Join(ref object x, ref object y)
{
object xroot, yroot;
xroot = find(ref x);
yroot = find(ref y);
union[xroot] = yroot;
}

private static object find(ref object x)
{
if (union[x] == x)
{
return x;
}
else
{
object z=union[x];
return find(ref z);
}
}
Dec 26 '07 #1
Share this question for a faster answer!
Share on Google+

Post your reply

Sign in to post your reply or Sign up for a free account.