Personal computing discussed

Moderators: renee, SecretSquirrel, just brew it!

 
maroon1
Gerbil First Class
Topic Author
Posts: 184
Joined: Fri Aug 26, 2005 5:25 pm
Contact:

help me in solving this minimum spanning tree problem (java)

Sun Dec 05, 2010 11:07 am

Consider a undirected graph, G(N,A), where N and A are the set of nodes and arcs (edges), respectively. Associated with each arc (i,j) in A is a cost c(i,j). Let |N| = n and |A|=m. The problem is to find a rooted undirected spanning tree, G(N,S) where S is a subset of A such that the sum of c(i,j) for all (i,j) in S is minimized. The rooted undirected spanning tree is defined as a graph which connects, without any cycle, all nodes with n-1 arcs, i.e., each node, except the root, has one and only one incoming arc.

You are required to read a graph from a text file. The first 2 numbers (N and E) in the text file specifies the number of vertices and the number of edges available. Follows are the E lines each specifying a link between 2 nodes.

The problem is to find a minimum spanning tree.

Sample input:
8 10
0 1 9
1 3 7
2 3 15
3 4 10
4 6 8
4 5 3
5 6 14
1 6 5
6 7 6
1 7 12

Sample output (The sum of the weights of the spanning tree edges)
53
 
maroon1
Gerbil First Class
Topic Author
Posts: 184
Joined: Fri Aug 26, 2005 5:25 pm
Contact:

Re: help me in solving this minimum spanning tree problem (java)

Sun Dec 05, 2010 11:07 am

This what I did so far

I have read about prim's algorithm and Kruskal's algorithm from wikipedia. But my problem is that I don't know how to implement it in java language

I do know how read number from texts (thats so easy). I also know how to use priority queue. But now what is the next step ? Do I put the vertices in array or queue, and weight of edges in another array ?


import java.io.*;
import java.util.*;


public class MST
{

  public static void main (String arg[])throws FileNotFoundException
{

Scanner input = new Scanner (new File("MST.txt"));

 PriorityQueue<Integer> q=new PriorityQueue<Integer>();

  int NumberOfNodes = input.nextInt();
  int NumberOfEdges = input.nextInt();

}
}

 
lgsmitty
Gerbil In Training
Posts: 1
Joined: Sun Dec 05, 2010 2:46 pm

Re: help me in solving this minimum spanning tree problem (java)

Sun Dec 05, 2010 2:56 pm

Hello, maroon1.

The algorithm continuously increases the size of a tree, one edge at a time, starting with a tree consisting of a single vertex, until it spans all vertices.

Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).
Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}
Repeat until Vnew = V:
1. Choose an edge (u, v) with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)
2. Add v to Vnew, and (u, v) to Enew
3. Output: Vnew and Enew describe a minimal spanning tree

Please let me know if you need Java code too.

Best regards,
lgsmitty.
 
maroon1
Gerbil First Class
Topic Author
Posts: 184
Joined: Fri Aug 26, 2005 5:25 pm
Contact:

Re: help me in solving this minimum spanning tree problem (java)

Sun Dec 05, 2010 4:03 pm

lgsmitty wrote:

Please let me know if you need Java code too.


Hi lgsmitty
If you could, then please send it to me. I really need that code. Thank you very much in advance
 
SNM
Emperor Gerbilius I
Posts: 6209
Joined: Fri Dec 30, 2005 10:37 am

Re: help me in solving this minimum spanning tree problem (java)

Sun Dec 05, 2010 4:21 pm

This web site is not a homework solutions provider. If you need help progressing, we might provide it, but you shouldn't expect or provide source code like that.

In your case, it sounds like you're trying to use the wrong things in your priority queue. Think about what way might make sense.
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals

Who is online

Users browsing this forum: No registered users and 1 guest
GZIP: On