implementacja kruskala

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.

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?

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

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ż...

#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.

a jak zabezpieczyć się przed zrobieniem cyklu?

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.

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...

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.

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

W którym miejscu pomyliłem pojęcie drzewo-graf?
Najwyraźniej się nie rozumiemy na innym poziomie.
Prawidłowo działający algorytm Kruskala na wejściu dostaje graf (z potencjalnymi cyklami) na wyjściu zawsze drzewo.
Ja zrozumiałem, że na wyjściu dostajesz graf z cyklami, bo to jest jedyna możliwość kiedy możesz mieć problem z cyklami w tym algorytmie.
Na początku algorytmu masz niepołączone wierzchołki (zero cykli, bo zero krawędzi), a następnie łączysz je tylko wtedy, gdy dana krawędź nie doprowadzi do cyklu (inny sposób powiedzenia, że przed dodaniem krawędzi nie da się przejść pomiędzy danymi wierzchołkami).
Jeśli twierdzisz, że masz problem z cyklami, znaczy, że ty coś nie rozumiesz względnie źle zaimplementowałeś, bo w trakcie tego algorytmu cykle nie mogą się pojawić, nawet wtedy, gdy graf wejściowy je ma.

"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)", a jak zrobić tan krok jaki warunek ?

Wlasnie się głowie nad tym od paru godzin, jak majac graf w postaci macierzy sasiedztwa to zrobić ( alg. Kruskala). Powiedzmy , że mam takie coś na wejsciu :

X | 0 | 1 | 2 | 3 |
0 0 4 1 3
1 4 0 5 0
2 1 5 0 2
3 3 0 2 0

Jak to rozrysuje na kartce mam cos na kształt kwadratu z jedną przekątną, powiedzmy ze mam taki graf wejsiowy ( te liczby w macierzy to wagi połączeń oczywiście , jak jest 0 to brak połączenia)

Dobra i zaczynam, powiedzmy ze mam drugą taką macierz , na razie wyzerowaną do niej chce wkladac pokolei odpowiednie elementy, aby uzyskac minimalne drzewo rozpinajace.

Zaczynam od znalezenie polaczenia o najmniejszej wadze - to 1 łączaca 0 z 2.
Potem dodaje polaczenie 2 z 3 -> waga 2 ... i teraz zaczynają sie schody, kolejna do daodania leci 3 z 0 (waga 3), ktore zrobi mi cykl i to trzeba odrzucić.

Jak to sprawdzac w programie, w macierzy ? Za cholerę tego nie widzę

W pierwszym kroku połączyłeś krawędzie 0 z 2 wiec w kolumnach oraz wierszach 0 i 2 już nie szukasz.
W drugi kroku połączyłeś krawędzie 2 z 3 wiec w kolumnach oraz wierszach 0, 2 i 3 już nie szukasz.
zostaje 0 z 1 waga 4

Mam problem z implementacją tego. Stworzylem dwie tablice dwuwymierowe : macierz z informacja o wszystkich polaczeniach oraz graf w ktorej znajdzie sie na koniec gotowe drzewo rozpinające. Na początku graf mam wyzerowany.

1. Najpierw znajduje najmniejsza wage w macierzy i przepisuje to do grafu, bo wiadomo jedno połączenie miec muszę.
2. Teraz musze szukac kolejnego o wadze wiekszej niz poprzednia(badz rownej...)
   ale najmniejszej sposrod tych ktore mam...

Nie potrafie tego zaimplementowac...
Poza tym chyba potrzebna bedzie jeszcze jedna macierz 'flag', bo ostatni wierzcholek musi byc dodany w miejscie gdzie na calej kolumnie oraz wierszu ktore sa na przecieciu tego miejsca są same zera.

