[projekt]
Marija Gajič (Avtor), Mirjam Sepesy Maučec (Mentor), Gregor Donaj (Komentor)

Povzetek

V zaključni projketni nalogi je opisano minimalno vpeto drevo in načini iskanja minimalnega vpetega drevesa v grafu. Predstavljeni in analizirani so trije algoritmi in sicer Primov, Kruskalov in Boruvkin algoritem. Podrobneje so predstavljene tudi programske implementacije teh treh algoritmov. V nadaljevanju je predstavljena praktična uporaba minimalnega vpetega drevesa v vsakdanjem življenju ter opis enega konkretnega primera – postavljanja vodovodnega omrežja. Za izbiro optimalnega algoritma so java programske implementacije algoritmov testirane na 408 testnih datotekah z grafi. Analizirana je odvisnost časovne zahtevnosti algoritma od števila povezav v grafu. Hkrati je predstavljena še primerjava časovne učinkovitosti vseh treh analiziranih algoritmov.

Ključne besede

minimalno vpeto drevo;primerjava algoritmov;časovna zahtevnost;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik: [M. Gajić]
UDK: 621.39
COBISS: 20406294 Povezava se bo odprla v novem oknu
Št. ogledov: 2580
Št. prenosov: 160
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Minimum spanning tree algorithms in everyday life
Sekundarni povzetek: The final project work describes the minimum spanning tree and a way to find the minimum spanning tree in the graph. Three different algorithms are presented and analyzed: Prim’s, Kruskal’s and Boruvka’s. Software implementation of each algorithm is also discussed. Furthermore, usage of the minimum spanning tree in everyday life is addressed through description of one practical problem regarding a water supply network and its solution. For making the best choice between the algorithms, three Java software implementations are tested on 408 graphs. Dependency of the time efficiency given the overall number of edges in the graph with the constant number of vertices is presented, together with comparison of time efficiencies for all three algorithms.
Sekundarne ključne besede: minimum spanning tree;comparison of different algorithms;usage in everyday life;time complexity;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo diplomskega projekta/projektno delo
Komentar na gradivo: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Telekomunikacije
Strani: X, 54 f.
ID: 9155429