Primjene DFS i BFS algoritama za A* algoritam, 2-obojivost i toploško sortiranje u grafovima

undergraduate thesis

• Title (english): Applications of DFS and BFS Algorithms for A* Search Algorithm, Bipartiteness Testing and Topological Sorting
• Author: Bruno Sačarić
• 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 ovom radu prezentirani su osnovni algoritmi pretraživanja grafa u širinu i dubinu,
te kako se njihova struktura može iskoristiti za napredniji algoritam A* te algoritme
testiranja 2-obojivosti grafa i topološkog sortiranja koji se koriste za mnoge učestale
probleme u teoriji grafova. Definirani su osnovni pojmovi teorije grafova potrebni za
razumijevanje danih algoritama. Dodatno, pokazana je implementacija algoritama u
Javi te je objašnjeno kako koristiti isti programski kod za više algoritama.

Abstract (english)

This paper presents basic graph search algorithms Breadth-First Search and Depth-
First Search and how their structure can be used for more advanced algorithms such
as A*, bipartiteness testing and topological search algorithm which are used for many
graph theory problems. Basic graph theory definitions are given in order to understand
the given algorithms. Additionally, the implementation of the algorithms is shown in
Java and it is explained how to reuse programming code for multiple algorithms.

• Keywords: Algoritmi pretraživanja grafa; A*; topološko sortiranje; 2-obojivost grafa; pretraživanje u širinu; pretraživanje u dubinu
• Keywords (english): Graph search algorithms; A*; topological sort; bipartiteness testing; breadth-first search; depth-first search
• Language: croatian
• URN:NBN: urn:nbn:hr:168:255457
• 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 21:55:06