Akarok irni egy kruskal algoritmust es nem tudom hogy ellenorizzem le, hogy van e kor a grafban amikor be rakok egy elet. Eleg gyors ha megnezem hogy az el egyik vegebol el tudok e jutni a masik vegebe?

[link]

Még kód se kell, itt az algoritmus levezetése. Csoportokba rakod a csúcsokat, és az élek behúzásánál összeveted a két csúcs csoportját. Ha eltérő, behúzod az élt, és egy csoport alá vonod az összes kapcsolódó csúcsot. Ha azonos csoportban van, akkor kör keletkezne, tehát az az él nem játszik.

Wiki szerint:

"Az éleket súlyuk szerint növekvő sorrendbe rendezzük, és sorra megvizsgáljuk, hogy melyeket vehetjük be a megoldásba. Annak ellenőrzése, hogy egy vizsgált él nem zár be kört, nagyon egyszerű. Kezdetben a gráf minden csúcsa egy-egy halmazt alkot. Egy vizsgált él akkor kerül be a megoldásba, ha a két végpontja két különböző halmazban van, és ekkor a két halmazt egyesítjük. Addig folytatjuk, amíg egy halmazt kapunk eredményül."

[link]

Angol wiki pszeudo kód:

[link]

KRUSKAL(G):

1_A = ∅

2_foreach v ∈ G.V:

3___MAKE-SET(v)

4_foreach (u, v) in G.E ordered by weight(u, v), increasing:

5___if FIND-SET(u) ≠ FIND-SET(v):

6_____A = A ∪ {(u, v)}

7_____UNION(u, v)

8_return

Attól, hogy az algoritmus jó, még lehet hiba a megvalósításban.

Ha a gráfban egy sétával visszajutsz a kezdőpontba, akkor lehet, hogy kétszer vagy többször is áthaladtál ugyanazon a ponton. Erre teszteléskor ügyelned kell.