implementacja kruskala

Odpowiedz Nowy wątek
2012-03-13 16:10
0

Witajcie panowie i panie. Mam mały progblem dotyczący implementacji algorytmu Kruskala. WIem jak on działa i wszystko mam rozpisane na małe kawałeczki, jednak nie umiem tego cholerstwa zakodować... nie wiem czego użyć jakiej struktury danych żeby to wszystko się trzymało kupy czy ktoś może mi dać jakieś wskazówki jak się zabrać do tego? Mam tak


const int MAX = 12;

Struct krawedz {
 char v1, v2;
 int waga;
}

krawedz tab[MAX];

for(i=0; i<MAX; i++)
  {
     cin >> tab[i].v1;
     cin >> tab[i].v2;
     cin >> tab[i].waga;
  }
...........

później tu mam sortowanie wstawione. Krawędzie są posortowane w tablicy typu struktury. I mam problem z ostatnią częścią zadania tą najważniejszą ;). Jak scalać drzewa należące do innych lasów ? Przyjmuję, że każdy wierzchołek grafu jest drzewem i łączę drzewa należące do różnego lasu tylko jak to w kodzie rozwiązać i jak się za to zabrać :( pomóżcie...

edytowany 1x, ostatnio: kowal99, 2012-03-13 16:11

Pozostało 580 znaków

2012-03-13 16:26
0

musisz napisać test czy da się przejść pomiędzy dwoma wierzchołkami?
jeśli się da to znaczy, że nowa krawędź jest zbędna, jeśli nie to aktualizujesz nowy graf o nową krawędź.
Opis grafu jedynie za pomocą krawędzi jest w tym przypadku bardzo nieporęczny.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2012-03-13 16:28

Pozostało 580 znaków

2012-03-13 16:29
0

ale jak ten graf ma wyglądać? Jaka struktura miałaby reprezentować ten graf w kodzie tablica? lista? Jeżeli bym zrobił, że każdy las to osobna lista to jak zrobić żeby dynamicznie te listy tworzyć nie wiem jak to opisać za bardzo nie znam aż tak dobrze c++ uczę się dopiero :P i nie bardzo wiem jak np. reprezentować w kodzie las, drzewo?

Pozostało 580 znaków

2012-03-13 16:34
0

Najprościej użyć macierzy sąsiedztwa.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.

Pozostało 580 znaków

2012-03-13 16:39
0

próbowałem tak wpisując w tej macierzy od razu wagi połączeń, ale i tak dalej nie wiem jak połączyć lasy w 1 drzewo zawsze znajdzie się taki graf w którym mi coś nie przejdzie muszą być jakieś zależności między tym przecież...

Pozostało 580 znaków

2012-03-13 16:45
1

#Zaczynasz od pustej macierzy sąsiedztwa (wszędzie zera reprezentujące wagi nieskończoność).
#Bierzesz pierwszą/kolejną krawędź łączącą wierzchołek i z j.
#Patrzysz czy macierz sąsiedztwa umożliwia dotarcie z i do j, jeśli nie to ustawiasz w niej wagi ij oraz ji (na tym polega łączenie drzew).
#skok do 2
koniec algorytmu.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 2x, ostatnio: MarekR22, 2012-03-13 16:48

Pozostało 580 znaków

2012-03-13 16:56
0

a jak zabezpieczyć się przed zrobieniem cyklu?

Pozostało 580 znaków

2012-03-13 20:33
0

W algorytmie Kruskala nie dasię zrobić cyklu (a raczej jest to sprzeczne z założeniami jaki ma być wynik) . Jeśli zrobisz cykl to znaczy, że źle zaimplementowałeś sprawdzanie czy da się przejść między dwoma wierzchołkami.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.

Pozostało 580 znaków

2012-03-13 21:21
0

jak się nie da... na tym polega algorytm. Wyznacza MST i o to wlasnie chodzi. Na wejściu jest graf z którego trzeba wyznaczyć MST... i trzeba go tak wyznaczyć żeby był tym drzewem czyli nie może się pojawić w nim cyklu...

Pozostało 580 znaków

2012-03-13 21:48
0

http://pl.wikipedia.org/wiki/Algorytm_Kruskala

wiki napisał(a)

Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.

Jeśli masz cykl to zawsze można ująć jedną krawędź i nadal utrzymać spójność drzewa, czyli graf z cyklami nie jest najmniejszym możliwym drzewem, ergo twój wynik nie jest zgodny z założeniami co powinien zwracać algorytm Kruskala.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2012-03-13 21:50

Pozostało 580 znaków

2012-03-13 23:05
0

nie będę się kłócił bo mi się nie chce, ale chyba nie masz pojęcia o czym piszemy co to jest MST i na czym polega kruskal (wikipedia to akurat nie jest najlepszy przykład, aby się czegoś nowego dowiedzieć) najwyraźniej nie wiesz też co to znaczy drzewo od razu może napiszę drzewo to spójny graf acykliczny więc ergo jeżeli jest cykl to nie można nazwać tego drzewem. Nie mam cyklu tzn. graf może mieć cykl, ale z tego grafu trzeba zrobić MST więc trzeba cykl wykluczyć. Wiem co powinien zwracać kruskal

edytowany 1x, ostatnio: kowal99, 2012-03-13 23:05

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0