Gráfok


HÁLÓS ADATSZERKEZETEK (HÁLÓ)

A gráf egy homogén, dinamikus adatszerkezet, a fák általánosítása, olyan adatszerkezet, amelyben az elemeknek akárhány megelőzőjük és rákövetkezőjük lehet, beleértve azt is, hogy két elem között olyan kapcsolat van, hogy az egyik a másik megelőzője és rákövetkezője és viszont (kölcsönösen). Egy elem akár önmaga megelőzője és rákövetkezője is lehet. A gráfnak nincs kitüntetet eleme.
A gráf hálózatok modellezésére használható, reprezentálni összefüggő irányított gráf segítségével lehet. A szűkebben vett számítástechnikában csak a hálózatoknál jelenik meg.

Pl.


Gráfok reprezentációjára a szomszédossági listát vagy a szomszédossági mátrixot használják.
A szomszédossági mátrix (csúcsmátrix) egy logikai mátrix, amelynek elemei: 0, 1. Ha a gráfnak n db eleme van, akkor a szomszédsági mátrix n×n-es. Az oszlopokat és a sorokat is a gráf elemeivel címkézzük fel. A mátrix kitöltésének szabálya: a mátrix (i,j) eleme legyen 0, ha az i és j csúcsok között nincs rákövetkező vagy megelőző viszony, különben 1.
A gráf ábrázolására alkalmazható a szétszórt ábrázolás, ahol általában a gráfnak egy multilista felel meg. Mutatótömböket veszek fel az adatelemek mellé. Kezeléshez lehet sorszámozni. Annyi elemű mutatótömböt építek fel, ahány eleme van a hálónak. E tömb elemei mutatótömbök, a mutatótömb elemei a rákövetkezőkre mutatnak.
A gráfon belül útnak nevezzük az olyan elemösszességet, amelyek listát alkotnak. A gráfban körútnak nevezzük az olyan listát, amikor az utolsó elem az elsőre mutat.

Műveletek
Létrehozás: Az üres háló létrehozása, ezután bővítjük. A szomszédossági mátrixban ez egy új sor és egy új oszlop felvételét jelenti, amelyeket megfelelően ki kell tölteni.
Törlés: Egy elem törlése esetén az elemet reprezentáló sort és oszlopot ki kell törölni.
Csere: Megkeresem az elemet és felülírom.
Rendezés, keresés: Nincs.
Bejárás (keresés, háló): Ezen alapszik a gráf feldolgozása. Létezik szélességi és mélységi bejárás.
Szélességi keresés
Az algoritmus a bejárás pillanatnyi állapotát a csúcsok színezésével (fehér, szürke, fekete) tartja számon. Kezdetben minden csúcs fehér, és később szürkére, majd feketére változhat. Egy csúcs elértté válik, amikor először találunk rá a keresés során, és ezután a színe nem lehet fehér. Így a szürke és a fekete csúcsok már elért csúcsok, de a szélességi keresés megkülönbözteti ezeket is: egy fekete csúcs összes szomszédja elért csúcs, de a szürke csúcsoknak lehetnek fehér szomszédjaik, ezek alkotják az elért és a még felfedezetlen csúcsok közötti határt. Tehát eredetileg minden csúcs fehér, kivéve a kezdő csúcsot, amelyik szürke. Egy csúcs akkor válik szürkévé, amikor elértük, és akkor feketévé, ha a belőle kiinduló összes élt már átvizsgáltuk.
A szélességi keresés létrehoz egy szélességi fát, amely kezdetben csak a gyökeret tartalmazza. Kezdőpontnak azt az elemet érdemes választani, amely a legtöbb rákövetkezővel rendelkezik. A fa gyökre az s kezdő csúcs. Ha egy fehér v csúcsot elértünk egy már elért u csúcs szomszédságának vizsgálata során, akkor a fát kiegészítjük a v csúccsal és az (u,v) éllel. Egy csúcsot legfeljebb egyszer érhetünk el.
Az algoritmus kezdetén minden, az s-től különböző csúcs színét fehérre kell állítani. A rákövetkezőit a Q sorban tároljuk, ebben kezdetben csak az s van, majd elemei a szürke csúcsok lesznek. A Q elemeit egy ciklus dolgozza fel, amely addig fut, amíg el nem fogynak a szürke csúcsok (minden csúcs fekete nem lesz), azaz amíg van olyan csúcs, amelynek szomszédsági listáját még nem dolgoztuk fel. A ciklusban kiválasztjuk a Q sor legelső elemét, és ha ennek van olyan szomszéd csúcsa, amelyet még nem értünk el, azaz fehér, akkor a Q sor végére fűzi a csúcsot. Ha a kiválasztott csúcs minden szomszédját megvizsgáltuk, akkor a csúcsot vegyük ki a sorból, és színét változtassuk feketére.
Mélységi keresés
A mélységi keresés során az utoljára elért, új kivezető élekkel rendelkező v csúcsból kivezető, még nem vizsgált éleket derítjük fel. Ha v-hez tartozó összes élt megvizsgáltuk, akkor a keresés „visszalép”, és megvizsgálja annak a csúcsnak a kivezető éleit, amelyből v-t elértük. Ezt addig folytatja, amíg el nem éri az összes csúcsot, amely elérhető az eredeti kezdő csúcsból. Ha marad olyan csúcs, amelyet nem értünk el, akkor ezek közül valamelyiket kiválasztjuk, mint új kezdő csúcsot, és az eljárást ebből kiindulva megismételjük. Ezt egészen addig folytatjuk, amíg az összes csúcsot el nem értük.
A szélességi kereséshez hasonlóan a csúcsok állapotait ebben az esetben is színekkel különböztetjük meg. Kezdetben minden csúcs fehér, amikor elérünk egy csúcsot, akkor szürkére színezzük azt, és befeketítjük, ha elhagytuk, azaz amikor a szomszédsági listájának minden elemét megvizsgáltuk. Ez a módszer biztosítja, hogy minden csúcs pontosan egy mélységi fába kerüljön, azaz, hogy ezek a fák diszjunktak legyenek.
A színezés ugyanígy történik, mint a szélességi keresőnél, de alapvető különbség az, hogy a fát szintenként építem fel.

Egy szintet vissza, vagy vissza a főmenübe.