Ha ezt az üzenetet látod, az annak a jele, hogy külső anyagok nem töltődnek be hibátlanul a honlapunkra.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Fő tartalom

Gráfok ábrázolása

Többféleképpen lehet programban gráfot ábrázolni. Minden módszernek megvan az előnye és a hátránya. Egyes helyzetek vagy algoritmusok, ahol gráf az input, más-más formátumot írnak elő. Itt most három módszert mutatunk be.
Három szempontot fogunk figyelembe venni. Az egyik a memóriaigény, az egyes leképezési módszerekhez szükséges tárkapacitás. Ehhez aszimptotikus jelölésrendszert fogunk használni. Igen, az aszimptotikus jelölésrendszer másra is alkalmas, nem csak futásidő mérésére! Alapvetően függvények jellemzésére való, és egy függvény futásidőt, tárigényt, vagy bármilyen más erőforrás-szükségletet is jellemezhet. A másik két szempont az időigényre vonatkozik. Az egyiknél azt vizsgáljuk, hogy mennyi időt vesz igénybe annak eldöntése, hogy egy adott él szerepel-e a gráfban. A másik azt nézi meg, mennyi idő kell egy csúcspont szomszédainak megkereséséhez.
Gyakran a csúcspontokat nem nevekkel (pl. „Audrey”, „Boston” vagy „pulcsi”), hanem számokkal azonosítunk úgy, hogy a |V| számú csúcspontot sorszámozzuk 0-tól |V|1-ig. Az ábrán a szociális hálózati gráfunk látható a 10 csúcsponttal, nevek helyett sorszámmal:

Éllista

Gráf ábrázolásának egyszerű módja az |E| él felsorolása egy listában vagy tömbben. Ezt éllistának hívjuk. Az éleket az élhez illeszkedő csúcspont-párok tömbjével, vagy egy csúcspont-párokat tartalmazó objektumtömbbel ábrázoljuk. Ha az élekhez súlyokat is rendeltünk, akkor a tömb soraihoz egy harmadik oszlop is tartozik, illetve az objektumhoz további információt adunk, ami az él súlyát tartalmazza. Mivel minden élhez két vagy három szám tartozik, az éllista tárhely igénye Θ(E). Például a szociális hálózati gráf megvalósítása JavaScriptben így néz ki:
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]
Az éllisták egyszerűek, de ha arra vagyunk kiváncsiak, hogy egy adott él szerepel-e a gráfban, a teljes listát végig kell nézni. Ha az élek az éllistában tetszőleges sorrendben vannak, akkor ez |E| elem lineáris keresését jelenti. Elgondolkodtató kérdés: hogyan szervezzük meg az éllistánkat, hogy egy adott él keresése O(lgE) időt igényeljen? A megoldás egy kicsit trükkös.

Szomszédsági mátrix

Egy |V| csúcsponttal rendelkező gráf esetében a szomszédsági mátrix egy |V||V| méretű, 0-kat és 1-eket tartalmazó mátrix, ahol az i-edik sor j-edik oszlopában akkor és csak akkor van 1, ha az (i,j) él szerepel a gráfban. Ha az élhez rendelt súlyt is ábrázolni akarod, akkor azt kell beírni az i-edik sor j-edik oszlopába, és meg kell határozni egy speciális értéket (például a null értéket) a nem létező él jelöléséhez. Az ábrán a szociális hálózat gráfjának szomszédsági mátrixa látható:
A JavaScriptben ezt a mátrixot így ábrázoljuk:
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
A szomszédsági mátrixban konstans idő kell ahhoz, hogy megállapítsuk, egy adott él létezik-e; egyszerűen beolvassuk a mátrix megfelelő elemét. Például, ha a szomszédsági mátrixunk neve graph, akkor úgy tudjuk megvizsgálni, hogy az (i,j) él szerepel-e a gráfban, hogy megnézzük graph[i][j] értékét. Akkor mi a szomszédsági mátrix hátránya? Kettő is van. Először is Θ(V2) a helyigénye, még akkor is, ha graph ritka mátrix, vagyis ha viszonylag kevés élt tartalmaz. Más szóval ritka mátrix esetén a szomszédsági mátrix túlnyomórészt 0-kból áll, ezért néhány él tárolásához sok memória kell. Másodszor, ha arra vagy kíváncsi, hogy egy adott i csúcsnak mik a szomszédai, akkor végig kell nézned az i sor összes |V| elemét, még akkor is, ha az i csúcsnak csak kevés szomszédja van.
Egy irányítatlan gráf szomszédsági mátrixa szimmetrikus: az i-edik sor j-edik eleme akkor, és csak akkor 1, ha a j-edik sor i-edik eleme is 1. Irányított gráf esetében a szomszédsági mátrixnak nem kell szimmetrikusnak lennie.

Szomszédsági lista

A szomszédsági lista a szomszédsági mátrix és az éllista kombinációja. Az egyes i csúcspontokhoz tároljuk a vele szomszédos csúcspontok tömbjét. Ez egy olyan tömböt jelent, amiben |V| darab szomszédsági listát tartalmazó tömb van, ami csúcspontonként egy szomszédsági listát jelent. Itt látható a szociális hálózat gráfjának leképezése szomszédsági listával:
JavaScriptben ezt a szomszédsági listát így definiáljuk:
[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]
A szomszédsági listában a csúcs azonosítóknak nincs kötött sorrendje, de a példánkhoz hasonlóan célszerű növekvő sorrendet alkalmazni.
Konstans idő alatt érhető el bármelyik csúcsponthoz tartozó szomszédsági lista a tömb megfelelő indexelésével. Ahhoz, hogy megtudjuk, az (i,j) él létezik-e a gráfban, konstans idő alatt előszedjük az i szomszédsági listáját, és az i szomszédsági listájában keressük j-t. Legrosszabb esetben mennyi ideig tart ez? A válasz Θ(d), ahol d az i csúcspont fokszáma, mert ez mutatja meg, hogy milyen hosszú i szomszédsági listája. Az i csúcspont foka maximum |V|1 lehet (abban az esetben, ha az összes többi |V|1 csúcsponttal össze van kötve), minimum 0 (akkor, ha i izolált, nem illeszkedik hozzá egy él sem). Egy irányítatlan gráfban a j csúcspont akkor és csak akkor van benne i csúcspont szomszédsági listájában, ha i benne van j szomszédsági listájában is. Ha a gráf súlyozott, akkor a szomszédsági lista minden eleme vagy egy kételemű tömb, vagy egy objektum, ami megadja a csúcspont azonosítóját és a súly értékét.
Megvizsgálhatod for ciklussal a szomszédsági lista csúcspontjait. Például tegyük fel, hogy a gráfot a graph változóval szomszédsági lista formájában ábrázoltad, úgyhogy graph[i] egy olyan tömb, ami az i csúcspont szomszédait tartalmazza. Ekkor az alábbi JavaScript programot használhatod arra, hogy az i csúcspont szomszédaira lefuttasd a doStuff függvényt:
for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}
Ha zavar a dupla indexelés, így is írhatod:
var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}
Mennyi hely kell a szomszédsági listákhoz? Összesen |V| listánk lesz, és bár minden listában |V|1 csúcspont lehet, összesen egy irányítatlan gráf szomszédsági listáiban 2|E| elem van. Miért 2|E|? Minden (i,j) él pontosan kétszer szerepel a szomszédsági listában, egyszer i listájában, egyszer pedig j listájában. Élből pedig |E| darab van. Irányított gráf esetében a szomszédsági listákban összesen |E| elem van, egy minden irányított élhez.
Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.