Graafityypit tietorakenteessa esimerkkien kanssa

Graafi on epälineaarinen tietorakenne, joka koostuu solmuista ja kaarista. Solmut sisältävät tiedon tai datan, ja kaaret toimivat linkkinä solmuparin välillä.

Graafeja voi olla useita erityyppisiä solmujen ja kaarien sijainnista riippuen. Tässä on joitakin tärkeitä graafien tyyppejä:

Ohjattu graafi

Suunnatun graafin reunoilla on nuolia, jotka osoittavat suunnan. Nuoli määrittää, mihin reuna osoittaa tai mihin se päättyy. Tässä on esimerkki suunnatusta graafista.

Ohjattu graafi

• Voimme siirtyä solmusta A paikkaan D.
• Emme kuitenkaan voi siirtyä solmusta D solmuun A, koska reuna osoittaa pisteestä A pisteeseen D.
• Koska kaaviossa ei ole painoja, matkustaminen kärjestä A paikkaan D maksaa saman verran kuin matkustaminen pisteestä D paikkaan F.

Ohjaamaton kaavio

Suuntaamaton graafi sisältää viivoja ilman osoittimia. Tämä tarkoittaa, että voimme liikkua päinvastoin kahden kärjen välillä. Tässä on yksinkertainen esimerkki suuntaamattomasta graafista.

Ohjaamaton kaavio

Yllä olevassa kaaviossa

• Voimme siirtyä pisteestä A pisteeseen B.
• Voimme myös siirtyä pisteestä B pisteeseen A.
• Reunat eivät sisällä ohjeita.

Se on esimerkki suuntaamattomasta graafista, jolla on äärellinen määrä solmuja ja kaaria ilman painoja.

Painotettu kaavio

Graafia, jonka kaarilla on painoja tai kustannuksia, kutsutaan painotetuksi graafiksi. Numeerinen arvo edustaa yleensä siirtymiskustannuksia yhdestä solmusta toiseen solmuun. Sekä suunnatuilla että suuntaamattomilla graafeilla voi olla painoja kaarilla. Tässä on esimerkki painotetusta graafista (suuntattu).

Suunnattu graafi painolla

• A:sta B:hen on etu ja painoarvo on 5, mikä tarkoittaa, että siirtyminen pisteestä A pisteeseen B maksaa meille 5.
• A osoittaa B:hen, mutta tässä kaaviossa B:llä ei ole suoraa reunaa A:han nähden. Joten emme voi matkustaa B:stä A:han.
• Jos kuitenkin haluamme siirtyä pisteestä A pisteeseen F, on olemassa useita polkuja. Polut ovat ADF ja ABF. ADF maksaa (10 + 11) eli 21.
• Tässä polku ABF maksaa (5 + 15) eli 20. Tässä lisätään polun jokaisen kaaren paino.

Tässä on esimerkki suuntaamattomasta graafista painojen kanssa:

Ohjaamaton kaavio painolla

Tässä reunalla on painoa, mutta ei suuntaa. Joten se tarkoittaa, että matka pisteestä A paikkaan D maksaa 10 ja päinvastoin.

Kaksisuuntainen kaavio

Kaksisuuntaisilla ja suuntaamattomilla graafeilla on yhteinen ominaisuus. Se on:

• Yleisesti ottaen suuntaamattomalla graafilla voi olla yksi kaari kahden kärjen välillä.

Esimerkiksi:

• Täällä siirtyminen paikasta A paikkaan D tai D paikkaan A maksaa 10.
• Kaksisuuntaisessa kuvaajassa voi olla kaksi reunaa kahden kärjen välillä.

Tässä on esimerkki:

Kaksisuuntainen kaavio

Matkustaminen pisteestä A pisteeseen D maksaa 17, mutta pisteestä D pisteeseen A 12. Emme siis voi antaa kahta eri painoa, jos kyseessä on suuntaamaton graafi.

Ääretön kaavio

Graafi sisältää äärettömän määrän kaaria ja solmuja. Jos graafi on ääretön ja se on myös yhtenäinen graafi, se sisältää myös äärettömän määrän kaaria. Tässä laajennetut kaaret tarkoittavat, että näihin solmuihin voi olla kaarien kautta yhteydessä useampia kaaria. Tässä on esimerkki äärettömästä graafista:

Ääretön kaavio

Nollakuvaaja

Nullgraafi sisältää vain solmuja tai kärkipisteitä, mutta ei kaaria. Jos annetaan graafi G = (V, E), jossa V on kärkipisteet ja E on kaaret, se on null, jos kaarien lukumäärä E on nolla. Tässä on esimerkki nullgraafista:

Nollakuvaaja

Triviaali kaavio

Graafitietorakennetta pidetään triviaalina, jos siinä on vain yksi solmu tai piste ilman kaaria. Tässä on esimerkki triviaalisesta graafista:

Monikuvaaja

Graafia kutsutaan multigraafiksi, kun kahden kärkipisteen välillä on useita kaaria tai kärkipisteessä on silmukka. Termi "silmukka" graafitietorakenteessa tarkoittaa kaaria, joka osoittaa samaan solmuun tai kärkipisteeseen. Multigraafi voi olla suunnattu tai suuntaamaton. Tässä on esimerkki monigraafista:

