ΕΡΓΑΣΙΑ Ο αλγόριθμος Kruskal και Prim αλγόριθμος.

[fiesta1420]

Καλημέρα σε όλους!!! Θα ήθελα την βοήθεια σας με μια εργασία που έχω, όπως αναφαίρω και στον τίτλο. Η εργασία πρέπει να παραδωθεί μέχρι την δευτέρα το βράδυ γι'αυτό ζητώ τα φώτα σας για την λύση της όσο μπώρει να είναι εφυκτό αυτο. Η εργασία ειναι σε συνημμένο zip αρχείο. Κάθε βοήθεια δεκτή.

 

ΕΥΧΑΡΙΣΤΩ ΕΚ ΤΩΝ ΠΡΟΤΕΡΩΝ!!!!!

Ergasia 1.zip

[Directx]

Άλλος ένας απελπισμένος .. δες εδω http://www.insomnia.gr/forum/showthread.php?t=372862 ..

[fiesta1420]

Σε ευχαριστώ!

το έχω δεί αυτο αλλα δεν πρέπει να είναι ολοκληρωμένη και πρέπει να εχει και λάθη.....

[Pantelwolf]

Σας παρακαλώ λύστε την εργασία, και μετά ελάτε σπίτι να μου κάνετε και μια μπουγάδα, και μέχρι σήμερα το βράδυ παρακαλώ.

 

Από απορία και μόνο αν έχεις μόνο την εκφώνηση άνοιξα το ζιπ. Επιβεβαιώθηκα.

 

Είναι τόσο εκνευριστικό αυτό το πράγμα. Αντί να στρωθείς να κάνεις να το λύσεις μόνος σου και να ρωτήσεις κάτι εκεί που κόλλησες όπως έκανε ο άλλος στο λινκ του Directx. Και να πει κανείς ότι δε δίνει πληροφορίες η εκφώνηση.. απλή καταγραφή σε pc θα κάνεις. Είσαι και Ε εξάμηνο , δεν έμαθες να γράφεις ακόμη κώδικα?

Και φυσικά γι' αυτό θα πάρεις στα 4 χρόνια πτυχίο κι εγώ δεν έχω πάρει ακόμη. Κι ας μην ξέρεις γρι.

 

Παρ' όλα αυτά θα βρούμε μια λύση. Οι απορίες είναι δωρεάν, οι πλήρεις ασκήσεις χρεώνονται. Δέχομαι μετρητά, paypal, πιστωτικές και λίρες.

 

ΥΓ. Τουλάχιστον είσαι ευγενικός

[fiesta1420]

Εχεις δίκιο!!!

το θέμα είναι οτι δεν παρακολουθώ το μάθημα λογω του οτι εργάζομαι και μου είναι δύσκολο να μπω στη λογική της εργασίας...

γι΄αυτο ζήτησα βοήθεια...

καταλαβαινώ παντως το να μην επιθυμείς να βοηθήσεις...

[Luciddream]

Και φυσικά γι' αυτό θα πάρεις στα 4 χρόνια πτυχίο κι εγώ δεν έχω πάρει ακόμη.

 

