Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 08. 02. 2010 09:17
Tarjanuv algoritmus
Ahojda mohl by mi prosim nekdo nejak polopate vysvetlit jak funguje Tarjanuv algorutmus?
priklad mam treba tento: Maji se najit pomoci tarjanova algoritmusilne souvisle komponenty grafuG=(V,E) , V=(1..,11) a E je dana vyctem:
(1,5) (3,9) (5,9) (7,2) (9,8) (10,6)
(2,1) (4,6) (5,10) (7,11) (9,10) (11,8)
(2,7) (5,4) (6,5) (8,11) (10,3)
Dekuju
Offline
- (téma jako nevyřešené označil(a) jelena)
#2 08. 02. 2010 12:42
#4 08. 02. 2010 18:04
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Tarjanuv algoritmus
↑ Lucky11: Ok. A co na tom googlu píšou?
google napsal(a):
Udělejte DFS a každému číslu přiřaďte
Nepíšou odkud začít, tak začneme z vrcholu číslo 1, nakreslíme DFS strom a index zapíšeme do závorky
1(1)---5(2)---4(3)---6(4)
|---9(5)---8(6)---11(7)
|--10(8)---3(9)
2(10)---7(11)
google napsal(a):
Zjistěte pro každý vrchol nejnižší index vrcholu, do kterého se z něj ze dostat.
Opět v závorkách:
1(1)---5(2)---4(2)---6(2)
|---9(2)---8(6)---11(6)
|--10(2)---3(2)
2(10)---7(10)
Vrcholy, které mají v závorce stejné číslo (ve druhém případě) tvoří komponenty souvislosti.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#6 21. 01. 2014 18:25
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Re: Tarjanuv algoritmus
Opět v závorkách:
1(1)---5(2)---4(2)---6(2)
|---9(2)---8(6)---11(6)
|--10(2)---3(2)
2(10)---7(10)
Takže pro každý vrchol pustím DFS zvlášť a zjišťuji číslo nejnižšího indexu? není to nějak moc pomalé :-o
nebo jak se tato část dělá?
Offline