SLO | ENG

Bigger font | Smaller font

Show document

Title:Algoritmi minimalnega vpetega drevesa v vsakdanjem življenju
Authors:Gajić, Marija (Author)
Sepesy Maučec, Mirjam (Mentor) More about this mentor... New window
Donaj, Gregor (Co-mentor)
Files:.pdf UN_Gajic_Marija_2016.pdf (1,34 MB)
 
Language:Slovenian
Work type:Diploma project paper (mb13)
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract: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.
Keywords:minimalno vpeto drevo, uporaba v vsakdanjem življenju, primerjava algoritmov, časovna zahtevnost
Year of publishing:2016
Publisher:[M. Gajić]
Source:Maribor
UDC:621.39
COBISS_ID:20406294 Link is opened in a new window
Views:340
Downloads:31
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:KTFMB - FERI
:
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:English
Title:Minimum spanning tree algorithms in everyday life
Abstract: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.
Keywords:minimum spanning tree, comparison of different algorithms, usage in everyday life, time complexity


Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica