Algoritmi minimalnega vpetega drevesa v vsakdanjem življenju

[projekt]

Marija Gajič (Author), Mirjam Sepesy Maučec (Mentor), Gregor Donaj (Co-mentor)

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;primerjava algoritmov;časovna zahtevnost;

Data

Language:	Slovenian
Year of publishing:	2016
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[M. Gajić]
UDC:	621.39
COBISS:	20406294
Views:	2580
Downloads:	160
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Minimum spanning tree algorithms in everyday life
Secondary 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.
Secondary keywords:	minimum spanning tree;comparison of different algorithms;usage in everyday life;time complexity;
URN:	URN:SI:UM:
Type (COBISS):	Diploma project paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Telekomunikacije
Pages:	X, 54 f.
ID:	9155429