Primjene DFS i BFS algoritama za Dijkstrin algoritam, traženje povezanih komponenti grafa i Kruskalov algoritam

završni rad

• Naslov (engleski): Applications of DFS and BFS Algorithms for Dijkstras Algorithm, Finding Connected Components and Kruskals Algorithm
• Autor: Mario Šaško
• Mentor: Andrea Aglić Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Josip Ž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 obrane: 2019-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: teorija grafova; pretraživanje u širinu; BFS; pretraživanje u dubinu; DFS; Dijkstrin algoritam; povezane komponente; Kruskalov algoritam
• Ključne riječi (engleski): graph theory; breadth-first search; BFS; depth-first search; DFS; Dijkstra's algorithm; connected components; Kruskal's algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:538765
• Studijski program: Naziv: 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 resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2020-01-07 22:17:32