od David Nohejl » 20. 6. 2005 15:11
Minimalni kostra.
Dal sem to za tri.. napsal sem kruskala a jarnika, "skoro" sem dokazal spravnost.. mohla to bejt dvojka
Samozrejme se ptal jak se efektivne najde cyklus, ja mu rek to slejvani komponent - oprava: ja mu rek to hloupejsi slejvani komponent, on rikal ze sme se ucili efektivnejsi zpusob, ja sem rek jo jasne, ty sefy... jo byly to sefove
Ale stejne sem se v tom trochu zamotal a hlavne sem mel nedomysleny dukaz toho ze kruskal opravdu najde minimalni kostru - cca v pulce dukazau sem se zasek
Trochu me prekvapilo ze si vlastne jenom precet co sem napsal, a kdyz sem to mel blbe tak se teprve ptal... myslel sem teda ze budu muset mluvit vic. Co sem videl tak kolegove meli AVL, dk prumerne hloubky BVS atd... IIRC ten s AVL to nedal.. zbytek nevim, rychle sem vypad na obed.
Minimalni kostra.
Dal sem to za tri.. napsal sem kruskala a jarnika, "skoro" sem dokazal spravnost.. mohla to bejt dvojka :( Samozrejme se ptal jak se efektivne najde cyklus, ja mu rek to slejvani komponent - oprava: ja mu rek to hloupejsi slejvani komponent, on rikal ze sme se ucili efektivnejsi zpusob, ja sem rek jo jasne, ty sefy... jo byly to sefove :) Ale stejne sem se v tom trochu zamotal a hlavne sem mel nedomysleny dukaz toho ze kruskal opravdu najde minimalni kostru - cca v pulce dukazau sem se zasek :(
Trochu me prekvapilo ze si vlastne jenom precet co sem napsal, a kdyz sem to mel blbe tak se teprve ptal... myslel sem teda ze budu muset mluvit vic. Co sem videl tak kolegove meli AVL, dk prumerne hloubky BVS atd... IIRC ten s AVL to nedal.. zbytek nevim, rychle sem vypad na obed.