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

završni rad

• Naslov (engleski): Applications of DFS and BFS Algorithms for A* Search Algorithm, Bipartiteness Testing and Topological Sorting
• Autor: Bruno Sačarić
• 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 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.

Sažetak (engleski)

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.

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