» »

Kruskalov algoritem težave pri implementaciji

Kruskalov algoritem težave pri implementaciji

zacetnik11 ::

Pozdravljeni
ZA faks morem na implementirat Kruskalov algoritem. Zadevo razum v potankosti, samo ne najdem napake pri sami kodi.
Prosil bi če mi lahko kdo pomaga.
Vse naredi vredu, težava je pri polju v, kjer spreminjam vrednsoti vozlisc.

Hvala za pomoč in odgovore.

/*
1
7
0 7 1000 5 1000 1000 1000
7 0 8 9 7 1000 1000
1000 8 0 1000 5 1000 1000
5 9 1000 0 15 6 1000
1000 7 5 15 0 8 9 
1000 1000 1000 6 8 0 11
1000 1000 1000 1000 9 11 0
2
3
4
*/
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

const int velikost = 21;

struct povezave
{
 int vozlisce_prvo;
 int vozlisce_drugo;
 int utez;
};

void preberi_datoteko(int polje[velikost][velikost], int stevilo_rocno)
{
 for(int i=0; i < stevilo_rocno; i++)
 {
         for(int j=0; j < stevilo_rocno; j++)
         {
                 cin >> polje[i][j];
         }
 }    
 
}

/************************* hitro uredi *************************************/
void zamenjaj_vrednosti(povezave &drugi, povezave &prvi)
{
     povezave temp;
     temp=prvi;
     prvi=drugi;
     drugi= temp;     
} 

/* funkcija deli */
int deli(povezave tabela_povezav[], int dno, int vrh)
{
     int w = tabela_povezav[dno].utez;
     int i = dno;
     int j = vrh+1;
     

     
     while(true)
     {
                do
                {
                j = j-1;
                }
                while(tabela_povezav[j].utez > w);
                
                do
                {
                i = i+1;
                }
                while(tabela_povezav[i].utez < w);
                
                if(i < j)
                 zamenjaj_vrednosti(tabela_povezav[i],tabela_povezav[j]);
                else
                {
                zamenjaj_vrednosti(tabela_povezav[j], tabela_povezav[dno]);
                return j;         
                }          
     }
}
/* funkcija hitro uredi */
void algoritem_hitro_uredi(povezave tabela_povezav[], int dno, int vrh)
{
     if(dno < vrh)
     {
     int delilni_elemen = deli(tabela_povezav, dno, vrh);
     algoritem_hitro_uredi(tabela_povezav, dno, delilni_elemen - 1);
     algoritem_hitro_uredi(tabela_povezav, delilni_elemen + 1, vrh);       
     }
     
     
}
/********************** KONEC hitro uredi *************************************/


void vnos_povezav(povezave tabela_povezav[], int stevila_rocno, int polje[velikost][velikost],  int& stevilo_povezav_index)
{
     povezave povezave_prva_druga;
     
     for(int i=0; i < stevila_rocno; i++)
     {
             for(int j=i; j < stevila_rocno; j++)
             {
             
              if(polje[i][j] != 1000 && polje[i][j] != 0)
              {
                             
               povezave_prva_druga.vozlisce_prvo = i;
               povezave_prva_druga.vozlisce_drugo = j;
               povezave_prva_druga.utez = polje[i][j];
              
               tabela_povezav[stevilo_povezav_index]= povezave_prva_druga;
               stevilo_povezav_index++;
              }
             }
     }
}


void kruskalov_algoritem(povezave tabela_povezav[], int v[], int stevilo_rocno, povezave mini_drevo_povezav[], int stevilo_povezav_index,  int& stevec_drugi)
{
  
 algoritem_hitro_uredi( tabela_povezav, 0, stevilo_povezav_index);
 
 for(int i=0; i < stevilo_rocno; i++)
 {
     mini_drevo_povezav[i].vozlisce_prvo =-10;
     mini_drevo_povezav[i].vozlisce_drugo =-10;    
     mini_drevo_povezav[i].utez = -10;        
 }   
 
 for(int j=0; j < stevilo_rocno; j++)
 {
 v[j]=j;
 }
 


 for(int l=0; l < stevilo_povezav_index; l++)
 {
         
  if(v[tabela_povezav[l].vozlisce_prvo] != v[tabela_povezav[l].vozlisce_drugo])
  {  
                                                                           
   mini_drevo_povezav[stevec_drugi].vozlisce_prvo = tabela_povezav[l].vozlisce_prvo;
   mini_drevo_povezav[stevec_drugi].vozlisce_drugo = tabela_povezav[l].vozlisce_drugo;
   mini_drevo_povezav[stevec_drugi].utez = tabela_povezav[l].utez;
   stevec_drugi++;
     
   int primerjava = v[tabela_povezav[l].vozlisce_drugo];
  
  /* Tukaj je težava, ker mi ne spremeni vrednosti v tabeli v[] in mi naredi preveč povezav */  
        for(int k=0; k < stevilo_rocno; k++)
        {        
                if(v[k] == primerjava )
                {
                  v[k] = v[tabela_povezav[l].vozlisce_prvo];
                }
        }  
  }
  
 }    
                       
}

