prims algorith and MST
hi, i have a project to turn in for a class, and for the life of me i cannot figure out what is wrong. I;ve spent the better part of the last couple days trying to figure it out, and its a no go. My professor affords me no help, and my book implements graphs with adjacent matricies, not linked lists. I've read through a few books on java and data structures, but they didn't help my linked list implementation, nor my understanding of the concept.
I am trying to implement prim's algorith using linked lists, and thus far i have this code, maybe someone can help me, as i have almost giving up all hope.
import java.io.*;
import java.util.*;
publicclass Graph{
Vertex_Node head;
int size;
publicvoid find_mst(){
clearMarks();
find_mst(head);
}
publicvoid find_mst(Vertex_Node v){
Edge_Node e = v.GetEdge_Head();int size_tree = 0; Edge_Node min = e;
v.SetMarked(true); v.Setin_mst(true); size_tree++;
while ( size_tree < size){
min = smallest(v);
min.Setin_mst(true);
v.SetMarked(true);
v.Setin_mst(true);
min.GetTarget().Setin_mst(true);
size_tree++;
v = v.GetNext();
}
}
public Edge_Node smallest(Vertex_Node v){
Edge_Node e = v.GetEdge_Head(), min = v.GetEdge_Head();
while(e !=null){
if(e.Getin_mst()){
e = e.GetNext();
}
else{
if(e.GetWeight() < min.GetWeight()){
min = e;
}
}
e = e.GetNext();
}
return min;
}
public Edge_Node cycle(int in_tree){
int visited = 0;
Edge_Node e = head.GetEdge_Head(); Edge_Node min = e;
Vertex_Node v = head;
while(visited < in_tree){
if(v.Getin_mst()){
System.out.println("min cycle = " + v.name);
min = smallest(v);
visited++;
if(min.GetTarget().Getin_mst()){
v = e.GetTarget();
}
}
}
return min;
}
publicvoid output_mst_edges(){
clearMarks();
output_mst_edges(head);
}
publicvoid output_mst_edges(Vertex_Node v){
Edge_Node e;
if (v ==null){
}
else{
while( v !=null){
v.SetMarked(true);
e = v.GetEdge_Head();
while (e !=null){
if (e.Getin_mst()){
System.out.print(e.GetWeight() +" ");
}
e = e.GetNext();
}
v = v.GetNext();
}
}
System.out.println();
}
publicvoid clearMarks(){
Vertex_Node v = head;
while (v !=null){
v.SetMarked(false);
v = v.GetNext();
}
}
publicvoid output_mst_weight(){
clearMarks();
System.out.println("Wt. = " + get_mst_weight(head));
}
publicint get_mst_weight(Vertex_Node v){
Edge_Node e;
int weight = 0;
if (v ==null || v.GetMarked())
weight = 0;
else{
v.SetMarked(true);
e = v.GetEdge_Head();
while (e !=null){
if (e.Getin_mst())
weight += e.GetWeight();
weight += get_mst_weight(e.GetTarget());
e = e.GetNext();
}
}
return weight;
}
public Vertex_Node input(String fileName)throws IOException{
String inputLine, vertexName, sourceName, targetName;
Vertex_Node source = null, target;
Edge_Node e;
int weight;
StringTokenizer input;
BufferedReader inFile =new BufferedReader(new FileReader(fileName));
inputLine = inFile.readLine();
while (inputLine !=null){
input =new StringTokenizer(inputLine);
sourceName = input.nextToken();
source = findVertex(sourceName);
if (source ==null){
head =new Vertex_Node(sourceName, head);
source = head;
size++;
}
targetName = input.nextToken();
target = findVertex(targetName);
if (target ==null){
head =new Vertex_Node(targetName, head);
target = head;
size++;
}
if (input.hasMoreTokens()){
weight = Integer.parseInt(input.nextToken());
// put edge in one direction -- after checking for repeat
e = source.edge_head;
while (e !=null){
if (e.target == target){
System.out.print("Multiple edges from " + source.name +" to ");
System.out.println(target.name +".");
break;
}
e = e.next;
}
source.edge_head =new Edge_Node(target, source.edge_head, weight);
// put edge in the other direction
e = target.edge_head;
while (e !=null){
if (e.target == source){
System.out.print("Multiple edges from " + target.name +" to ");
System.out.println(source.name +".");
break;
}
e = e.next;
}
target.edge_head =new Edge_Node(source, target.edge_head, weight);
}
inputLine = inFile.readLine();
}
inFile.close();
return source;
}
public Vertex_Node findVertex(String s){
Vertex_Node pt = head;
while (pt !=null && s.compareTo(pt.name) != 0)
pt = pt.next;
return pt;
}
}
class Vertex_Node{
String name;
int distance;
boolean marked;
boolean in_mst;
Edge_Node edge_head;
Vertex_Node next;
public Vertex_Node(String target, Vertex_Node v){
name = target;
next = v;
}
public Vertex_Node GetNext(){
return next;
}
publicboolean GetMarked(){
return marked;
}
publicvoid SetMarked(boolean b){
marked = b;
}
public Edge_Node GetEdge_Head(){
return edge_head;
}
publicvoid SetDistance(int d){
distance = d;
}
publicboolean Getin_mst(){
return in_mst;
}
publicvoid Setin_mst(boolean b){
in_mst = b;
}
}
class Edge_Node{
int weight;
boolean in_mst;
Edge_Node next;
Vertex_Node target;
public Edge_Node(Vertex_Node v, Edge_Node e,int w){
next = e;
target = v;
weight = w;
}
publicboolean Getin_mst(){
return in_mst;
}
publicint GetWeight(){
return weight;
}
public Vertex_Node GetTarget(){
return target;
}
public Edge_Node GetNext(){
return next;
}
publicvoid Setin_mst(boolean b){
in_mst = b;
}
}
thank you for any help.
