Forum » Programiranje » 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.
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/...
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.
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 ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | Izdelava algoritmaOddelek: Znanost in tehnologija | 1538 (918) | Klemen86 |
» | križci krožci c # (strani: 1 2 )Oddelek: Programiranje | 11788 (10447) | Yacked2 |
» | java pomočOddelek: Programiranje | 1947 (1339) | kr?en |
» | osnove v Javi - zvezdiceOddelek: Programiranje | 3521 (2743) | Tutankhamun |
» | c++ in linux/windowsOddelek: Programiranje | 1712 (1588) | rapvirus |