Elementarni algoritmi nad grafovima

undergraduate thesis

• Title (english): Elementary Graph Algorithms
• Author: Maja Stupalo
• Mentor: Andrea Aglić-Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Mirko Sužnjević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2014-07-14, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

U sklopu rada obrađena su dva elementarna algoritma nad grafovima pod nazivom pretraživanje prvo u širinu (BFS) i pretraživanje prvo u dubinu (DFS). Mnogi algoritmi nad grafovima organizirani su kao jednostavne razrada osnovnih algoritama za pretraživanje grafova. Obilazak ili pretraživanje grafa je sistematičan prolazak bridovima kako bi se obišli svi čvorovi. Algoritam BFS koristi strategiju traženja „šire“ u grafu i računa najmanju udaljenost od početnog čvora s do svakog dohvatljivog čvora te stvara BFS-stablo s korijenom s i svim dohvatljivim čvorovima. Algoritam DFS koristi strategiju traženja „dublje“ u grafu kad god je to moguće tj. za svaki susjedni čvor v čvora u algoritam DFS rekurzivno se poziva i provjerava susjede čvora v prije nego se vrati i provjeri preostale susjede čvora u. Uz opis algoritama dani su i njihovi pseudokodovi te je dokazano da BFS za zadani čvor pronalazi najkraću udaljenost do svakog čvora u njegovoj komponenti povezanosti te je prikazana primjena DFS algoritma za topološko sortiranje u usmjerenim acikličkim grafovima. Također je napravljena aplikacija pod nazivom „BFS“ koja računa najkraću udaljenost od zadanog čvora do svih ostalih čvorova.

Abstract (english)

This thesis gives presentation of two elementary graph algorithms called the breadth-first search (BFS) and the depth-first search (DFS). Many graph algorithms are organized as simple elaboration of the basic algorithms for searching graphs. Searching a graph means systematically following the edges of the graph so as to visit the vertices of the graph. The strategy followed by breadth-first search is to search “broader” in the graph. It computes the distance from s to each reachable vertex. It also produces a “breadth-first tree” with root s that contains all reachable vertices. The strategy followed by depth-first search is, as its name implies, to search “deeper” in the graph whenever possible and for each vertex v adjacent to vertex u recursively calls and checks the neighbors vertex v before returning and checking the remaining neighbor of vertex u. With algorithm descriptions, there are also their pseudocodes. It is proven that BFS finds shortest-path distance for a given vertex to each vertex in its component connections and there is also shown the use of DFS algorithm for topological sorting of directed acyclic graphs. For the purpose of this study, the application called "BFS" has been made. It calculates the shortest-path distance from a given vertex to all other vertex.

• Keywords: BFS; DFS; najkraći put; BFS-stablo; DFS-stablo; DFS-šuma; graf
• Keywords (english): BFS; DFS; shortest path; BFS-tree; DFS-tree; DFS-forest; graph
• Language: croatian
• URN:NBN: urn:nbn:hr:168:234127
• 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: 2018-02-06 07:24:04