4. heti jegyzet (2014.10.30.)

Órai anyag:

Erősen összefüggő komponensek, komponensgráf, topológikus rendezés.

Mélységi bejárás a k csúcsból indítva:
main(k)
| for i:=0 to n-1
| | volt[i]:=false
| t:=0
| mély(k)
mély(x)
| elérés[x]:=t++ //elérési idő
| volt[x]:=true
| foreach y in szomszédok(x)
| | if !volt[y]
| | | hon[y]:=x //szülő a feszítőfában
| | | mély(y)
| elhagyás[x]:=t++ //elhagyási idő

Élek osztályozása:
-fa él
-vissza él
-kereszt él
-előre él


Házi:

Keressük meg a leghosszab, adott csúcsból induló út hosszát egy súlyozott, irányított, körmentes gráfban!
Bemenet: csúcsok száma, élek száma, kiinduló csúcs, majd az egyes élek leírása következik. Minden élt három számmal írunk le: kiindulópont, végpont, súly.