09-27-2005, 08:04 PM | #1 (permalink) | |
Lover - Protector - Teacher
Location: Seattle, WA
|
[Java/C++]Minimum Spanning Trees..
So I'm enrolled in -- by far -- the hardest class I've ever taken for my Comp Sci major (as of yet). It's a Design/Analysis class for Algorithms...
Has anyone implemented the Kruskal, Prim, or Dijkstra Algorithms for Minimum Spaninng Trees in Java? I'm having a very difficult time implementing these alogrithms because of the poor explanation by my professor. Searching around on google, I can't get anything more than the poor psuedo-code my instructor provided. Quote:
I've implemented it with a java class Edge which is aware of its weight and its connecting nodes. It entirely works, except the "cycle()" method. I'm not sure how to make the program aware of a cycle? Each edge has no knowledge of the next edge to be added other than its verticies and weight. AAAAAAH .. any help is appreciated, as it is approaching one week late as I've tried to implement it different ways..
__________________
"I'm typing on a computer of science, which is being sent by science wires to a little science server where you can access it. I'm not typing on a computer of philosophy or religion or whatever other thing you think can be used to understand the universe because they're a poor substitute in the role of understanding the universe which exists independent from ourselves." - Willravel |
|
09-27-2005, 08:36 PM | #2 (permalink) |
Free Mars!
Location: I dunno, there's white people around me saying "eh" all the time
|
That looks like pascel coding. The := sign gave it away.
Go to java.sun.com and punch in the search key Dijkstra and you'll get quite a few results relating to that particular algorithms
__________________
Looking out the window, that's an act of war. Staring at my shoes, that's an act of war. Committing an act of war? Oh you better believe that's an act of war |
09-27-2005, 08:44 PM | #3 (permalink) |
Lover - Protector - Teacher
Location: Seattle, WA
|
I'm not getting anything related to the alogrithms on java.sun.com
__________________
"I'm typing on a computer of science, which is being sent by science wires to a little science server where you can access it. I'm not typing on a computer of philosophy or religion or whatever other thing you think can be used to understand the universe because they're a poor substitute in the role of understanding the universe which exists independent from ourselves." - Willravel |
09-27-2005, 09:07 PM | #4 (permalink) |
Free Mars!
Location: I dunno, there's white people around me saying "eh" all the time
|
Sorry, forgot to mention to look within the forums. Sun Microsystems doesn't offer alot of article on that but there is a lot of threads on that.
Dijkstra Search Results Kruskal Search Results
__________________
Looking out the window, that's an act of war. Staring at my shoes, that's an act of war. Committing an act of war? Oh you better believe that's an act of war |
09-27-2005, 09:19 PM | #5 (permalink) |
Dreams In Digital
Location: Iowa
|
MMMmmmmmmm...
We went over these briefly in my Algorithms class last semester. I dug up the online notes, and they skim Dijkstra's- http://www.cns.uni.edu/~wallingf/tea...session27.html Here's something I found for Kruskal's and Prim's: http://www.people.vcu.edu/~gasmerom/MAT131/mst.html I must admit.. I've forgotten these already.... But I hope that helps just a little!
__________________
I can't seem to remember now What it was like- to live life, before you.. symbiont |
09-27-2005, 11:02 PM | #6 (permalink) |
Lover - Protector - Teacher
Location: Seattle, WA
|
Still stuck -- god I hate programming.. if I dont sleep for the next 7 hours until work, I might get somewhere.. eyes burning already.
__________________
"I'm typing on a computer of science, which is being sent by science wires to a little science server where you can access it. I'm not typing on a computer of philosophy or religion or whatever other thing you think can be used to understand the universe because they're a poor substitute in the role of understanding the universe which exists independent from ourselves." - Willravel |
09-28-2005, 04:19 AM | #7 (permalink) |
Junkie
Location: India
|
i have that same subject this semester...the prof sucks(as do most of them)
we had to make an implimentation of krustuls algo during the last lab class here it is in C good luck understanding it...all i know it worked..eureka Code:
#include<stdio.h> int allconn(int con[][10],int no) { int q,w; for(q=0;q<no;q++) for(w=0;w<no;w++) if(con[q][w]==0) return 0; return 1; } int moresameweight(int min,int flag[][10],int weight[][10],int no,int *q1,int *w1) { int q,w; for(q=0;q<no;q++) for(w=0;w<no;w++) if(min==weight[q][w]&&flag[q][w]==0) { *q1=q;*w1=w; return 1; } return 0; } int main() { int noofno,weight[10][10],flag[10][10],con[10][10]; int next=0,q1,w1,q=1,w=1,e,minfound=100; printf("Number of nodes:"); scanf("%d",&noofno); for(q=0;q<noofno;q++) for(w=0;w<noofno;w++) {weight[q][w]=50;flag[q][w]=0;con[q][w]=0;con[q][q]=1;} printf("Enter node1,node2,weight (0 0 0 to end):\n"); while(!(q==0&&w==0)) { scanf("%d %d %d",&q,&w,&e); weight[q-1][w-1]=e;weight[w-1][q-1]=e; } while(allconn(con,noofno)==0) { if(minfound==100&&next==0) { next=1; for(q=0;q<noofno;q++) for(w=0;w<noofno;w++) if(minfound>weight[q][w]) {minfound=weight[q][w];q1=q;w1=w;} flag[q1][w1]=1;flag[w1][q1]=1;con[q1][w1]=1;con[w1][q1]=1; printf("new con:%d %d\n",q1+1,w1+1); } if(minfound>49&&next==1) {printf("over\n"); exit(0); } while(moresameweight(minfound,flag,weight,noofno,&q1,&w1)==0) { minfound++; } flag[q1][w1]=1;flag[w1][q1]=1; con[q1][w1]=1;con[w1][q1]=1; printf("new con:%d %d\n",q1+1,w1+1); for(q=0;q<noofno;q++) for(w=0;w<noofno;w++) for(e=0;e<noofno;e++) { if(con[q][w]==1&&con[w][e]==1) { con[q][e]=1;con[e][q]=1; } } } return 0; }
__________________
Why did the Comp. Engineer get X-mas and Halloween mixed up? Because Oct(31) == Dec(25) |
Tags |
java or c, minimum, spanning, trees |
|
|