Summary of Gráfok és szélességi és mélységi bejárás
Gráfok és Szélességi/Mélységi Bejárás: Teljes Útmutató
Bevezetés a Gráfok Világába
Üdvözöllek a gráfelmélet világában! Ez a terület a matematika és a számítástudomány egyik alappillére, amely lehetővé teszi számunkra, hogy komplex rendszerek közötti kapcsolatokat modellezzük és elemezzük. Legyen szó közlekedési hálózatokról, közösségi médiáról, vagy akár az agy felépítéséről, a gráfok mindenhol ott vannak, hogy segítsék a megértést és a problémamegoldást.
Mi is az a Gráf?
Egy gráf ($G$) két alapvető építőelemből áll: csúcsokból (pontokból) és élekből (összeköttetésekből). Képzeld el a csúcsokat, mint helyszíneket (pl. városok, emberek), az éleket pedig mint az ezek közötti kapcsolatokat (pl. utak, barátságok).
Csúcs (Vertex/Node): A gráf alapvető egysége. Gyakran pontként ábrázolják.
Él (Edge): Két csúcs közötti kapcsolat. Vonalakkal ábrázolják.
Gráfok Típusai
Nem minden gráf egyforma! Különbséget tehetünk aszerint, hogy az éleknek van-e irányuk, vagy hogy tartozik-e hozzájuk valamilyen érték (súly).
Irányítatlan és Irányított Gráfok
-
Irányítatlan gráf: Ebben az esetben az éleknek nincs irányuk. Ha A csúcsból B csúcsba vezet egy él, akkor B-ből A-ba is vezet ugyanaz az él. Gondolj egy közösségi hálózatra, ahol a barátságok általában kölcsönösek.
Példa: Egy A és B közötti barátság azt jelenti, hogy A barátja B-nek és B barátja A-nak.
-
Irányított gráf (Digraph): Itt az éleknek van irányuk. Ha A-ból B-be van egy él, az nem feltétlenül jelenti azt, hogy B-ből A-ba is van. Egyirányú utcák vagy Twitter követési kapcsolatok jó példák erre.
Példa: Ha Pisti követi Évit Twitteren, az nem jelenti automatikusan azt, hogy Évi is követi Pistit.
Súlyozatlan és Súlyozott Gráfok
-
Súlyozatlan gráf: Az élekhez nem tartozik extra érték. Minden él „egy egységnyi” távolságnak vagy költségnek számít.
Példa: Az, hogy két ember között van-e barátság, de nem számít, mennyire "erős" a barátság.
-
Súlyozott gráf: Az élekhez numerikus érték, egy úgynevezett súly tartozik. Ez a súly reprezentálhat távolságot, időt, költséget, kapacitást stb. Súlyozott gráfokat gyakran használunk a legrövidebb út vagy a minimális költségű útvonal megtalálására.
Példa: Egy úthálózatban a városok közötti utak hossza vagy az autópályadíj lehet a súly.
Kapcsolatok és Tulajdonságok
Néhány további fontos fogalom, amivel találkozni fogsz:
Szomszédos csúcsok: Két csúcs szomszédos, ha él köti össze őket.
Fokszám (Degree): Egy csúcs fokszáma az adott csúcshoz kapcsolódó élek száma.
Irányított gráfoknál ezt tovább bontjuk:
- Bemenő fokszám (In-degree): Az adott csúcsba befutó élek száma.
- Kimenő fokszám (Out-degree): Az adott csúcsból kifutó élek száma.
Gráfok Reprezentációja: Hogyan Tároljuk őket?
A gráfokat különböző módokon tárolhatjuk számítógépen, attól függően, hogy milyen műveleteket akarunk hatékonyan végrehajtani rajtuk. A két leggyakoribb reprezentáció a szomszédsági mátrix és a szomszédsági lista.
1. Szomszédsági mátrix (Adjacency Matrix)
Ez egy négyzetes mátrix, ahol a sorok és oszlopok a gráf csúcsait reprezentálják. Ha van él az $i$-edik csúcsból a $j$-edik csúcsba, akkor a mátrix $M[i][j]$ elemének értéke 1 (vagy az él súlya). Ha nincs él, akkor 0.
- Leírás: Egy $V \times V$ méretű mátrix, ahol $V$ a csúcsok száma. $M[i][j] = 1$ (vagy a súly), ha van él $i$-ből $j$-be, egyébként $0$.
- Előnyök:
- Gyorsan ellenőrizhető, hogy két csúcs között van-e él: $O(1)$ idő.
- Egyszerű implementálni.
- Hátrányok:
- Nagy térigény: $O(V^2)$ memória, ami ritka gráfok (kevés él) esetén pazarló lehet.
- Egy csúcs szomszédainak lekérdezése lassú: $O(V)$ idő.
Példa: Egy 3 csúcsú irányítatlan gráf ($1-2$, $2-3$) szomszédsági mátrixa:
$$\
Sign up for the full summaryAlready have an account? Sign in
Gráfok Alapjai
Klíčová slova: Gráf algoritmusok, Szélességi bejárás (BFS), Mélységi bejárás (DFS), Gráfbejárási Algoritmusok
Klíčové pojmy: A gráfok csúcsokból (vertices) és élekből (edges) állnak, amelyek kapcsolatokat reprezentálnak., Az irányítatlan gráfokban az éleknek nincs irányuk, míg az irányított gráfokban (digraphok) van irányuk., A súlyozatlan gráfokban az élekhez nem tartozik érték, míg a súlyozott gráfokban numerikus súlyok kapcsolódnak az élekhez., Két csúcs szomszédos, ha él köti össze őket., Egy csúcs fokszáma a hozzá kapcsolódó élek száma; irányított gráfoknál megkülönböztetünk bemenő és kimenő fokszámot., A szomszédsági mátrix egy $V \times V$ méretű tábla, amely $O(V^2)$ memóriát igényel, és gyors él ellenőrzést tesz lehetővé $O(1)$ időben., A szomszédsági lista egy tömb listákból, amely $O(V + E)$ memóriát igényel, és hatékonyan listázza a szomszédokat $O(\text{fokszám})$ időben., A szomszédsági mátrix sűrű gráfokhoz, a szomszédsági lista ritka gráfokhoz alkalmasabb., A gráfelmélet alapvető a komplex rendszerek modellezésében és elemzésében a számítástudományban és a matematikában.