void Znajdz_Kolejny_I_Polacz(int ** Macierz,int **Graf,int n,int & waga){

	   int w=0;
	   int k=0;
	   int temp;

      for(int i = 0; i < n; i++)
         for(int j = 0; j < n; j++){
		       if(Macierz[i][j]!=0 && Macierz[i][j]!=waga ){
				      temp=Macierz[i][j];
					    if(

				      waga=Macierz[i][j];   // tutaj bedzie najkrotsze polaczenie
			          w=i;
					  k=j;          // wiem w ktorym wierszu i kolumnie jest najmniejszy element
		       }

		 }

		 Graf[w][k]=waga;
		 Graf[k][w]=waga;

	} 

Poza tym jest sytuacja gdzie beda np 3 polaczenia tej samej wagi...
Moze stworzyc liste do ktorej wpakuje wagi wszystkich polaczen róznych od zera ( przeszukac tylko powyzej gornej przekatnej Macierz ), potem je posortuje rosnaco i bede wyszukiwac kolejne elementy w tej macierzy o danej wadze ?

Pierwszy węzeł możesz wybrać dowolny, np z indeksem 0 dopisujesz go do puli wybranych.
Krawędź wybierasz najmniejszą łączącą już wybrany węzeł z jeszcze nie wybranym, po wybraniu krawędzi dopisujesz drugi węzeł do puli wybranych.
Jeżeli nie rozumiesz jakiegoś słowa to powiedz którego, jeżeli jedynie co cię zadowoli to gotowiec to też to wprost napisz.

_13th_Dragon napisał(a):

Pierwszy węzeł możesz wybrać dowolny, np z indeksem 0 dopisujesz go do puli wybranych.
Krawędź wybierasz najmniejszą łączącą już wybrany węzeł z jeszcze nie wybranym, po wybraniu krawędzi dopisujesz drugi węzeł do puli wybranych.
Jeżeli nie rozumiesz jakiegoś słowa to powiedz którego, jeżeli jedynie co cię zadowoli to gotowiec to też to wprost napisz.

To nie prawda , nie wybieram najmniejszej już łączącej , tak jest w alg. Prima a nie Kruskala. Polecam poniższy przykład.

http://www.jarocin.cba.pl/STRONY/ALGORYTM%20KRUSKALA/krok.html

Pokazał także że moja koncepcja jest również błędna co do ustawiania flag, ten przykład jest dobry do sprawdzania. Pierwsze 2 elementy mozna dodac do tablicy grafu zawsze, natomiast potem musimy sprawdzać czy dodając kolejny nie tworzymy cyklu, czyli pętli tak jakby.

Nie wiem czy się rozumiemy, ale sprawa nie jest prosta.

po prostu narysowalem sobie macierz pusta 6x6 i uzupelnialem ja tak jak kolejno w tym przykladzie sa dodawane połączenia. Po dodaniu tych 2 co w tym przykladzie,
kazdy moglby byc nastepnym gdyby mial najmniejsza wage. Patrzac na uzupelniona tablice grafu nie potrafie jak zrobic warunek na to czy stworzy się cykl czy tez nie po dodaniu okreslonego polaczenia

misiek123 napisał(a):

_13th_Dragon napisał(a):

Pierwszy węzeł możesz wybrać dowolny, np z indeksem 0 dopisujesz go do puli wybranych.
Krawędź wybierasz najmniejszą łączącą już wybrany węzeł z jeszcze nie wybranym, po wybraniu krawędzi dopisujesz drugi węzeł do puli wybranych.
Jeżeli nie rozumiesz jakiegoś słowa to powiedz którego, jeżeli jedynie co cię zadowoli to gotowiec to też to wprost napisz.

To nie prawda , nie wybieram najmniejszej już łączącej , tak jest w alg. Prima a nie Kruskala. Polecam poniższy przykład.

http://www.jarocin.cba.pl/STRONY/ALGORYTM%20KRUSKALA/krok.html

To co napisałeś można nazwać jedynie majaczeniami, dowody na to poniżej.

Kim jest ten jarocin i czemu uważasz że on cokolwiek słyszał o algorytmie Kruskala ?
A jeżeli masz pewność że słyszał to czemu uważasz że on cokolwiek zrozumiał?

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