Vrste grafova u strukturi podataka s primjerima

Graf je nelinearna podatkovna struktura koja se sastoji od vrhova i bridova. Vrhovi sadrže informacije ili podatke, a rubovi djeluju kao poveznica između para vrhova.

Grafovi mogu biti više vrsta, ovisno o položaju čvorova i rubova. Evo nekoliko važnih vrsta grafikona:

Usmjereni graf

Rubovi usmjerenog grafa sadrže strelice koje označavaju smjer. Strelica određuje gdje je rub usmjeren ili završava.

Evo primjera usmjerenog grafa.

• Možemo ići od čvora A do D.
• Međutim, ne možemo ići od čvora D do čvora A jer rub pokazuje od A do D.
• Kako Graf nema težine, putovanje od vrha A do D će koštati isto kao i putovanje od D do F.

Neusmjereni graf

Neusmjereni graf sadrži rubove bez pokazivača. To znači da možemo putovati obrnuto između dva vrha.

Evo jednostavnog primjera neusmjerenog grafa.

U gornjem grafikonu,

• Možemo prijeći od A do B
• Također možemo prijeći iz B u A
• Rubovi ne sadrže smjerove.

To je primjer neusmjerenog grafa koji ima konačan broj vrhova i bridova bez težine.

Ponderirani grafikon

Graf koji sadrži težine ili troškove na rubovima naziva se ponderirani graf. Numerička vrijednost općenito predstavlja trošak premještanja s jednog vrha na drugi vrh. I usmjereni i neusmjereni graf mogu imati težine na svojim rubovima.

Evo primjera ponderiranog grafa (usmjerenog).

• A do B, postoji prednost, a težina je 5, što znači da će nas prelazak iz A u B koštati 5.
• A pokazuje na B, ali u ovom grafikonu, B nema izravni brid iznad A. Dakle, ne možemo putovati od B do A.
• Međutim, ako se želimo pomaknuti od A do F, postoji više puteva. Staze su ADF, ABF. ADF će koštati (10+11) ili 21.
• Ovdje će staza ABF koštati (5+15) ili 20. Ovdje dodajemo težinu svakog ruba na stazi.

Evo primjera neusmjerenog grafa s težinama:

Ovdje rub ima težinu, ali nema smjer. Dakle, to znači da će putovanje od vrha A do D koštati 10 i obrnuto.

Dvosmjerni graf

Dvosmjerni i neusmjereni grafovi imaju zajedničko svojstvo. To je

• Općenito, neusmjereni graf može imati jedan brid između dva vrha.

Na primjer:

• Ovdje će prelazak s A na D ili D na A koštati 10.
• U dvosmjernom grafu možemo imati dva ruba između dva vrha.

Evo primjera:

Putovanje od A do D koštat će nas 17, ali putovanje od D do A koštat će nas 12. Dakle, ne možemo dodijeliti dvije različite težine ako se radi o neusmjerenom grafu.

Beskonačni graf

Graf će sadržavati beskonačan broj rubova i čvorova. Ako je graf Beskonačan i također je povezan graf, tada će također sadržavati beskonačan broj bridova. Ovdje prošireni rubovi znače da više rubova može biti povezano s tim čvorovima preko rubova.

Evo primjera beskonačnog grafa:

Null Graph

Null Graph sadrži samo čvorove ili vrhove, ali bez rubova. Ako je dan graf G = (V, E), gdje su V vrhovi, a E bridovi, on će biti nula ako je broj bridova E nula.

Evo primjera nultog grafa:

Trivijalni graf

Struktura podataka grafa smatra se trivijalnom ako je prisutan samo jedan vrh ili čvor bez rubova.

Evo primjera trivijalnog grafa:

Višestruki grafikon

Graf se naziva multigraf kada je između dva vrha prisutno više bridova ili vrh ima petlju. Izraz "petlja" u strukturi podataka grafa znači rub koji pokazuje na isti čvor ili vrh. Multigraf može biti usmjeren i neusmjeren.

Evo primjera multigrafa:

