Page 1 of 1
help me in solving this minimum spanning tree problem (java)
Posted: Sun Dec 05, 2010 11:07 am
by maroon1
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
Re: help me in solving this minimum spanning tree problem (java)
Posted: Sun Dec 05, 2010 11:07 am
by maroon1
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();
}
}
Re: help me in solving this minimum spanning tree problem (java)
Posted: Sun Dec 05, 2010 2:56 pm
by lgsmitty
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.
Re: help me in solving this minimum spanning tree problem (java)
Posted: Sun Dec 05, 2010 4:03 pm
by maroon1
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
Re: help me in solving this minimum spanning tree problem (java)
Posted: Sun Dec 05, 2010 4:21 pm
by SNM
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.