Gráfok
A gráf egy olyan adatszerkezet, amely csúcsokból/pontokból, és azokat összekötő élekből áll.
Ez pl. egy gráf:
A gráfokat tipikusan olyan helyzetekben alkalmazzuk, amikor különféle dolgok kapcsolatáról beszélünk.
Ez lehet egy metróhálózat:
Vagy diákok, akiknek legjobb barátaik vannak:
Néhány hasznos kifejezés, szakszó
A gráf összefüggő, ha bármely pontjából bármely pontjába el lehet jutni.
Ez pl. egy nem összefüggő gráf:
A gráf irányított, ha ez éleknek van egy kiinduló és egy végpontja. A fenti legjobb barát gráf irányított, míg a metróhálózat irányítatlan.
Egy gráf pedig súlyozott, ha az élekhez egy-egy számértéket rendelünk. A metróhálózat gráf súlyozott, míg a legjobb barát súly nélküli.
Egy gráf egyszerű, ha nincsenek benne olyan élek, amiknek:
- Ugyanazt a két pontot kötik össze (többszörös él)
- A kezdő- és a végpontja megegyezik (hurokél)
A korábbi példák mind egyszerű gráfok, az alábbi viszont nem:
Egy gráf pedig fa, ha összefüggő, és nincs benne kör - azaz ha egy pontból elindulunk, nem lehet visszajutni anélkül, hogy élen kétszer átmennénk. Érdemes összevetni az adatszerkezeteknél tanult definícióval - a kettő végeredményben ugyanazt jelenti, de a megközelítés, a felhasználás módja különbözik. E legelső példa az nem fa, mert tartalmazza az “1-2-3” pontokból álló kört.
Sok más hasznos tulajdonságot is elmondhatunk a gráfokról, itt csak a legfontosabbakat szedtem össze. Egy teljesebb körű fogalomtár megtalálható itt.
Tárolási mód
A gráfokat természetesen el kell tárolni valahogy, hogy a számítógép dolgozni tudjon vele. Erre a két gyakran alkalmazott megoldási mód van: a csúcsmátrix és az éllista. Vegyük pl. az első példabeli gráfot:
Csúcsmátrix
Ez egy táblázat, ahol a sorok/oszlopok egy-egy csúcst jelképeznek. A táblázatban 1 szerepel, ha az adott élt összeköti egy él, és 0 (vagy üresen is hagyhatjuk), ha nem.
1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | |
2 | 1 | 1 | |||
3 | 1 | 1 | |||
4 | 1 | ||||
5 | 1 |
Leolvasható, hogy az 1-3 pontokat összeköti egy él, mert a csúcsmátrixban az 1. sor 3. oszlopban szerepel egy 1-es. A 2-4 pontokat viszon nem köti össze, mert a 2. sor 4. oszlopában nincs 1-es.
Éllista
Szimplán felsoroljuk az éleket:
- 1-2
- 1-3
- 1-4
- 1-5
- 2-3