Vrste grafova u strukturi podataka s primjerima

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

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

Usmjereni graf

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

Usmjereni graf

• 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 bridove bez pokazivača. To znači da se možemo kretati obrnuto između dva vrha. Evo jednostavnog primjera neusmjerenog grafa.

Neusmjereni graf

U gornjem grafikonu,

• Možemo se kretati od točke A do točke B.
• Također se možemo pomaknuti iz B u A.
• Rubovi ne sadrže smjerove.

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

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 iz jednog vrha u drugi. I usmjereni i neusmjereni grafovi mogu imati težine na svojim rubovima. Evo primjera ponderiranog grafa (usmjerenog).

Usmjereni graf s težinom

• Od A do B, postoji rub, a težina je 5, što znači da će nas premještanje od A do B koštati 5.
• A pokazuje na B, ali u ovom grafu, B nema izravnu prednost nad A. Dakle, ne možemo putovati od B do A.
• Međutim, ako se želimo pomaknuti od A do F, postoji više puteva. Putevi su ADF i ABF. ADF će koštati (10+11) ili 21.
• Ovdje će put ABF koštati (5+15) ili 20. Ovdje zbrajamo težinu svakog brida u putu.

Evo primjera neusmjerenog grafa s težinama:

Neusmjereni graf s težinom

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:

Dvosmjerni graf

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 bridova i čvorova. Ako je graf beskonačan i ujedno povezan graf, tada će sadržavati i beskonačan broj bridova. Ovdje prošireni bridovi znače da se više bridova može spojiti na te čvorove putem bridova. Evo primjera beskonačnog grafa:

Beskonačni graf

Null Graph

Null graf sadrži samo čvorove ili vrhove, ali bez bridova. Ako je zadan graf G = (V, E), gdje su V vrhovi, a E bridovi, bit će null ako je broj bridova E nula. Evo primjera Null grafa:

Null Graph

Trivijalni graf

Struktura podataka grafa smatra se trivijalnom ako je prisutan samo jedan vrh ili čvor bez bridova. Evo primjera trivijalnog grafa:

Višestruki grafikon

Graf se naziva multigraf kada postoji više bridova između dva vrha ili vrh ima petlju. Izraz "petlja" u strukturi podataka grafa označava brid koji pokazuje na isti čvor ili vrh. Multigraf može biti usmjeren ili neusmjeren. Evo primjera multigrafa:

Postoje dva brida od B do A. Štoviše, vrh E ima vlastitu petlju. Gornji graf je usmjereni graf bez težina na bridovima.

Kompletan grafikon

Graf je potpun ako svaki vrh ima usmjerene ili neusmjerene bridove sa svim ostalim vrhovima. Pretpostavimo da postoji ukupno V vrhova i da svaki vrh ima točno V-1 bridova. Tada će se ovaj graf nazivati ​​potpunim grafom. U ovoj vrsti grafa, svaki vrh je povezan sa svim ostalim vrhovima putem 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 brida.

Povezani graf

Graf se naziva povezani graf ako počinjemo od čvora ili vrha i možemo putovati do svih čvorova iz početnog čvora. Za to mora postojati barem jedan brid između svakog para čvorova ili vrhova. Evo primjera povezanog grafa:

Evo objašnjenja gore navedenog povezanog grafa:

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

Ciklički graf

Graf se naziva cikličkim ako u grafu postoji jedan ili više ciklusa. Evo primjera cikličkog grafa:

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 pri izvođenju Topološko sortiranje ili pronalaženje redoslijeda izvršenja. DAG je također važan za stvaranje sustava raspoređivanja ili skeniranje ovisnosti resursa itd. Međutim, gornji graf ne sadrži nikakav ciklus unutra. Evo jednostavnog primjera usmjerenog acikličkog grafa (DAG):

Grafikon ciklusa

Ciklični graf nije isto što i ciklički graf. U cikličkom grafu, svaki čvor će imati točno dva povezana brida, što znači da će svaki čvor imati točno dva stupnja. Evo primjera cikličkog grafa:

Bipartitni graf

Takve vrste Grafovi su posebne vrste grafova gdje su vrhovi dodijeljeni dvama skupovima. Dvodijelni graf mora slijediti pravilo:

• Dva skupa vrhova trebaju biti različita, što znači da svi vrhovi moraju biti podijeljeni u dvije skupine ili skupa.
• Vrhovi istog skupa ne smiju formirati nikakve bridove.

Eulerov graf

Struktura podataka Graf smatra se Eulerovim grafom ako svi vrhovi imaju paran stupanj. Pojam stupanj vrhova označava broj bridova koji pokazuju na ili iz određenog vrha. Evo primjera Eulerovog grafa:

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

Hamiltonov graf

Hamiltonov graf je povezani graf u kojem možete posjetiti sve vrhove iz zadanog vrha bez ponovnog posjećivanja istog čvora ili korištenja istog brida. Ova vrsta povezanog grafa poznata je kao "Hamiltonov graf". Put koji posjećujete kako biste provjerili je li zadani graf Hamiltonov graf ili ne poznat je kao Hamiltonov put. Evo jednostavnog primjera Hamiltonovog grafa:

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

Pitanja i odgovori