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

undergraduate thesis

• Title (english): Applications of DFS and BFS Algorithms for Dijkstras Algorithm, Finding Connected Components and Kruskals Algorithm
• Author: Mario Šaško
• Mentor: Andrea Aglić Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Josip Žubrinić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: teorija grafova; pretraživanje u širinu; BFS; pretraživanje u dubinu; DFS; Dijkstrin algoritam; povezane komponente; Kruskalov algoritam
• Keywords (english): graph theory; breadth-first search; BFS; depth-first search; DFS; Dijkstra's algorithm; connected components; Kruskal's algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:538765
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-07 22:17:32