Pisteen B ja A välillä on kaksi kaaria. Lisäksi solmulla E on itsesilmukka. Yllä oleva graafi on suunnattu graafi, jonka kaarilla ei ole painoja.

Täydellinen kaavio

Graafi on täydellinen, jos jokaisella kärjellä on suunnattuja tai suuntaamattomia kaaria kaikkien muiden kärkien kanssa. Oletetaan, että kärkien lukumäärä on yhteensä V ja jokaisella kärjellä on täsmälleen V - 1 kaaria. Tällöin tätä graafia kutsutaan täydelliseksi graafiksi. Tällaisessa graafissa jokainen kärki on yhdistetty kaikkiin muihin kärkiin kaarien kautta. Tässä on esimerkki täydellisestä graafista, jossa on viisi kärkeä:

Kuvassa näkyy, että solmujen kokonaismäärä on viisi ja kaikilla solmuilla on täsmälleen neljä reunaa.

Yhdistetty kaavio

Graafia kutsutaan yhtenäiseksi graafiksi, jos se alkaa yhdestä solmusta tai kärkipisteestä ja voi jatkaa kaikkiin solmuihin lähtösolmusta. Tätä varten jokaisen solmu- tai kärkipisteparin välillä tulisi olla vähintään yksi kaari. Tässä on esimerkki yhtenäisestä graafista:

Tässä on selitys yllä olevasta yhdistetystä graafista:

• Olettaen, ettei C:n ja F:n välillä ole reunaa, emme voi matkustaa pisteestä A pisteeseen G. Reuna C:stä F:ään kuitenkin mahdollistaa matkustamisen tietystä solmusta mihin tahansa solmuun.
• Täydellinen Graafi on Yhdistetty Graafi, koska voimme siirtyä solmusta mihin tahansa toiseen solmuun annetussa kaaviossa.

Syklinen kaavio

Graafia sanotaan sykliseksi, jos siinä on yksi tai useampi sykli. Tässä on esimerkki syklisestä graafista:

Tässä solmut A, B ja C muodostavat syklin. Graafi voi sisältää useita syklejä sen sisällä.

Suunnattu asyklinen kaavio (DAG)

Graafia kutsutaan suunnatuksi asykliseksi graafiksi eli DAG:ksi, jos graafin sisällä ei ole syklejä. DAG on tärkeä tehtävä suoritettaessa... Topologinen lajittelu tai suoritusjärjestyksen löytämiseksi. DAG on tärkeä myös aikataulutusjärjestelmien luomisessa tai resurssien riippuvuuksien skannaamisessa jne. Yllä oleva graafi ei kuitenkaan sisällä sykliä. Tässä on yksinkertainen esimerkki suunnatusta asyklisestä graafista (DAG):

Kiertokaavio

Syklikaavio ei ole sama asia kuin syklinen kaavio. Syklikaaviossa jokaisella solmulla on täsmälleen kaksi yhdistettyä kaarraa, mikä tarkoittaa, että jokaisella solmulla on täsmälleen kaksi astetta. Tässä on esimerkki syklikaaviosta:

Kahdenvälinen kaavio

Tällaiset Kuvaajat ovat erikoisia graafeja, joissa solmut on sijoitettu kahteen joukkoon. Kaksijakoisen graafin on noudatettava sääntöä:

• Kahden kärkijoukon tulee olla erilliset, mikä tarkoittaa, että kaikki kärkipisteet on jaettava kahteen ryhmään tai joukkoon.
• Saman joukon kärkipisteiden ei tulisi muodostaa kaaria.

Euler-kaavio

Graafitietorakennetta pidetään Eulerin graafina, jos kaikilla sen solmuilla on parillinen aste. Termi solmujen aste tarkoittaa tiettyyn solmuun osoittavien tai siitä ulospäin osoittavien kaarien lukumäärää. Tässä on esimerkki Eulerin graafista:

Kaikilla kärkipisteillä on parilliset asteet. Pisteillä A, D, E ja H on kaksi astetta. Tässä solmulla C on neljä astetta, mikä on parillinen luku.

Hamiltonin kaavio

Hamilton-graafi on yhtenäinen graafi, jossa voit käydä kaikissa tietyn pisteen solmuissa palaamatta samaan solmuun tai käyttämättä samaa kaarea. Tämän tyyppistä yhtenäistä graafia kutsutaan "Hamilton-graafiksi". Polkua, jota pitkin tarkistat, onko annettu graafi Hamilton-graafi vai ei, kutsutaan Hamiltonin poluksi. Tässä on yksinkertainen esimerkki Hamiltonin graafista:

Tässä kuvassa voimme vierailla kaikissa yllä olevan kaavion solmupisteissä. Yksi poluista voi olla ADCHBEOn myös mahdollista löytää Hamiltonin sykli. Hamiltonin sykli alkaa ja päättyy samaan kärkeen. Joten Hamiltonin sykli on ADCHBEA.

UKK