Graafikute tüübid andmestruktuuris koos näidetega

Graaf on mittelineaarne andmestruktuur, mis koosneb tippudest ja servadest. Tipud sisaldavad teavet või andmeid ning servad toimivad lülina tippude paaride vahel.

Graafikuid võib olla mitut tüüpi, olenevalt sõlmede ja servade asukohast. Siin on mõned olulised graafikutüübid.

Suunatud graafik

Suunatud graafiku servad sisaldavad suunda tähistavaid nooli. Nool määrab, kuhu serv on suunatud või kus see lõpeb.

Siin on näide suunatud graafikust.

• Võime minna sõlmest A punkti D.
• Kuid me ei saa minna sõlmest D sõlme A, kuna serv osutab punktist A punkti D.
• Kuna graafikul pole kaalusid, maksab sõit tipust A punkti D sama palju kui sõitmine punktist D punkti F.

Suunamata graafik

Suunamata graafik sisaldab servi ilma osutiteta. See tähendab, et saame kahe tipu vahel liikuda ka vastupidi.

Siin on lihtne näide suunamata graafikust.

Ülaltoodud graafikul

• Võime liikuda punktist A punkti B
• Võime liikuda ka punktist B punkti A
• Servad ei sisalda juhiseid.

See on näide suunamata graafist, millel on piiratud arv tippe ja servi ilma kaaluta.

Kaalutud graafik

Graafiku, mille servadel on kaalud või kulud, nimetatakse kaalutud graafikuks. Arvväärtus tähistab üldiselt ühest tipust teise tippu liikumise kulu. Nii suunatud kui ka suunamata graafiku servadel võib olla kaalu.

Siin on näide kaalutud graafikust (suunatud).

• A punkti B, seal on serv ja kaal on 5, mis tähendab, et punktist A punkti B liikumine maksab meile 5.
• Punkt punktini B, kuid sellel graafikul pole B-l otsest serva A ees. Seega ei saa me liikuda punktist B punkti A.
• Kui aga tahame liikuda punktist A punkti F, on mitu teed. Teed on ADF, ABF. ADF maksab (10+11) või 21.
• Siin maksab tee ABF (5+15) või 20. Siin liidame tee iga serva raskuse.

Siin on näide kaaludega suunamata graafikust:

Siin on serval kaal, kuid puudub suund. Niisiis, see tähendab, et reisimine tipust A punkti D maksab 10 ja vastupidi.

Kahesuunaline graafik

Kahesuunalistel ja suunamata graafikutel on ühine omadus. See on

• Üldiselt võib suunamata graafikul olla üks serv kahe tipu vahel.

Näiteks:

• Siin maksab A-st D-sse või D-sse A kolimine 10.
• Kahesuunalises graafikus võib kahe tipu vahel olla kaks serva.

Siin on näide:

Sõit punktist A punkti D maksab meile 17, aga punktist D sõitmine 12. Seega ei saa me määrata kahte erinevat kaalu, kui tegemist on suunamata graafikuga.

Lõputu graafik

Graafik sisaldab lõpmatu arvu servi ja sõlmi. Kui graaf on lõpmatu ja see on ka ühendatud graaf, siis sisaldab see ka lõpmatu arvu servi. Siin tähendavad laiendatud servad, et nende sõlmedega võib servade kaudu olla ühendatud rohkem servi.

Siin on näide lõpmatust graafikust:

Nullgraafik

Nullgraafik sisaldab ainult sõlmi või tippe, kuid ilma servadeta. Kui antud graafik G = (V, E), kus V on tipud ja E on servad, on see null, kui servade arv E on null.

Siin on nullgraafiku näide:

Triviaalne graafik

Graafiku andmestruktuuri peetakse triviaalseks, kui esineb ainult üks tipp või sõlm ilma servadeta.

Siin on näide triviaalsest graafikust:

Mitu graafikut

Graafi nimetatakse multigraafiks, kui kahe tipu vahel on mitu serva või kui tipus on silmus. Graafilise andmestruktuuri termin "silmus" tähendab serva, mis osutab samale sõlmele või tipule. Multigraaf võib olla suunatud või suunamata.

Siin on näide mitmest graafikust:

