Pojam grafa srećemo svakodnevno, vjerovatno nismo ni svjesni primjene teorije grafova oko nas. Stoga, u ovom blogu istražit ćemo kako se teorija grafova oslikava na programiranje i pružiti neke specifične primjere njenih aplikacija u OOP-u.
Pojam grafa srećemo svakodnevno, vjerovatno nismo ni svjesni primjene teorije grafova oko nas. Stoga, u ovom blogu istražit ćemo kako se teorija grafova oslikava na programiranje i pružiti neke specifične primjere njenih aplikacija u objektno-orijentisanom programiranju. Važno je pomenuti da su neki od osnovnih algoritama razvijeni upravo koristeći grafove, kao što su pretrage u dubinu (DFS) ili pretrage u širinu (BFS).
Razumijevanje Osnova Teorije Grafova
Grafovi su apstraktni matematički entiteti koji se koriste za modeliranje i analizu odnosa između objekata. Formalno, graf se definira kao uređeni par G=(V,E), gdje je V skup čvorova (vertices), a E skup bridova/ivica (edges) koji povezuju čvorove. Ovi čvorovi i bridovi mogu predstavljati različite entitete i odnos između njih.
- Čvorovi (Vertices): Čvorovi u grafu predstavljaju pojedinačne objekte ili entitete. Na primjer, u društvenoj mreži, svaki korisnik može biti čvor, ili u mreži puteva, svaki raskrsnica cesta može biti čvor.
- Bridovi/Ivice (Edges): Bridovi predstavljaju odnose između čvorova. Ako je čvor A povezan s čvorom B, taj odnos se modelira bridom između A i B. Brid može biti neusmjeren (slika 1. a) ili usmjeren (slika 1. b), ovisno o tome ima li smjer ili ne.
Slika 1.
Kako bismo dublje zakoračili u ovu fascinantnu oblast, važno je razumjeti nekoliko ključnih pojmova koji oblikuju svojstva grafova :
Težina – bridovi imaju ili nemaju težinu
Cikličnost – ukoliko postoji prolazak kroz bridove tako da se iz nekog čvora može ponovno doći u njega
Stablo – neusmjereni graf s N čvorova i N-1 bridova
Usmjereni graf bez ciklusa (engl. Directed Acyclic Graph – DAG)
Povezanost grafova i algoritama stvara simbiozu koja obogaćuje svijet programiranja. Grafovi nude strukturu, a algoritmi pružaju rješenja za kompleksne probleme. Kroz ovu harmoniju, programeri stvaraju efikasne i intuitivne aplikacije, utemeljene na temeljima teorije grafova i algoritamske inteligencije. U ovom blogu ćemo detaljnjije opisati algoritme pretrage, te Djikstra algoritam koji pronalazi najkraći put izmedju bilo koja dva grafa čvora u grafu.
Algoritmi pretrage
DFS (Pretraživanje u dubinu)
DFS, pretraživanje u dubinu, predstavlja sofisticiranu tehniku koja otvara vrata beskrajnim mogućnostima unutar grafova. Ovaj algoritam temelji se na pažljivom sistematičnom istraživanju u dubinu tako što obilazi granu po granu, omogućavajući programerima da prodru u srž strukture grafa. Kroz DFS, ne samo da se efikasno pronalaze putevi, već se pruža i temeljito razumijevanje povezanosti između čvorova. Njegove primjene sežu od analize igara, gdje se koristi za istraživanje mogućih scenarija, do otkrivanja kompleksnih povezanosti u društvenim mrežama, međutim beskoriso ga je koristit kada je dubina grafa beskonačna. DFS nije samo algoritam pretrage; to je ključ za dublje razumijevanje i rješavanje problema koji zahtijevaju detaljnu analizu strukture grafa.
BFS (Pretraživanje u širinu)
Suprotno DFS-u, BFS, pretraživanje u širinu, donosi horizontalnu eksploziju mogućnosti u istraživanju grafova, te se pretraga vrši nivo po nivo. Fokusiranje na širinu omogućuje programerima identifikaciju najkraćih puteva i optimizaciju pretrage unutar grafa. Ovaj algoritam pruža jedinstvenu perspektivu koja se ogleda u širokom spektru primjena, počevši od algoritama najkraćeg puta, gdje je efikasno pronalaženje optimalnih rješenja od suštinske važnosti, do otkrivanja nivoa povezanosti u grafovima koji modeliraju kompleksne informacijske mreže. Za razliku od DFS – a, korisno ga je koristiti kada nismo sigurni da li je graf konačne dubine.
Za kraj ćemo spomenuti i Djikstra algoritam koji služi za nalaženje najkraćeg puta od jednog čvora do svih ostalih. Usredsređen je na minimalnu ukupnu težinu puta do određenog čvora. Filozofija algoritma leži u neprestanoj optimizaciji, tražeći put koji minimizira težinu pređenog puta. Ovo čini Djikstrin algoritam iznimno korisnim u raznim scenarijima, poput optimizacije rutiranja mreža ili planiranja logističkih ruta.
Algritam : Korak-Po-Korak
- Inicijalizacija:
- Algoritam počinje inicijalizacijom težina čvorova, postavljajući početni čvor s težinom 0, dok se ostali čvorovi postavljaju na beskonačnost. Ova faza priprema teren za daljnje korake.
- Izbor Najjeftinijeg Čvora:
- Djikstrin algoritam zatim bira čvor s najmanjom trenutnom težinom. Ovaj čvor postaje “aktivan” i svi susjedni čvorovi se provjeravaju u potrazi za kraćim putem.
- Ažuriranje Težina:
- Ako se pronađe put do susjednog čvora koji je kraći od trenutne težine, težina tog čvora se ažurira. Ovaj korak osigurava neprestano ažuriranje puteva kako bi se održala minimalna težina.
- Ponavljanje:
- Postupak izbora najjeftinijeg čvora, provjere susjeda i ažuriranja težina ponavlja se sve dok svi čvorovi ne postanu “aktivni” i dok se ne pronađu najkraći putevi do svih ciljnih čvorova.
Neke od osnovnih primjena Djikstrinog Algoritma su:
- Rutiranje Mreža:
- Optimizacija putanja u telekomunikacijskim mrežama ili internetu.
- GPS i Navigacija:
- Pronalaženje najbržih puteva između lokacija na temelju stvarnih vremenskih i prometnih uvjeta.
- Robotika:
- Određivanje optimalnih putanja kretanja robota u određenom prostoru.
U svakodnevnom životu, pojam grafa možda nam nije uvijek očigledan, ali teorija grafova i njene primjene prožimaju mnoge aspekte našeg okruženja. Kroz ovaj blog, istražili smo kako se teorija grafova prenosi na područje programiranja, nudeći programerima moćne alate za rješavanje složenih problema. Kroz razumijevanje strukture grafova i primjene algoritama, otvaramo vrata inovacijama i efikasnom rješavanju problema. Grafovi nisu samo crteži na papiru; oni su putokazi ka programerskom uspjehu.
Do sljedećeg bloga,
Happy Coding !
Izvor: lonac.pro
