Graafityypit tietorakenteessa esimerkkien kanssa

Graafi on epälineaarinen tietorakenne, joka koostuu pisteistä ja reunoista. Huippupisteet sisältävät tietoa tai dataa, ja reunat toimivat linkkinä kärkiparien välillä.

Graafit voivat olla monen tyyppisiä solmujen ja reunojen sijainnista riippuen. Tässä on joitain tärkeitä kaaviotyyppejä:

Ohjattu graafi

Suunnatun kuvaajan reunat sisältävät suuntaa osoittavia nuolia. Nuoli määrittää, mihin reuna osoittaa tai mihin se päättyy.

Tässä on esimerkki ohjatusta kaaviosta.

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

Ohjaamaton kaavio

Suuntaamaton kuvaaja sisältää reunat ilman osoittimia. Se tarkoittaa, että voimme matkustaa päinvastoin kahden kärjen välillä.

Tässä on yksinkertainen esimerkki ohjaamattomasta kuvaajasta.

Yllä olevassa kaaviossa

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

Se on esimerkki suuntaamattomasta graafista, jossa on äärellinen määrä pisteitä ja reunoja ilman painoja.

Painotettu kaavio

Graafia, joka sisältää painot tai kustannukset reunoilla, kutsutaan painotetuksi kuvaajaksi. Numeerinen arvo edustaa yleensä siirtokustannuksia kärjestä toiseen. Sekä suunnatun että ohjaamattoman graafin reunoilla voi olla painotuksia.

Tässä on esimerkki painotetusta kaaviosta (ohjattu).

• A paikkaan B, siellä on reuna ja paino on 5, mikä tarkoittaa, että siirtyminen paikasta A paikkaan B maksaa meille 5.
• Piste B:hen, mutta tässä kaaviossa B:llä ei ole suoraa reunaa A:hen nähden. Emme siis voi matkustaa paikasta B paikkaan A.
• Kuitenkin, jos haluamme siirtyä paikasta A paikkaan F, polkuja on useita. Polut ovat ADF, ABF. ADF maksaa (10+11) tai 21.
• Tässä polku ABF maksaa (5+15) tai 20. Tähän lisätään polun jokaisen reunan paino.

Tässä on esimerkki ohjaamattomasta kaaviosta painojen kanssa:

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 kaavioilla on yhteinen ominaisuus. Tuo on

• Yleensä suuntaamattomalla kuvaajalla voi olla yksi reuna 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ä esimerkki:

Matka paikasta A paikkaan D maksaa meille 17, mutta matka paikasta D paikkaan A maksaa 12. Joten emme voi antaa kahta eri painoa, jos se on suuntaamaton graafi.

Ääretön kaavio

Graafi sisältää äärettömän määrän reunoja ja solmuja. Jos graafi on ääretön ja se on myös yhdistetty graafi, se sisältää myös äärettömän määrän reunoja. Tässä laajennetut reunat tarkoittavat, että näihin solmuihin voidaan liittää useampia reunoja reunojen kautta.

Tässä on esimerkki äärettömästä graafista:

Nollakuvaaja

Null Graph sisältää vain solmut tai kärjet, mutta ei reunoja. Jos annetaan Graafi G = (V, E), jossa V on pisteet ja E on reunat, se on nolla, jos reunojen määrä E on nolla.

Tässä on esimerkki nollakaaviosta:

Triviaali kaavio

Graafin tietorakennetta pidetään triviaalina, jos vain yksi kärki tai solmu on läsnä ilman reunoja.

Tässä on esimerkki triviaalikaaviosta:

Monikuvaaja

Graafia kutsutaan multigrafiksi, kun kahden kärjen välillä on useita reunoja tai kärjessä on silmukka. Termi "silmukka" kuvaajatietorakenteessa tarkoittaa reunaa, joka osoittaa samaan solmuun tai kärkeen. Multigrafi voi olla suunnattu tai suuntaamaton.

Tässä on esimerkki monikaaviosta:

B:stä A:han on kaksi reunaa. Lisäksi kärjessä E on omasilmukka. Yllä oleva Graafi on suunnattu graafi, jossa ei ole painoja reunoilla.

Täydellinen kaavio

Graafi on valmis, jos jokaisella kärjellä on suunnatut tai suuntaamattomat reunat kaikkien muiden kärkien kanssa.

