5. heti jegyzet (2014.11.06.)

Órai anyag:

Hidak megkeresése összefüggő irányítatlan gráfban:
main
| t:=0
| for i:=0 to n-1
| | volt[i]:=false
| mély(0)
| for i:=1 to n-1
| | if me[i]==elérés[i]
| | | print(i, hon[i])
mély(x)
| me[x]:=elérés[x]:=t++
| volt[x]:=true
| foreach y in szomszédok(x)
| | if !volt[y]
| | | hon[y]:=x
| | | mely(y)
| | | if me[x]>me[y]
| | | | me[x]=me[y]
| | else
| | | if y!=hon[x] && me[x]>elérés[y]
| | | | me[x]=elérés[y]


Házi:

Keressük meg a hidakat nem-összefüggő irányítatlan gráfban!