Tilted Forum Project Discussion Community - [Java/C++]Minimum Spanning Trees..

- Tilted Technology (https://thetfp.com/tfp/tilted-technology/)

- - [Java/C++]Minimum Spanning Trees.. (https://thetfp.com/tfp/tilted-technology/95389-java-c-minimum-spanning-trees.html)

[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:

T := {}
for i := 1 to n -1 {
do
(x,y) := getNextedge(G) using greedy selection mechanism
while (not cycle(x,y,G)
addEdge(x, y, T);
}

// assume G is a connected graph with N nodes

That's ALL the information I was provided, and was asked to implement it. That said, I'm not looking for a complete solution, although that wouldn't be refused. :)

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..

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

I'm not getting anything related to the alogrithms on java.sun.com :(

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

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!

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 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 :p

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;

}