Postoje dva brida od B do A. Štoviše, vrh E ima samopetlju. Gornji graf je usmjereni graf bez utega na rubovima.

Kompletan grafikon

Graf je potpun ako svaki vrh ima usmjerene ili neusmjerene bridove sa svim ostalim vrhovima.

Pretpostavimo da postoji ukupan broj vrhova V i da svaki vrh ima točno V-1 bridova. Tada će se ovaj graf zvati Potpuni graf. U ovoj vrsti grafa, svaki vrh je povezan sa svim ostalim vrhovima preko bridova.

Evo primjera potpunog grafa s pet vrhova:

Na slici možete vidjeti da je ukupan broj čvorova pet, a svi čvorovi imaju točno četiri ruba.

Povezani graf

Graf se naziva povezanim grafom ako krenemo od čvora ili vrha i obiđemo sve čvorove od početnog čvora. Za to bi trebao postojati barem jedan brid između svakog para čvorova ili vrhova.

Evo primjera povezanog grafikona:

Evo nekoliko objašnjenja gornjeg "cjelovitog primjera grafikona" Graf:

• Pod pretpostavkom da nema ruba između C i F, ne možemo putovati od A do G. Međutim, rub C do F omogućuje nam putovanje do bilo kojeg čvora iz danog čvora.
• Potpuni graf je povezani graf jer se možemo kretati s čvora na bilo koji drugi čvor u danom grafu.

Ciklički graf

Za graf se kaže da je ciklički ako postoji jedan ili više ciklusa prisutnih u grafu.

Evo primjera cikličkog grafikona:

Ovdje vrhovi A, B i C tvore ciklus.

Graf može imati više ciklusa unutar sebe.

Usmjereni aciklički graf (DAG)

Graf se naziva usmjereni aciklički graf ili DAG ako unutar grafa nema ciklusa. DAG je važan dok radite Topološko sortiranje ili pronalazak naloga za izvršenje. DAG je također važan za stvaranje sustava za planiranje ili skeniranje ovisnosti o resursima itd. Međutim, gornji grafikon ne sadrži nikakav ciklus unutra.

Evo jednostavnog primjera usmjerenog acikličkog grafa (DAG):

Grafikon ciklusa

Ciklusni graf nije isto što i ciklički graf. U Cycle Graphu svaki će čvor imati točno dva spojena ruba, što znači da će svaki čvor imati točno dva stupnja.

Evo primjera ciklusnog grafikona:

Bipartitni graf

Takve vrste Grafovi su posebne vrste grafova gdje su vrhovi dodijeljeni dvama skupovima.

Bipartitni graf mora slijediti pravilo:

• Dva skupa vrhova trebaju biti različita, što znači da svi vrhovi moraju biti podijeljeni u dvije grupe ili skupa.
• Vrhovi istog skupa ne bi trebali tvoriti rubove.

Eulerov graf

Strukture podataka grafa smatraju se Eulerovim grafom ako svi vrhovi imaju parni stupanj. Pojam stupnja vrhova označava broj bridova koji pokazuju ili izlaze iz određenog vrha.

Evo primjera Eulerovog grafa:

Svi vrhovi imaju parne stupnjeve. Vrh A, D, E i H imaju dva stupnja. Ovdje čvor C ima četiri stupnja, što je čak.

Hamiltonov graf

Hamilton Graph je Connect Graph, gdje možete posjetiti sve vrhove iz danog vrha bez ponovnog posjećivanja istog čvora ili korištenja istog ruba. Ova vrsta povezanog grafa poznata je kao "Hamiltonov graf". Put koji posjećujete kako biste provjerili je li dani graf Hamiltonov graf ili nije poznat je kao Hamiltonov put.

Evo jednostavnog primjera grafikona Hamiltona:

Na ovoj slici možemo posjetiti sve vrhove iz bilo kojeg čvora u gornjem grafikonu. Jedan od putova može biti ADCHBE. Također je moguće pronaći Hamiltonov ciklus. Hamiltonov ciklus počinje i završava na istom vrhu. Dakle, Hamiltonov ciklus će biti ADCHBEA.