Graafin tietorakenne ja Algorithms (Esimerkki)

Mikä on graafi tietorakenteessa?

Graafi on epälineaarinen tietorakenne, joka koostuu solmuista ja kaarista, joissa solmut sisältävät informaation tai datan ja kaaret toimivat linkkinä solmujen parin välillä.

Sitä käytetään ratkaisemaan reaalimaailman ongelmia, kuten parhaan reitin löytämistä määränpäähän sekä reittiä televiestinnälle ja sosiaalisille verkostoille. Käyttäjiä pidetään graafissa solmuina, ja langat ovat käyttäjiä yhdistäviä reunoja.

Jos reunat esitetään muodossa E ja kärjet V, niin graafi G voidaan kirjoittaa kärkien ja reunojen joukoksi, kuten esim. G (V, E).

Esimerkki graafista tietorakenteessa

Tässä on yksinkertainen esimerkki graafin tietorakenteesta:

Se on yksinkertainen suuntaamaton graafi (eräänlainen graafi). Tässä solmujen joukko on: {A, B, C, D, E, F}. Kaksi solmua muodostaa kaaren. Esimerkiksi A ja B on yhdistetty kaarella. A ja F eivät kuitenkaan ole yhdistetty millään kaarilla.

Kuvaajan terminologiat tietorakenteessa

Seuraavassa on joitakin tärkeitä termejä, joita käytetään graafin tietorakenteessa:

Termi	Tuotetiedot
Kärki	Jokaista dataelementtiä kutsutaan solmuksi tai kärkipisteeksi. Yllä olevassa kuvassa A, B, C, D ja E ovat solmut.
Reuna (kaari)	Kahden solmun tai kärkipisteen välisiä yhdistäviä linkkejä kutsutaan kaareksi (Arc). Sillä on kaksi päätä ja se esitetään muodossa (alkuPiste, loppuPiste).
Ohjaamaton reuna	Se on kaksisuuntainen reuna.
Ohjannut Edge	Se on yksisuuntainen reuna.
Painotettu reuna	Reuna, jolla on arvo.
Aste	Graafissa yhteen kärkeen yhdistettyjen kaarien lukumäärää kutsutaan asteeksi.
Indegree	Huippupisteeseen yhdistettyjen saapuvien reunojen kokonaismäärä.
Ylimielinen	Huippupisteeseen yhdistettyjen lähtevien reunojen kokonaismäärä.
Itsesilmukka	Reunaa kutsutaan itsesilmukaksi, jos sen kaksi päätepistettä ovat samat.
Viereisyys	Kärkien sanotaan olevan vierekkäisiä, jos niiden välillä on yhdistetty kaari.

Kuvaajien tyypit tietorakenteessa

Tässä on luettelo yleisimmistä kaaviotyypit tietorakenteessa:

• Ohjattu graafi
• Ohjaamaton kaavio
• Painotettu kaavio
• Kaksisuuntainen kaavio
• Ääretön kaavio
• Nollakuvaaja
• Triviaali kaavio
• Monikuvaaja
• Täydellinen kaavio
• Yhdistetty kaavio
• Syklinen kaavio
• Suunnattu asyklinen kaavio (DAG)
• Kiertokaavio
• Kahdenvälinen kaavio
• Euler-kaavio
• Hamiltonin kaavio

Kuinka esittää graafi tietorakenteessa?

Graafi tallennetaan yleensä muistiin käyttämällä yhtä kahdesta esitystavasta. Valinta vaikuttaa siihen, kuinka paljon muistia graafi käyttää ja kuinka nopeasti yleiset toiminnot suoritetaan.

• Vierekkäisyysmatriisi: Kaksiulotteinen V × V -taulukko, jossa solu [i][j] on 1 (tai kaaren paino), jos pisteiden i ja j välillä on kaari, ja 0 muuten. Se sallii O(1)-kaarenhaun, mutta käyttää O(V²)-avaruutta, mikä tekee siitä parhaan tiheille graafeille.
• Vierekkäisyysluettelo: Listojen taulukko, jossa jokainen solmu tallentaa listan naapurisolmuistaan. Se käyttää O(V + E)-avaruutta ja on tehokas harvoille graafeille, minkä vuoksi useimmat reaalimaailman graafit käyttävät sitä.

Voit lukea lisää näistä osiosta vierekkäisyyslista ja graafin matriisiesitys opetusohjelma.

Graafisen tietorakenteen sovellukset

Graafilla on monia käyttötapauksia. On olemassa paljon algoritmeja, jotka käyttävät graafeja. Tässä on joitakin graafin sovelluksia:

• Google Kartat käyttävät kuvaajia kahden tien risteyksen löytämiseen ja kahden sijainnin välisen etäisyyden laskemiseen. Esimerkiksi Dijkstra, lyhimmän etäisyyden löytämiseksi lähtö- ja määränpään välillä.
• Facebook käyttää graafeja löytääkseen käyttäjien yhteiset ystävät. Sen algoritmi pitää jokaista käyttäjää graafin solmuna.
• Resurssien allokointiin käytetään DAG:ia (Directed Acyclic Graph). Se tarkistaa resurssien riippuvuuden.
• Google Hakukoneet käyttävät graafisia kaavioita verkkosivustojen sijoituksen luomiseen.
• Karttaping laite käyttää graafitietorakennetta.
• A reititin ja sen protokolla käyttää Graafia oppiakseen polun määränpäähän.

UKK