10. fejezet - Gráfalgoritmusok

10.1. Gráfok ábrázolása

A gráfok ábrázolására két módszer terjedt el, s rendszerint a csúcsok és élek aránya dönti el, hogy adott feladatnál melyiket alkalmazzuk. A szomszédsági éllistás ábrázolásnál egy, a csúcsok számával megegyező elemszámú mutatótömböt használunk, és minden egyes v csúcshoz egy lista tartozik, azon u csúcsok listája, melyre (v, u) a gráf egy éle. Az 10.1.1. ábrán szereplő gráf éllistás ábrázolása a 10.1.2. ábrán látható. Ebben az ábrázolásban a szükséges tárterület a gráf csúcsai és élei számának összegével arányos. A fejezetben szereplő programokban a v csúcshoz tartozó éllistára Adj(v) néven hivatkozunk. A szomszédsági mátrixhoz (másnéven csúcsmátrix) egy m kétdimenziós tömböt használunk, a csúcsokat megszámozzuk az 1, . . . , n értékekkel és és mij = 1 akkor és csak akkor, ha (i, j) a gráf éle. Ebben az esetben a szükséges tárterület a csúcsok számával négyzetesen arányos. Az 10.1.1. ábrán szereplő gráf szomszédsági mátrixos ábrázolása az 1. táblázaton látható.

10.1. ábra - 10.1.1. ábra. Példagráf

10.1.1. ábra. Példagráf

10.2. ábra - 10.1.2. ábra. A példagráf éllistás ábrázolása

10.1.2. ábra. A példagráf éllistás ábrázolása

10.3. ábra - 1. táblázat. A példagráf szomszédsági mátrixos ábrázolása

1. táblázat. A példagráf szomszédsági mátrixos ábrázolása