/*****************************************************************************/
void  izpis(povezave drevo_povezav[], int stevec_drugi)
{
      cout << "Vpeto drevo: " << endl;
      for(int i=0; i < stevec_drugi; i++)
      {
       cout << "Vozlisce:" << drevo_povezav[i].vozlisce_prvo << " --> ";
       cout << "Vozlisce:" << drevo_povezav[i].vozlisce_drugo << " --> ";
       cout << "Utez:" << drevo_povezav[i].utez << endl;
      }
}


int main(int argc, char *argv[])
{
    int izbor_menija=0;
    int stevilo_rocno = 0;
    int polje[velikost][velikost];
    int stevilo_povezav_index =0;
    povezave tabela_povezav[velikost];
    int stevec_drugi=0;
    
    int v[velikost];
    povezave drevo_povezav[velikost];
    int indeks_minDrevo=0;
    
    
    
     do
    {
        cout << "**************************************************************" << endl;
        cout << "*        Kruskalov algoritem - izbira:                       *" << endl;
        cout << "*                                                            *" << endl;
        cout << "*     1. Vnos podatkov - rocni                               *" << endl;
        cout << "*     2. Zagon Kruskalovega algoritma                        *" << endl;
        cout << "*     3. Izpis minimalnega vpetega drevesa                   *" << endl;
        cout << "*     4. Konec                                               *" << endl;
        cout << "*                                                            *" << endl;
        cout << "**************************************************************" << endl;
        cout << "      Vasa izbira:";
        cin  >> izbor_menija;
        
        switch(izbor_menija)
        {
         case 1:
              cout << endl;
              cout << "     Koliko vozlisc zelis vnesti:";
              cin >>  stevilo_rocno;
               cout << endl;
              preberi_datoteko( polje, stevilo_rocno);
              vnos_povezav(tabela_povezav, stevilo_rocno, polje,  stevilo_povezav_index);
         break;
         case 2:
               cout << endl;
               
               kruskalov_algoritem( tabela_povezav,  v,  stevilo_rocno,  drevo_povezav, stevilo_povezav_index, stevec_drugi);
     
               cout << endl;
         break;
         case 3:
               cout << endl;
           izpis( drevo_povezav,  stevec_drugi);
            cout << endl << endl;
         break;
         case 4:
             exit (1);
         break;    
        }
    }
    while(izbor_menija != 4) ;
     
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

amacar ::

Tu imaš lepo opisan algoritem in njegov psevdokod, ki ga le dopolniš za 4 različne možnosti: http://www10.zippyshare.com/v/40452277/...

Spura ::

Celotna stvar je zelo bizarno napisana, drugace bi pa moralo delat.

Mesar ::

Spura je izjavil:

Celotna stvar je zelo bizarno napisana, drugace bi pa moralo delat.


Kar pomeni?
Your turn to burn!

Spura ::

Sprasujem se, ce je res napaka v tistem kosu kode.

zacetnik11 ::

Hvala za odgovore.
ZAnima me če lahko @spura malo bolj rayložiš, zakaj je koda bizarno napisana?
Koda je napisana v strukturnem c++, in ne v objektnem, prav tako nismo uporabili kazalcel.
Drugače so pa bila navodila za izdelavo programa takšna (strukturno in ne uporaba kazalcel).

LP G.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Izdelava algoritma

Oddelek: Znanost in tehnologija
61544 (924) Klemen86
»

križci krožci c # (strani: 1 2 )

Oddelek: Programiranje
5011873 (10532) Yacked2
»

java pomoč

Oddelek: Programiranje
211961 (1353) kr?en
»

osnove v Javi - zvezdice

Oddelek: Programiranje
403540 (2762) Tutankhamun
»

c++ in linux/windows

Oddelek: Programiranje
121726 (1602) rapvirus

Več podobnih tem