Szathmáry László honlapja @ DEIK

Gráfbejárások

A gráfokról itt olvashat többet: adatszerkezetek-11.

Tekintsük a következő gráfot:

Adjuk meg a gráf leírását egy fájlban JSON formátumban:

{
  "a": ["b", "f", "g"],
  "b": [],
  "c": ["a"],
  "d": ["f"],
  "e": ["d", "e"],
  "f": ["e"],
  "g": ["c", "e", "j"],
  "h": ["g", "i"],
  "i": ["h"],
  "j": ["k", "l", "m"],
  "k": [],
  "l": ["g", "m"],
  "m": ["l"]
}

A csúcsokat betűkkel címkézzük. A bejárás során 3 kategóriát különböztetünk meg ("fekete", "szürke", ill. "fehér" csúcsok). A fekete csúcsok lesznek a már bejárt csúcsok; a szürke csúcsok azok, melyeket már látunk a feketékből; a fehér csúcsok pedig még nem is látszanak. Amikor egyszerre több csúcsot is át kell tenni a 2. kategóriába (a "szürke" csúcsok közé), akkor a könnyebb ellenőrizhetőség kedvéért a csúcsokat ábécésorrendben tegyük be.

Szélességi bejárás

Járjuk be a gráfot az "a" csúcsból kiindulva szélességi bejárással, s írassuk ki a csúcsok bejárási sorrendjét. Ha a "szürke" csúcsok közé ábécésorrendben tettük be az elemeket, akkor a következő bejárási sorrendet kell kapnunk: a b f g e c j d k l m h i.

A szélességi bejárás esetén a "szürke" csúcsokat egy sor adatszerkezetben tároljuk. Ehhez felhasználhatjuk a köv. kódrészletet:

import Queue

q = Queue.Queue()

for i in range(5):
q.put(i)

while not q.empty():
print(q.get())

A fenti kódrészlet kimenete:

$ python3 Queue_fifo.py

0
1
2
3
4

A Queue osztályról itt olvashat többet.

Mélységi bejárás

Járjuk be a gráfot az "a" csúcsból kiindulva mélységi bejárással, s írassuk ki a csúcsok bejárási sorrendjét. Ha a "szürke" csúcsok közé ábécésorrendben tettük be az elemeket, akkor a következő bejárási sorrendet kell kapnunk: a g j m l k e d c f b h i.

A mélységi bejárás esetén a "szürke" csúcsokat egy verem adatszerkezetben tároljuk. Ehhez felhasználhatjuk a köv. kódrészletet:

import Queue

q = Queue.LifoQueue()

for i in range(5):
q.put(i)

while not q.empty():
print(q.get())

A fenti kódrészlet kimenete:

$ python3 Queue_lifo.py

4
3
2
1
0

A Queue osztályról itt olvashat többet.

20130528a

Gráfbejárások