Uvod u graf u strukturi podataka
Grafovi su nelinearne strukture podataka koje sadrže konačni skup čvorova i rubova. Čvorovi su elementi, a rubovi su poredani parovi veza između čvorova.
Primijetite riječ nelinearna. Nelinearna struktura podataka je ona u kojoj elementi nisu poredani rednim redoslijedom. Na primjer, niz je linearna struktura podataka jer su elementi raspoređeni jedan za drugim. Možete prelistavati sve elemente matrice u jednom pokretu. To nije slučaj s nelinearnim strukturama podataka. Elementi nelinearne strukture podataka raspoređeni su u više razina, često slijedeći hijerarhijski uzorak. Grafikoni su nelinearni.
Sljedeća riječ na koju treba obratiti pozornost je konačna. Graf definiramo tako da ima konačan i brojiv broj čvorova. To je prilično nepodoban izraz. U osnovi, graf može imati neograničen broj čvorova i još uvijek je konačan. Na primjer, obiteljsko stablo koje seže od Adama i Eve. Ovo je relativno beskonačan graf, ali još uvijek se može računati i stoga se smatra konačnim.
Primjer iz stvarnog svijeta
Najbolji primjer grafova u stvarnom svijetu je Facebook. Svaka osoba na Facebooku je čvor i povezana je preko rubova. A je prijatelj B. B je prijatelj C i tako dalje.
nazivlja
Ovdje su navedene Terminologije grafikona u strukturi podataka
1. Grafički prikaz: Graf je obično predstavljen kao par skupova (V, E). V je skup točaka ili čvorova. E je skup rubova. U gornjem primjeru,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Čvor ili vrh: Elementi grafikona povezani su preko rubova.
3. Rubovi: Put ili linija između dvaju vrhova u grafikonu.
4. susjedni čvorovi: dva čvora nazivaju se susjedna ako su povezana preko ruba. U gornjem primjeru, čvor A je uz čvorove B, C i D, ali ne i čvor E.
5. Put: Put je slijed rubova između dvaju čvorova. To je u osnovi prolaz koji počinje na jednom čvoru i završava na drugom. U gornjem primjeru postoji više staza od čvora A do čvora E.
Put (A, E) = (AB, BE)
ILI
Put (A, E) = (AC, CD, DE)
ILI
Put (A, E) = (AD, DE)
6. Neizmjerni graf: Neusmjerni graf je onaj gdje rubovi ne određuju određeni smjer. Rubovi su dvosmjerni.
Primjer
Stoga se u ovom primjeru izmjenični rub ruba može prelaziti od A do C i od C do A. Slično svim rubovima. Put od čvora B do čvora C bio bi (BA, AC) ili (BD, DC).
7. Usmjereni graf: usmjereni graf je onaj gdje se rubovi mogu kretati samo u određenom smjeru.
Primjer
Dakle, u istom primjeru sada su rubovi usmjereni. Možete samo preći rub duž njegovog smjera. Sada nema staze od čvora B do čvora C sada.
8. Grafički ponderirani: Graf se ponderira gdje su rubovi povezani s težinom. To je općenito trošak prelaska ruba.
Primjer
Dakle, u istom primjeru sada rubovi s njima imaju određenu težinu. Postoje dva moguća putanja između čvora A do čvora E.
Put 1 = (AB, BD, DE), težina1 = 3 + 2 + 5 = 10
Path2 = (AC, CD, DE), Weight2 = 1 + 3 + 5 = 9
Jasno je da bi radije Path2 ako je cilj doći do čvora E iz čvora A s minimalnim troškovima.
Osnovne operacije na grafu
Ovdje su navedene osnovne operacije grafikona
1. Dodavanje / uklanjanje vertexa
Ovo je najjednostavnija operacija na grafikonu. Grafu jednostavno dodate tačku. Ne mora biti povezan s bilo kojom drugom kralježnicom preko ruba. Pri uklanjanju kralježnice morate ukloniti sve rubove koji potječu od i završavaju na izbrisanoj kralježnici.
2. Dodavanje / uklanjanje ivica
Ova operacija dodaje ili uklanja rub između dvaju vrhova. Kada se brišu svi rubovi koji potiču od vrha i završavaju se, ona postaje izolirana.
3. Prva potraga za kruhom (BFS)
Ovo je transverzalna operacija na grafu. BFS horizontalno prelazi graf. To znači da prelazi sve čvorove na jednoj razini prije nego što prijeđe na sljedeću razinu.
BFS algoritam započinje pri vrhu prvog čvora na grafikonu, a zatim prolazi kroz sve susjedne čvorove na njemu. Jednom kada se prelaze svi susjedni čvorovi, algoritam ponavlja isti postupak za podređene čvorove.
Primjer
Pomicanje gornjeg grafa na način BFS proizlazi iz A -> B -> C -> D -> E -> F -> G. Algoritam počinje od čvora A i prolazi kroz sve njegove susjedne čvorove B, C i D. sva četiri čvora kao posjećena. Nakon što su prešli svi susjedni čvorovi A, algoritam prelazi na prvi susjedni čvor A i ponavlja isti postupak. U ovom slučaju, čvor je B, a susjedni čvorovi na B su E i F. Dalje, prolaze se susjedni čvorovi na C. Nakon što su posjećeni svi čvorovi, operacija se završava.
4. Prva dubina pretraživanja (DFS)
Dubina prve pretrage ili DFS prelazi grafikon okomito. Započinje korijenskim čvorom ili prvim čvorom grafikona i prelazi sve podređene čvorove prije nego što se preseli na susjedne čvorove.
Primjer
Pomicanje gornjeg grafa na način BFS proizlazi iz A -> B -> E -> F -> C -> G -> D. Algoritam polazi od čvora A i prolazi kroz sve njegove podređene čvorove. Čim naiđe na B, čini se da ima daljnje dječje čvorove. Dakle, podređeni čvorovi B prelaze se prije nego što prijeđu na sljedeći podređeni čvorov A.
Realna implementacija grafikona
- Dizajn električnih krugova za prijenos snage.
- Dizajn mreže međusobno povezanih računala.
- Proučavanje molekularne, kemijske i stanične strukture bilo koje tvari, npr. Ljudske DNK.
- Izrada prometnih ruta između gradova i mjesta u gradu.
Zaključak - Grafikon u strukturi podataka
Grafovi su vrlo koristan pojam u strukturama podataka. Ima praktične implementacije u gotovo svim poljima. Vrlo je važno razumjeti osnove teorije grafova, razviti razumijevanje algoritama grafske strukture.
Ovaj je članak bio samo uvod u grafikone. To je samo odskočni kamen. Preporučuje se daljnji zaron u temi teorije grafova.
Preporučeni članci
Ovo je vodič za graf u strukturi podataka. Ovdje smo raspravljali o terminologijama i osnovnim operacijama grafikona u strukturi podataka. Možete pogledati i sljedeći članak da biste saznali više -
- Intervjui o strukturi podataka
- Podaci modela u Cassandri
- Što je podatkovni mart?
- Što je podatkovni znanstvenik?