B-st A-ni on kaks serva. Lisaks on tipul E isesilmus. Ülaltoodud graafik on suunatud graafik, mille servadel pole kaalu.

Täielik graafik

Graaf on täielik, kui igal tipul on suunatud või suunamata servad kõigi teiste tippudega.

Oletame, et tippe on kokku V ja igal tipul on täpselt V-1 servad. Seejärel nimetatakse seda graafikut täielikuks graafikuks. Seda tüüpi graafiku puhul on iga tipp ühendatud kõigi teiste tippudega servade kaudu.

Siin on näide viie tipuga täielikust graafikust:

Pildil on näha sõlmede koguarv viis ja kõigil sõlmedel on täpselt neli serva.

Ühendatud graafik

Graafi nimetatakse ühendatud graafikuks, kui alustame sõlmest või tipust ja liigume kõik sõlmed algussõlmest. Selleks peaks iga sõlme- või tipupaari vahel olema vähemalt üks serv.

Siin on näide ühendatud graafikust:

Siin on ülaltoodud "täieliku graafiku näite" graafiku selgitus:

• Eeldades, et C ja F vahel pole serva, ei saa me liikuda punktist A punkti G. Kuid serv C kuni F võimaldab meil liikuda antud sõlmest mis tahes sõlme.
• Täielik graafik on ühendatud graafik, kuna saame liikuda antud graafiku sõlmest mis tahes teise sõlme.

Tsükliline graafik

Graafikut peetakse tsükliliseks, kui graafikul on üks või mitu tsüklit.

Siin on näide tsüklilisest graafikust:

Siin moodustavad tipud A, B ja C tsükli.

Graafikul võib olla mitu tsüklit.

Suunatud atsükliline graafik (DAG)

Graafikut nimetatakse suunatud atsükliliseks graafikuks või DAG-ks, kui graafikus pole tsükleid. DAG on selle tegemisel oluline Topoloogiline sortimine või täitmiskorralduse leidmine. DAG on oluline ka ajastamissüsteemide loomiseks või ressursside sõltuvuse kontrollimiseks jne. Ülaltoodud graafik ei sisalda aga ühtegi tsüklit.

Siin on lihtne näide suunatud atsüklilisest graafikust (DAG):

Tsükligraafik

Tsükligraafik ei ole sama mis tsükliline graafik. Tsükligraafikus on igal sõlmel ühendatud täpselt kaks serva, mis tähendab, et igal sõlmel on täpselt kaks kraadi.

Siin on näide tsükligraafikust:

Kahepoolne graafik

Sellised Graafikud on eriliigid graafikud, kus tipud on määratud kahele hulgale.

Kahepoolne graafik peab järgima reeglit:

• Kaks tippude komplekti peaksid olema erinevad, mis tähendab, et kõik tipud tuleb jagada kahte rühma või hulka.
• Sama komplekt Tipud ei tohiks moodustada servi.

Euleri graafik

Graafiku andmestruktuure loetakse Euleri graafikuks, kui kõigil tippudel on paarisarvuline aste. Termin tippude aste tähendab servade arvu, mis osutavad konkreetsele tipule või osutavad sellele.

Siin on näide Euleri graafikust:

Kõikidel tippudel on paarisastmed. Tiputel A, D, E ja H on kaks kraadi. Siin on sõlmel C neli kraadi, mis on ühtlane.

Hamiltoni graafik

Hamilton Graph on Connect Graph, kus saate külastada antud tipu kõiki tippe ilma sama sõlme uuesti külastamata või sama serva kasutamata. Seda tüüpi ühendatud graafikut tuntakse "Hamiltoni graafikuna". Tee, mida külastate, et kontrollida, kas antud graafik on Hamiltoni graafik või mitte, on tuntud kui Hamiltoni tee.

Siin on lihtne graafiku näide Hamiltoni kohta:

Sellel pildil saame külastada kõiki tippe ülaltoodud graafiku mis tahes sõlmest. Üks teedest võib olla ADCHBE. Samuti on võimalik leida Hamiltoni tsiklit. Hamiltoni tsükkel algab ja lõpeb samas tipus. Niisiis, Hamiltoni tsükkel saab olema ADCHBEA.