αχχ και να σουν ο μόνος.. !! :-(

[Dr.Fuzzy]

Εχεις δίκιο!!!

το θέμα είναι οτι δεν παρακολουθώ το μάθημα λογω του οτι εργάζομαι και μου είναι δύσκολο να μπω στη λογική της εργασίας...

γι΄αυτο ζήτησα βοήθεια...

καταλαβαινώ παντως το να μην επιθυμείς να βοηθήσεις...

 

Στη λογική της εργασίας που εργάζεσαι όμως έχεις μπει. Έτσι δεν είναι; Συνέχισε λοιπόν στην εργασία σου και άσε την εργασία, δεν τη χρειάζεσαι πραγματικά απ'ότι φαίνεται.

 

Αν όντως θες και τα δύο, το να ζητάς την εργασία έτοιμη, είναι πολύ λάθος! Δεν είσαι ούτε ο πρώτος ούτε ο τελευταίος που δουλεύει και σπουδάζει παράλληλα.

[kostikas00]

δεν ειναι σωστη νομιζω...

μηπως μπορειτε να ανεβασετε μια ολοκληρομενη??

please.......

[poscaman]

κι από εδώ;;

 

Καλώς τους.

[Pantelwolf]

Μήπως , λέω μήπως θα έπρεπε να κάνουμε ένα movement ενδοινσομνιακο που να ζητά να μπει στους κανόνες να κλειδώνονται θρεντ τέτοιου στυλ μετά από report? Τώρα τελευταία έχει παραγίνει.

[poscaman]

συμφωνώ ΑΠΟΛΥΤΑ!

[Dr.Fuzzy]

+1 και από μένα.

[narbi]

Α ρε teilam αθάνατο...!

[nikolaos_]

>
/*Krushkal <strong class="highlight">Algorithm</strong>
Input defined as follow
First give number of nodes n
starting end of edge and then ending end of edge and then cost of edge

example:
graph is as follows
1-2 2-5 3-4 4-2 2-3
then 
input is
5
1 2 1
2 5 1
3 4 1
4 2 1
2 3 1

0  to end the input
*/


#define N 100  //N is max nodes
#define M 10000 // M is max edges
#include<iostream>
#include <stdlib.h>
using namespace std;
// UNION FIND DATA STRUCURE STARTS
struct data{
int name;
int size;
struct data *home;
};
typedef struct data mydata;

class makeunionfind
{
public :
mydata S[N];
public:
makeunionfind(int n)
{
   for(int i=0;i<n;i++)
   {
      S[i].name=i+1;
      S[i].size=0;
      
      S[i].home=&S[i];
   }
   
}    
   
void myunion(int a, int 
{
    int sizea,sizeb;
    sizea=S[a-1].home->size;
    sizeb=S[b-1].home->size;
   if(sizea>sizeb)
   {
      (S[b-1].home)->home=S[a-1].home;
      S[a-1].size=sizea+sizeb;
      
   }
   else
   {
       (S[a-1].home)->home=S[b-1].home;
       S[b-1].size=sizea+sizeb;
       
   }
   
}
int myfind(int a)
{
   mydata *temp,*temp2,*stoppoint;
   int result;
   temp2=&S[a-1];
   temp=S[a-1].home;
   while(temp2!=temp)
   {                        
         temp2=temp;
         temp=(*temp2).home;              
   }
   result=temp2->name;
    stoppoint=temp2;
      temp2=&S[a-1];
  //path compression
    do{
          temp=temp2->home;       
          (*temp2).home=stoppoint;
          temp2=temp;         
    }while(temp2!=stoppoint);   
    return result;                                     
}
};
//UNION FIND DATA STRUCURE ends
//Krushkal Algo starts
struct node{
int name;
};
typedef struct node mynode;
class edge
{
   public :
   mynode *start,*end;
   double cost;
   edge()
   {
       start=NULL;
       end=NULL;
       cost=0;
   } 
};
struct edges{
edge e;
};
int compare(const void *a,const void *b )
{
edge *a1,*b1;
a1=(edge*)a;
b1=(edge*)b;
   if(a1->cost<b1->cost)
   return -1;
   else if (a1->cost>b1->cost)
   return 1;
   else
   return 0;
   
}
void *kruskal(edge *e,int n,int m,int *size,edge *ans)
{
   makeunionfind list(n);
   int (*comp)(const void *a,const void *b );
int k=0;
   comp=compare;
   qsort((void*)e,m,sizeof(e[0]),comp);
   for(int i=0;i<m;i++)
   {
       int s,f;
       s=(e[i].start)->name;
       f=(e[i].end)->name;
       
       if(list.myfind(s)==list.myfind(f))
       {
           continue;
       }
       else
       {
         list.myunion(s,f);
         ans[k]=e[i];
         k++;      
       }
   
   }
   *size=k;
   return ans;    

}

int main()
{
   mynode nodes[N];
   edge e[M];
   int n,m; // n is the number of nodes , m is no. of nodes
   cin>>n;
   for(int i=0;i<n;i++){
   nodes[i].name=i+1;
   }
   // temp1 is starting node temp2 is ending node temp3 is cosr
   int temp1,i;   
   cin>>temp1;
   for (i=0;temp1!=0;i++)
   {
       int temp2;
       double temp3;
       cin>>temp2;
       cin>>temp3;
       e[i].start=&nodes[temp1-1];
       e[i].end=&nodes[temp2-1];
       e[i].cost=temp3;
       cin>>temp1;    
   }
   m=i;
     
     edge ans[M];
     int size;
     kruskal(e,n,m,&size,ans);
     
     for(int p=0;p<size;p++)
     {
        cout<<p+1<<")  start "<<(ans[p].start)->name<<"  end "<<(ans[p].end)->name<<endl;
     }
    return 0;

}