Oletetaan, että pisteitä on yhteensä V ja jokaisella kärjellä on täsmälleen V-1 reunat. Sitten tätä kuvaajaa kutsutaan täydelliseksi kuvaajaksi. Tämän tyyppisessä kuvaajassa jokainen kärkipiste on yhdistetty kaikkiin muihin kärkikohtiin reunojen kautta.

Tässä on esimerkki täydellisestä kaaviosta, jossa on viisi kärkeä:

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

Yhdistetty kaavio

Graafia kutsutaan yhdistetyksi graafiksi, jos aloitamme solmusta tai kärjestä ja kuljetamme kaikki solmut aloitussolmusta. Tätä varten jokaisen solmu- tai kärkiparin välillä tulee olla vähintään yksi reuna.

Tässä on esimerkki yhdistetystä kaaviosta:

Tässä on selitys yllä olevasta "täydellinen kaavioesimerkki" -kaaviosta:

• Olettaen, että C:n ja F:n välillä ei ole reunaa, emme voi matkustaa paikasta A paikkaan G. Reunan C ja F avulla voimme kuitenkin matkustaa mihin tahansa solmuun tietystä solmusta.
• Täydellinen Graafi on Yhdistetty Graafi, koska voimme siirtyä solmusta mihin tahansa toiseen solmuun annetussa kaaviossa.

Syklinen kaavio

Kuvaajan sanotaan olevan syklinen, jos kaaviossa on yksi tai useampi jakso.

Tässä on esimerkki syklisestä kaaviosta:

Tässä kärkipisteet A, B ja C muodostavat syklin.

Graafissa voi olla useita syklejä.

Suunnattu asyklinen kaavio (DAG)

Graafia kutsutaan suunnatuksi asykliseksi kuvaajaksi tai DAG:ksi, jos kaaviossa ei ole jaksoja. DAG on tärkeä tehtäessä Topologinen lajittelu tai täytäntöönpanomääräyksen löytäminen. DAG on myös tärkeä luotaessa ajoitusjärjestelmiä tai skannattaessa resurssiriippuvuutta jne. Yllä oleva kaavio ei kuitenkaan sisällä mitään sykliä.

Tässä on yksinkertainen esimerkki suunnatusta asyklisestä kuvaajasta (DAG):

Kiertokaavio

Cycle Graph ei ole sama kuin syklinen kuvaaja. Cycle Graphissa jokaisessa solmussa on täsmälleen kaksi reunaa yhdistettynä, mikä tarkoittaa, että jokaisella solmulla on täsmälleen kaksi astetta.

Tässä on esimerkki syklikaaviosta:

Kahdenvälinen kaavio

Tällaiset Kuvaajat ovat erityisiä Graph-tyyppejä, joissa pisteet on määritetty kahdelle joukolle.

Kaksiosaisen kaavion on noudatettava sääntöä:

• Kahden kärkijoukon tulee olla erillisiä, mikä tarkoittaa, että kaikki pisteet on jaettava kahteen ryhmään tai joukkoon.
• Sama joukko Vertices ei saa muodostaa reunoja.

Euler-kaavio

Graafisten tietorakenteiden katsotaan olevan Euler-graafit, jos kaikilla pisteillä on parillinen aste. Termi kärkipisteiden aste tarkoittaa tiettyyn kärkeen osoittavien tai siitä osoittavien reunojen määrää.

Tässä on esimerkki Euler-kaaviosta:

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

Hamiltonin kaavio

Hamilton Graph on Connect Graph, jossa voit vierailla tietyn kärjen kaikissa pisteissä käymättä uudelleen samassa solmussa tai käyttämättä samaa reunaa. Tällainen yhdistetty kaavio tunnetaan nimellä "Hamilton Graph". Polku, jolla käyt varmistaaksesi, onko annettu kuvaaja Hamiltonin kuvaaja, tunnetaan nimellä Hamiltonin polku.

Tässä on yksinkertainen kaavioesimerkki Hamiltonista:

Tässä kuvassa voimme vierailla kaikissa yllä olevan kaavion solmupisteissä. Yksi poluista voi olla ADCHBE. On myös mahdollista löytää Hamilton Cycle. Hamiltonin sykli alkaa ja päättyy samaan kärkeen. Joten, Hamiltonin sykli tulee olemaan ADCHBEA.