Gráfalgoritmusok

Gráfalgoritmusok a gráfokkal kapcsolatos problémák megoldására szolgáló algoritmusok összessége. A gráf olyan elemek halmaza, amelyek csúcsokból és élekből állnak; lehet irányított vagy irányítatlan, és lehet súlyozott vagy súlyozatlan. A súly gyakran költséget, hosszúságot vagy kapacitást jelöl. A gráf-típusok különféle problémákat és megoldási megközelítéseket írhatnak elő.

Az alapvető feladatok közé tartozik a bejárás és az útvonal-keresés. A bejárási módszerek közül a szélességi bejárás (BFS) és a mélységi bejárás (DFS) segítenek a gráf szerkezetének feltárásában, kapcsolati összefüggések feltárásában és algráfok képzésében. Számos feladat számítási redukció segítségével megoldható a bejárt részgráfokra.

Rövides útvonal-keresés esetén használják a Dijkstra-algoritmust pozitív súlyú élek esetén, a Bellman–Ford-ot negatív súlyokra, és a Floyd–Warshall-t minden páros út hosszának kiszámítására. A legkisebb költségű feszítőfa problémára megoldást adó algoritmusok közé tartozik Kruskal és Prim; mindkettő egy minimális költségű feszítőfát talál a gráfnod összefüggő részére.

Hálózati áramlás problémáknál a Ford–Fulkerson és az Edmonds–Karp azonosítják a maximális áramlást és a minimális vágást. Bipartit gráfokra vonatkozó problémákban a Hopcroft–Karp algoritmus hatékony a maximális párosított komponensek megtalálására. A keresés és optimalizáció területén gyakran alkalmaznak A* jellegű heurisztikákat is útvonal-keresési feladatokban.

Az algoritmusok teljesítményét nagyban befolyásolja az adatszerkezet használata: adjacencia lista vagy mátrix, valamint a prioritási adatszerkezetek optimális implementációja. Gyakorlati alkalmazások közé tartozik az útvonaltervezés, hálózati forgalom-optimalizálás, logisztika, társadalmi hálózatok elemzése és ütemezési feladatok. Számos gráfprobléma NP-hard, például Hamilton-kör vagy általános gráf színezése.