|
|
|
|
| LEADER |
03624na a2200241 4500 |
| 003 |
HR-ZaFER |
| 005 |
20160516012005.0 |
| 008 |
160221s2014 ci ||||| m||| 00| 0 hr d |
| 035 |
|
|
|a (HR-ZaFER)ferid1240
|
| 040 |
|
|
|a HR-ZaFER
|b hrv
|c HR-ZaFER
|e ppiak
|
| 100 |
1 |
|
|a Stupalo, Maja
|9 35749
|
| 245 |
|
|
|a Elementarni algoritmi nad grafovima :
|b završni rad /
|c Maja Stupalo ; [mentor Andrea Aglić-Aljinović].
|
| 246 |
1 |
|
|a Elementary Graph Algorithms
|i Naslov na engleskom:
|
| 260 |
|
|
|a Zagreb,
|b M. Stupalo,
|c 2014.
|
| 300 |
|
|
|a 33 str. ;
|c 30 cm +
|e CD-ROM
|
| 502 |
|
|
|b preddiplomski studij
|c Fakultet elektrotehnike i računarstva u Zagrebu
|g smjer: Telekomunikacije i informatika, šifra smjera: 42, datum predaje: 2014-06-13, datum završetka: 2014-07-14
|
| 520 |
3 |
|
|a Sažetak na hrvatskom: 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.
|
| 520 |
3 |
|
|a Sažetak na engleskom: 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.
|
| 653 |
|
1 |
|a BFS
|a DFS
|a najkraći put
|a BFS-stablo
|a DFS-stablo
|a DFS-šuma
|a graf
|
| 653 |
|
1 |
|a BFS
|a DFS
|a shortest path
|a BFS-tree
|a DFS-tree
|a DFS-forest
|a graph
|
| 700 |
1 |
|
|a Aglić-Aljinović, Andrea
|4 ths
|9 34937
|
| 942 |
|
|
|c Z
|2 udc
|
| 999 |
|
|
|c 44957
|d 44957
|