[c++] ALGORYTM KRUSKALA I PRIMA

Problemy dotyczące programowania.

Moderatorzy: Moderatorzy, Administratorzy

Awatar użytkownika
millena
Użytkownik
Posty: 124
Rejestracja: 2006-03-20, 14:37
Lokalizacja: /dev/null
Kontakt:

[c++] ALGORYTM KRUSKALA I PRIMA

Post autor: millena »

Kruskala sobie napisałam, po ciężkiej katordze :) Potrzebuje pomocy z Primem. Musi byc na tym samym grafie, który mam w tym pliku.

Kod: Zaznacz cały

class Krawedz
{
    public:
        int stad;
        int dokad;
        int waga;
};
Chyba jakoś tak to było :) Na dole wklejam kod moich wypocin.

http://pastebin.com/TszaN5ZK

Proszę o pomoc.
[color=green]dd if=/home/millena of=/dev/null [/color]-> [color=olive]od kiedy kieruje backupy do /dev/null idą o wiele szybciej [/color] [img]http://mandrivauser.ovh.org/.image/fftoie.gif[/img]
Awatar użytkownika
mina86
Moderator
Posty: 3343
Rejestracja: 2004-06-14, 21:58
Lokalizacja: Linux 5.x x86_64
Kontakt:

Re: [c++] ALGORYTM KRUSKALA I PRIMA

Post autor: mina86 »

Po co własna funkcja sortowania? std::sort() powinno wystarczyć.

Mieszasz malloc() i delete. W C++ zalecanym sposobem jest alokowanie poprzez "new" i zwalnianie poprzez "delete" lub "delete[]" w przypadku tablic.

A w ogóle to możesz zresztą użyć std::vector.

Do wypełnienia tablicy zerami może posłużyć std::fill_n(A + 1, n, 0) (o ile dobrze pamiętam kolejność argumentów).

Wydaje się, że alokujesz o dwa elementy za dużo.

Co do Prima, to czy Wiki nie jest pomocna?
Zastrzegam sobie prawo nieanalizowania postów pisanych niepoprawną polszczyzną.
Post generated automatically by A.I. system code name ‘mina86’ in response to the previous one.
Awatar użytkownika
millena
Użytkownik
Posty: 124
Rejestracja: 2006-03-20, 14:37
Lokalizacja: /dev/null
Kontakt:

Re: [c++] ALGORYTM KRUSKALA I PRIMA

Post autor: millena »

Dzięki Mina86, zaraz poprawie, bo rzeczywiście, coś mi nie działam zbyt dobrze.
No Prim, ok na Wiki, ale chciałam zrobić na liście Krawędzi... Ale okazało się, że nie muszę, więc poradzę sobie z Primem robiąc go na Macierzy Wag.
A macie jakiś sposób na inne liczenie czasu (bardziej dokładnie), bo clock() dla grafu 25-100% dla 100 krawedzi wywala mi 0 (przy zmianie sortowanie na quick). ????

Właśnie od rana ruszam tego std::sort(), ale nie wiem, jak posortowac "tablice" struktur/klas???
[color=green]dd if=/home/millena of=/dev/null [/color]-> [color=olive]od kiedy kieruje backupy do /dev/null idą o wiele szybciej [/color] [img]http://mandrivauser.ovh.org/.image/fftoie.gif[/img]
Awatar użytkownika
mina86
Moderator
Posty: 3343
Rejestracja: 2004-06-14, 21:58
Lokalizacja: Linux 5.x x86_64
Kontakt:

Re: [c++] ALGORYTM KRUSKALA I PRIMA

Post autor: mina86 »

Dodaj gdzieś funkcję:

Kod: Zaznacz cały

bool operator<(const Krawedz &a, const Krawedz &b) {
    return a.waga < b.waga;
}
Z taką funkcją wystarczy coś w stylu std::sort(k, k + n);.

Do mierzenia czasu oczywiście gettimeofday() choć on mierzy czas zegarowy, a nie wykorzystany przez program. Jeżeli jest to problemem można próbować getrusage().
Zastrzegam sobie prawo nieanalizowania postów pisanych niepoprawną polszczyzną.
Post generated automatically by A.I. system code name ‘mina86’ in response to the previous one.
Awatar użytkownika
millena
Użytkownik
Posty: 124
Rejestracja: 2006-03-20, 14:37
Lokalizacja: /dev/null
Kontakt:

Re: [c++] ALGORYTM KRUSKALA I PRIMA

Post autor: millena »

Oooo, super... Właśnie zaczęłam badania robić :)
[color=green]dd if=/home/millena of=/dev/null [/color]-> [color=olive]od kiedy kieruje backupy do /dev/null idą o wiele szybciej [/color] [img]http://mandrivauser.ovh.org/.image/fftoie.gif[/img]
Awatar użytkownika
millena
Użytkownik
Posty: 124
Rejestracja: 2006-03-20, 14:37
Lokalizacja: /dev/null
Kontakt:

Re: [c++] ALGORYTM KRUSKALA I PRIMA

Post autor: millena »

Odgrzebuje stary temat, bo potrzebuje kodu kruskalowego i primowego, ale w wersji na std::map.
Czy ktoś jest mi w stanie pomóc to przerobić?

Z góry dziękuje,

http://pastebin.com/99pjtQ3L
[color=green]dd if=/home/millena of=/dev/null [/color]-> [color=olive]od kiedy kieruje backupy do /dev/null idą o wiele szybciej [/color] [img]http://mandrivauser.ovh.org/.image/fftoie.gif[/img]
Awatar użytkownika
webster
Użytkownik
Posty: 1269
Rejestracja: 2009-10-06, 11:58
Lokalizacja: Gdańsk
Kontakt:

Re: [c++] ALGORYTM KRUSKALA I PRIMA

Post autor: webster »

beuhuehe, myślę, że od listopada już dała radę się z tym uporać :p
††† Chaos Of The Mirror - Valheru †††
††† I ♥ SlackWare RuLeZ †††

Slackware Poland FaceBook
ODPOWIEDZ