Graafin tietorakenne ja Algorithms (Esimerkki)
Sarah Chen
Mikä on graafi tietorakenteessa?
Graafi on epälineaarinen tietorakenne, joka koostuu pisteistä ja reunoista, jossa kärjet sisältävät tiedot tai datan ja reunat toimivat linkkinä kärkiparien välillä.
Sitä käytetään oikeiden tekstiongelmien ratkaisemiseen, kuten parhaan reitin löytämiseen määränpäähän sekä televiestinnän ja sosiaalisten verkostojen reitin löytämiseen. Käyttäjiä pidetään Graphin solmuina, ja johdot 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 kaavion tietorakenteesta:
Se on yksinkertainen ohjaamaton graafi (yksi graafinen tyyppi). Tässä kärkijoukko on: {A, B, C,D,E,F}. Kaksi kärkeä luo reunan. Esimerkiksi A ja B on yhdistetty reunalla. A ja F eivät kuitenkaan ole sidoksissa mihinkään reunaan.
Kuvaajan terminologiat tietorakenteessa
Seuraavassa on joitain tärkeitä termejä, joita käytetään kaavion tietorakenteessa:
| Termi | Tuotetiedot |
|---|---|
| Kärki | Kaikkia tietoelementtejä kutsutaan kärjeksi tai solmuksi. Yllä olevassa kuvassa A, B, C, D & E ovat kärjet. |
| Reuna (kaari) | Kahden solmun tai kärjen välisiä yhdistäviä linkkejä kutsutaan reunaksi (Arc). Sillä on kaksi päätä ja se esitetään muodossa (alkuVertex, loppuVertex). |
| Ohjaamaton reuna | Se on kaksisuuntainen reuna. |
| Ohjannut Edge | Se on yksisuuntainen reuna. |
| Painotettu reuna | Reuna, jolla on arvoa. |
| Aste | Grafissa kärkipisteeseen yhdistettyjen reunojen 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 | Pisteiden sanotaan olevan vierekkäisiä, jos reuna on yhdistetty. |
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
Graafisen tietorakenteen sovellukset
Kaaviolla on monia käyttötapauksia. On olemassa monia algoritmeja, jotka käyttävät paljon grafiikkaa. Tässä on joitain Graphin sovelluksia:
- Google Maps löytää kaavioiden avulla kahden tien risteyksen ja laskee kahden sijainnin välisen etäisyyden.
Esimerkiksi Dijkstra, löytääksesi lyhimmän etäisyyden lähteen ja määränpään välillä. - Facebook käyttää Grapheja löytääkseen käyttäjien yhteisen ystävän. Sen algoritmi pitää jokaista käyttäjää graafin solmuna.
- Resurssien allokoinnissa käytetään DAG:ta (Direct Acyclic Graph). Se tarkistaa resurssien riippuvuuden.
- Google-hakukone käyttää kaavioita verkkosivustojen sijoituksen luomiseen.
- Kartoituslaite käyttää graafin tietorakennetta.
- reititin ja t:n protokolla käyttää Grafia oppiakseen määränpääpolun polun.