prikaz prve stranice dokumenta Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam
Rad nije dostupan
završni rad
Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. urn:nbn:hr:168:538765
Šaško, Mario
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Šaško, M. (2019). Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam (Završni rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:538765

Šaško, Mario. "Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. https://urn.nsk.hr/urn:nbn:hr:168:538765

Šaško, Mario. "Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. https://urn.nsk.hr/urn:nbn:hr:168:538765

Šaško, M. (2019). 'Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam', Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 27.12.2024., https://urn.nsk.hr/urn:nbn:hr:168:538765

Šaško M. Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam [Završni rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2019 [pristupljeno 27.12.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:538765

M. Šaško, "Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam", Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2019. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:538765

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:538765
Podaci o radu
NaslovPrimjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam
Naslov (engleski)Applications of DFS and BFS Algorithms for Dijkstras Algorithm, Finding Connected Components and Kruskals Algorithm
AutorMario Šaško
MentorAndrea Aglić Aljinović (mentor)
Član povjerenstvaAndrea Aglić Aljinović (predsjednik povjerenstva)
Član povjerenstvaMario Krnić (član povjerenstva)
Član povjerenstvaJosip Žubrinić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
Zagreb
Datum i država obrane2019-07-12, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
U moderno vrijeme, primjene teorije grafova su sveprisutne. Pojam grafa, osnovna klasifikacija grafova te reprezentacija grafa u memoriji, nužni su razumijevanje složenijih postupaka obilaska grafa i pronalaska najkraćeg puta, pronalaska povezanih komponenti i minimalnog razapinjućeg stabla. Pretraživanjem u širinu ili BFS algoritmom sustavno se pretražuju vrhovi jedne razine grafa prije prelaska na sljedeću razinu. Suprotno, pretraživanjem u dubinu ili DFS algoritmom obilaze se vrhovi najdublje razine, prije nego se backtrackingom algoritam vraća na pliće razine. U slučaju težinskog grafa, Dijkstrinim algoritmom pronalazi se put s najkraćom cijenom. Pretraživanje u širinu specijalan je slučaj Dijkstrinog algoritma, u kojem su težine bridova konstantne. Osnovna povezanost komponenti definirana nad neusmjerenim grafom, u slučaju usmjerenog grafa dijeli se na slabu i jaku povezanost. Svi oblici povezanosti rješivi su algoritmima BFS i DFS. Neovisan o njima, problem pronalaska minimalnog razapinjućeg stabla rješava se Kruskalovim algoritmom. Efikasno rješenje ostvaruje se specifičnom podatkovnom strukturom za upravljanje nepreklapajućim podskupovima inicijalnog skupa, tzv. strukturom Union-find.
Sažetak (engleski)
In modern times, applications of graph theory are omnipresent. Concept of graph, basic graph classification and the representation of the graph in the memory are necessary to understand the more complex procedures of traversing the graph and finding the shortest path, finding connected components and the minimum spanning tree. Breadth-first search or BFS systematically scans vertices of one level before going to the next level. On the contrary, depth-first search or DFS visits the vertices at the deepest level before the algorithm, using backtracking technique, returns to shallower levels. In the case of a weighted graph, Dijkstra's algorithm finds the path with the lowest cost. Breadth-first search is a special case of Dijkstra's algorithm, in which edge weights are constant. Basic definition of connectivity defined for an undirected graph, in case of a directed graph is divided into weak and strong connectivity. All forms of connectivity are solved by BFS or DFS. Regardless of them, the problem of finding the minimum spanning tree is solved by Kruskal's algorithm. An efficient solution is achieved through usage of the specific data structure for managing non-overlapping subsets of the initial set, so-called Union-find.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:538765
Studijski programNaziv: Računarstvo
Vrsta studija: sveučilišni
Stupanj studija: preddiplomski
Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2020-01-07 22:17:32