Upoznajte se s podatkovnim strukturama koje svakodnevno koristite
? Dobrodošli! Krenimo s nekim vitalnim kontekstom. Da vas pitam nešto:
Use Koristite li Google pretraživanje?
✅ Koristite li Google Maps?
Use Koristite li stranice na društvenim mrežama?
Ako je vaš odgovor "da" na bilo koje od ovih pitanja, tada ste definitivno koristili grafikone, a niste to ni znali! Iznenađeni? ? I ja sam bio! Ovaj će vam članak pružiti vizualni uvod u svijet grafova, njihovu svrhu, elemente i vrste.
Ove su strukture podataka zaista privukle moju pažnju zbog svojih nevjerojatnih mogućnosti. Toliko su moćni da nećete ni zamisliti koliko raznolike mogu biti njihove stvarne aplikacije. Započnimo! ?
Applications Aplikacije u stvarnom svijetu - čarolija započinje!
Grafovi se koriste u raznim industrijama i poljima:
- GPS sustavi i Google Maps koriste grafikone kako bi pronašli najkraći put od jednog odredišta do drugog.
- Društvene mreže koriste grafikone za predstavljanje veza između korisnika.
- Algoritam Google pretraživanja koristi grafikone za određivanje relevantnosti rezultata pretraživanja.
- Operacijsko istraživanje polje je koje koristi grafikone za pronalaženje optimalnog puta za smanjenje troškova prijevoza i isporuke robe i usluga.
- Čak se i Kemija koristi grafikonimapredstavljati molekule !!! ❤️
Njihove su primjene nevjerojatne, zar ne?
Počnimo naše putovanje ovim svijetom! ?
? Upoznajte grafikone!
Sad kad imate određeni kontekst, krenimo s razgovorom o njihovoj glavnoj svrsi i elementima.
Grafovi se koriste za predstavljanje, pronalaženje, analizu i optimizaciju veza između elemenata (kuće, zračne luke, lokacije, korisnici, članci itd.).
Ovo je primjer kako grafikon izgleda:
? Građevni blokovi
Siguran sam da ste na gornjem dijagramu primijetili dva glavna elementa: krugove i debele crte koji ih povezuju. Zovu se čvorovi, odnosno rubovi .
Pogledajmo ih detaljnije! ?
- Čvorovi: oni su elementi koji stvaraju mrežu. Mogli bi predstavljati kuće, lokacije, zračne luke, luke, autobusne stanice, zgrade, korisnike, u osnovi sve što biste mogli predstaviti kao povezano s drugim sličnim elementima u mreži.
- Rubovi: oni su veze između čvorova. Mogli bi predstavljati ulice, letove, autobusne rute, vezu između dva korisnika na društvenoj mreži ili bilo što drugo što bi moglo predstavljati vezu između čvorova u kontekstu s kojim radite.
Što se događa ako nema veze?
Ako dva čvora nisu povezana rubom, to znači da između njih nema izravne veze. Ali nemojte paničariti! ? Možda ćete i dalje moći prelaziti s jednog čvora na drugi slijedeći niz rubova, slično vožnji kroz nekoliko ulica do vašeg konačnog odredišta. ?️ ? ?
Na primjer, na donjem dijagramu, iako ne postoji izravna veza ( rub ) između ljubičastog čvora (lijevo) i žutog čvora (desno), možete prijeći od ljubičastog čvora do narančastog čvora, do ružičastog čvora, do zelenog čvora i napokon do žutog čvora. ?
Ovo je ključni aspekt grafikona da element koji tražite možete tražiti slijedeći dostupne putove.
? Označavanje i terminologija
Vrlo je važno naučiti formalni "jezik" za rad s grafikonima:
|V|= Ukupan broj vrhova ( čvorova ) na grafikonu.|E|= Ukupan broj veza ( rubova ) na grafikonu.
U donjem primjeru, |V| = 6jer postoji šest čvorova (krugova) i
|E| = 7jer postoji sedam bridova (linija).
Vrste grafikona
Grafovi se klasificiraju na temelju karakteristika njihovih bridova (veza). Pogledajmo ih detaljno! ?
1️⃣ Usmjereni grafikoni
U usmjerenim grafovima rubovi imaju smjer. Oni prelaze s jednog čvora na drugi i kroz taj rub nema načina da se vrate na početni čvor.
Kao što možete vidjeti na donjem dijagramu, rubovi (veze) sada imaju strelice koje upućuju na određeni smjer. Zamišljajte ove rubove kao jednosmjerne ulice. Možete ići u jednom smjeru i doći do odredišta, ali ne možete se vratiti tom istom ulicom, pa morate pronaći alternativni put.
Na primjer, ako kreiramo grafikon za uslugu dostave pizze, koji predstavlja grad, dvije kuće (čvorovi) mogu biti povezane jednosmjernom ulicom (rubom). Ovom ulicom ste mogli doći od kuće A do kuće B, ali se niste mogli vratiti, pa biste morali ići alternativnim putem.
? Napomena: U usmjerenom grafikonu možda se uopće nećete moći vratiti na svoje početno mjesto ako nema putanje s odgovarajućim uputama. ? Na donjem dijagramu možete vidjeti da možete uspješno prijeći iz ljubičastog čvora u zeleni čvor, ali primijetite da ne postoji način za povratak iz zelenog čvora u ljubičasti čvor jer su rubovi „jednosmjerne ulice. "
2️⃣ Neusmjereni grafikoni
U ovoj vrsti grafa rubovi su usmjereni (nemaju određeni smjer). Neusmjerene rubove smatrajte dvosmjernim ulicama. Možete prijeći s jednog čvora na drugi i vratiti se istim "putem".
? Napomena: Kada vidite dijagram grafa na kojem rubovi nemaju strelice usmjerene u određenom smjeru, možete pretpostaviti da je graf neusmjeren.
? Za našu uslugu dostave pizze to bi značilo da motocikl za dostavu može ići od izvora do odredišta istom ulicom ili putem (na njihovo olakšanje! ?).
Na donjem grafikonu možete ići od ljubičastog čvora do zelenog čvora i vratiti se istim putem , tako da ne dođete do točke bez povratka. ?
? Utezi? - Da, utezi!
1️⃣ Ponderirani grafikoni
U ponderiranim grafovima svaki rub ima povezanu vrijednost (koja se naziva težina) . Ova se vrijednost koristi za predstavljanje određene mjerljive veze između čvorova koje povezuju.
Na primjer, ponderi mogu predstavljati udaljenost, vrijeme, broj veza koje dijele dva korisnika na društvenoj mreži ili bilo što drugo što se može koristiti za opisivanje veze između čvorova u kontekstu s kojim radite.
Te utege koristi Dijkstrin algoritam za optimizaciju ruta pronalaženjem najkraćih ili najskupljih staza između čvorova u mreži. (Pratite članak za Dijkstrin algoritam! ?).
2️⃣ Neponderirani grafovi
Nasuprot tome, neponderirani grafovi nemaju pondere povezane s rubovima. Primjer ove vrste grafova može se naći na društvenim mrežama, gdje rubovi predstavljaju vezu između dva korisnika. Veza se ne može kvantificirati. Stoga rub nema težinu.
? Napomena: Možda ste primijetili da, za sada, naši grafovi imaju samo jedan rub povezuje svaki par čvorova. Prirodno je pitati se može li biti više od jednog ruba između para čvorova. Posve je to moguće s M ultigrafima! T ej može imati više rubova spojne isti par čvorova.
? Broj rubova! - Važan čimbenik
Vrlo je važno znati ima li graf mnogo ili malo bridova, jer je to presudan faktor za odlučivanje kako ćete predstaviti ovu strukturu podataka u svom kodu. Pogledajmo različite vrste! ?
1️⃣ Gusti grafikoni
Gusti grafikoni imaju mnogo bridova. Ali čekaj! ⚠️ Znam o čemu moraš razmišljati, kako možeš odrediti što se kvalificira kao „mnogo rubova“? Ovo je malo previše subjektivno, zar ne? ? Slažem se s tobom, pa hajde da je malo kvantificiramo:
Find Pronađimo maksimalan broj bridova u usmjerenom grafu. Ako |V|u usmjerenom grafu postoje čvorovi (u donjem primjeru, šest čvorova), to znači da svaki čvor može imati do |v|veza (u donjem primjeru šest veza).
Zašto? Budući da bi se svaki čvor mogao povezati sa svim ostalim čvorovima i sam sa sobom (vidi "petlju" u nastavku) . Dakle, maksimalan broj rubova da je graf može imati je , što je ukupan broj čvorova pomnožen maksimalni broj veza koje svaki čvor može imati.|V|*|V|
Kada je broj bridova na grafikonu blizak maksimalnom broju rubova, graf je gust. ?
? Napomena: "Petlje" se javljaju kada čvor ima rub koji ga povezuje sa sobom. Čudno i zanimljivo, zar ne? ?
2️⃣ Rijetki grafikoni
Rijetki grafikoni imaju malo bridova. Kao što možete vidjeti na donjem dijagramu, nema mnogo veza između čvorova.
Kada je broj bridova na grafikonu znatno manji od maksimalnog broja rubova, graf je rijedak. ?
⭕️ Upoznajte cikluse!
Sada ćemo vidjeti vitalni koncept za razumijevanje grafikona, ciklusa.
Vjerojatno ste primijetili da ako slijedite slijed veza na grafikonu, možda ćete pronaći put koji će vas vratiti na isti čvor. To je poput "hodanja u krugu", točno kao da se vozite svojim gradom i krenete stazom koja bi vas mogla vratiti na početno mjesto.
U grafikonima se ti "kružni" putovi nazivaju "ciklusima". To su valjane staze koje započinju i završavaju na istom čvoru. Na primjer, na donjem dijagramu možete vidjeti da ako započnete s bilo kojim čvorom, možete se vratiti na isti čvor slijedeći rubove.
Ciklusi nisu uvijek "izolirani", jer mogu biti dio većeg grafa. Možete ih otkriti započinjanjem pretraživanja na određenom čvoru i pronalaženjem puta koji vas vodi natrag do istog čvora.
? Ukratko ...
- Grafovi su sjajne podatkovne strukture koje svakodnevno koristite putem Google pretraživanja, Google karata, GPS-a i društvenih mreža.
- Koriste se za predstavljanje elemenata koji dijele veze .
- Elementi u grafu nazivaju se Čvorovi, a veze između njih Rubovi .
- Grafovi se mogu usmjeriti kada njihovi rubovi imaju određenu orijentaciju, sličnu jednosmjernim ulicama, ili neusmjereni, ako njihovi rubovi nemaju određenu orijentaciju, slično dvosmjernim ulicama.
- Rubovi mogu imati povezanu vrijednost, koja se naziva težina .
- Ako graf ima mnogo bridova, naziva se gust graf. Inače, ako ima malo bridova, naziva se rijetki graf.
- Niz veza može formirati ciklus ako stvore put koji vam omogućuje povratak na isti čvor.
Nastavite učiti o tim nevjerojatnim strukturama podataka! To će vam se potpuno isplatiti za vašu budućnost kao programera. Trenutno učim o strukturama podataka i smatram ih potpuno fascinantnima. ? ? ❤️
Važno je ne prestati ispitivati. Znatiželja ima svoj razlog postojanja. - Albert Einstein? Hvala!
Zaista se nadam da vam se svidio moj članak. ❤️
Prati me naCvrkut. ?