Graafiku andmestruktuur ja Algorithms (Näide)
Sarah Chen
⚡ Nutikas kokkuvõte
Graafi andmestruktuur on mittelineaarne tippude ja servade kogum, kus iga serv ühendab tippude paari. Graafikud modelleerivad reaalse maailma võrgustikke, nagu kaardid, sotsiaalsed ühendused ja veebilehed, ning toetavad paljusid võimsaid algoritme.
Mis on andmestruktuuri graafik?
Graafik on mittelineaarne andmestruktuur, mis koosneb tippudest ja servadest, kus tipud sisaldavad teavet või andmeid ja servad toimivad lüliks tippude paari vahel.
Seda kasutatakse reaalsete probleemide lahendamiseks, näiteks parima marsruudi leidmiseks sihtkohta ning telekommunikatsiooni ja sotsiaalvõrgustike marsruudi leidmiseks. Kasutajaid käsitletakse graafikus sõlmena ja juhtmed on kasutajaid ühendavad servad.
Kui servad on E ja tipud V, siis saab graafi G kirjutada tippude ja servade hulgana, näiteks G (V, E).
Graafiku näide andmestruktuuris
Siin on lihtne näide graafi andmestruktuurist:
See on lihtne suunamata graaf (üks graafi liik). Siin on tippude hulk: {A, B, C, D, E, F}. Kaks tippu moodustavad serva. Näiteks A ja B on ühendatud servaga. A ja F ei ole aga ühegi servaga ühendatud.
Graafiterminoloogiad andmestruktuuris
Järgnevalt on toodud mõned graafi andmestruktuuris kasutatavad olulised terminid:
| Termin | Kirjeldus |
|---|---|
| Kõrgeim tipp | Iga andmeelementi nimetatakse tipuks või sõlmeks. Ülaltoodud pildil on tipud A, B, C, D ja E. |
| Serv (kaar) | Kahe sõlme või tipu vahelisi ühenduslülisid nimetatakse servaks (Arc). Sellel on kaks otsa ja seda esitatakse kui (algusTipp, lõppTipp). |
| Suunamata serv | See on kahesuunaline serv. |
| Režissöör Edge | See on ühesuunaline serv. |
| Kaalutud serv | Väärtusega serv. |
| Kraad | Graafis nimetatakse tipuga ühendatud servade arvu astmeks. |
| Indegree | Tipuga ühendatud sissetulevate servade koguarv. |
| Väljaspool kraadi | Tipuga ühendatud väljuvate servade koguarv. |
| Self-loop | Serva nimetatakse iseahelaks, kui selle kaks otspunkti langevad kokku. |
| Lähedus | Tippusid nimetatakse külgnevateks, kui nende vahel on ühendatud serv. |
Graafikute tüübid andmestruktuuris
Siin on nimekiri kõige tavalisematest graafikute tüübid andmestruktuuris:
- Suunatud graafik
- Suunamata graafik
- Kaalutud graafik
- Kahesuunaline graafik
- Lõputu graafik
- Nullgraafik
- Triviaalne graafik
- Mitu graafikut
- Täielik graafik
- Ühendatud graafik
- Tsükliline graafik
- Suunatud atsükliline graafik (DAG)
- Tsükligraafik
- Kahepoolne graafik
- Euleri graafik
- Hamiltoni graafik
Kuidas graafikut andmestruktuuris kujutada?
Graafi salvestatakse mällu tavaliselt ühel kahest esitusviisist. Valik mõjutab seda, kui palju mälu graaf kasutab ja kui kiiresti tavalised toimingud toimivad.
- Kõrvaloleku maatriks: Kahemõõtmeline V × V massiiv, kus lahtri [i][j] väärtus on 1 (või serva kaal), kui tippude i ja j vahel on serv, ja muul juhul 0. See võimaldab O(1) servaotsingut, kuid kasutab O(V²) ruumi, mistõttu sobib see kõige paremini tihedate graafikute jaoks.
- Naabruskondade loend: Loendite massiiv, kus iga tipp salvestab oma naabertippude loendi. See kasutab O(V + E) ruumi ja on efektiivne hõredate graafide puhul, mistõttu enamik reaalse maailma graafe seda kasutab.
Nende kohta saate lähemalt lugeda Graafi külgnevusloend ja maatriksi esitus juhendaja.
Graafilise andmestruktuuri rakendused
Graafil on palju kasutusjuhtumeid. On palju algoritme, mis graafe kasutavad. Siin on mõned graafi rakendused:
- Google Kaardid kasutavad graafikuid kahe tee ristumiskoha leidmiseks ja kahe asukoha vahelise kauguse arvutamiseks. Näiteks dijkstra, lähte- ja sihtkoha vahelise lühima vahemaa leidmiseks.
- Facebook kasutab kasutajate ühiste sõprade leidmiseks graafe. Selle algoritm käsitleb iga kasutajat graafi sõlmena.
- Ressursside jaotamiseks kasutatakse DAG-i (Directed Acyclic Graph). See kontrollib ressursside sõltuvust.
- . Google Otsingumootorid kasutavad veebisaitide edetabeli loomiseks graafikuid.
- Kaartping Seade kasutab graafi andmestruktuuri.
- A ruuter ja selle protokoll kasutab sihtkohta jõudmise tee õppimiseks graafikut.
