3. heti jegyzet (2014.10.16.)

Órai anyag:

Kiegészítettük a széltében keresés pszeudokódját.

Széltében keresés a k csúcsból indítva:
for i:=0..n-1
| v[i]:=-1 // a v ("volt") tömbben jegyezzük fel a távolságokat, illetve a -1-gyel jelezzük, ha még nem vettük fel a listára
v[k]:=0 // a kezdő csúcs önmagától vett távolsága 0
l[0]:=k // a "lista" tömbben jegyezzük fel a feldolgozandó csúcsokat
akt:=0 // akt: a lista tömbben hol tartunk a csúcsok feldolgozásával
kov:=1 // kov: a lista tömbben hol van a következő üres hely
while akt<kov
| foreach sz eleme szomszédok(l[akt])
| | if v[sz]==-1
| | | l[kov]:=sz
| | | kov++
| | | v[sz]:=v[l[akt]]+1
| | | hon[sz]:=l[akt] // a hon tömbben feljegyezhetjük, honnan jöttünk
| akt++

Ezután ki tudjuk iratni a kiinduló pontból egy x csúcsba vezető legrövidebb úton lévő csúcsokat (fordított sorrendben), pl. az alábbi módon:
while x!=k
| print(x)
| x:=hon[x]
print(k)

Absztrakt adattípusok: verem, sor.

Egy adatszerkezet: láncolt lista.

A vermet és a sort implentálhatjuk pl. láncolt lista segítségével, de tömbös megoldások is lehetségesek.
Pl. a széltében keresésben az l tömböt sorként használtuk.

Gráf-reprezentáció:
-szomszédsági mátrix
-éllista
-csúcslista


Házi:

Olvassunk be egy irányított gráfot, és reprezentáljuk csúcslistával!
A bemenet az alábbiakat tartalmazza: a csúcsok száma, az élek száma, majd az élek listája (ahol minden élt két számmal írunk le: az él kezdő- és végpontjának sorszáma).