Algoritmi za traženje minimalnog razapinjućeg stabla u grafu

završni rad

• Naslov (engleski): Algorithms for Search of Minimal Spanning Tree
• Autor: Šimun Smolčec
• Mentor: Siniša Srbljić (mentor)
• Član povjerenstva: Siniša Srbljić (predsjednik povjerenstva)
• Član povjerenstva: Adrian Satja Kurdija (član povjerenstva)
• Član povjerenstva: Iva Jurković (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2020-08-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu objašnjen je problem pronalaska minimalnog razapinjućeg stabla. Također su i objašnjena tri algoritma: Boruvkin, Primov i Kruskalov. Sva tri algoritma izvedena su u programskom jeziku Pyhton. Napravljen je generator primjera koji pazi da generirani grafovi budu povezani kako bi ih mogli obraditi pomoću algoritama razapinjućeg stabla. Sva tri prethodno navedena algoritma testirana su na grafovima različite veličine i gustoće. Na dobivenim rezultatima analizirane su njihove prednosti i mane. Algoritmi su također testirani i na jednom problemu iz stvarnog života, a to je kako povezati muzeje u užem centru Zagreba optičkom mrežom najmanje cijene.

Sažetak (engleski)

In this paper, the problem of finding minimum spanning tree is explained. Three algorithms that were explained were Boruvka’s, Prim’s and Kruskal’s. All three algorithms were programmed in Python. An example generator has been created so that the generated graphs were all connected graphs so that the algorithms could process them to find minimum spanning tree. All three previously mentioned algorithms were tested on graphs of different size and density. The results were analysed to find the advantages and disadvantages of each algorithm. In the end, a real-life example of connecting Museums in the city of Zagreb with optical network of minimal cost was tested with all three algorithms.

• Ključne riječi: povezani graf; minimalno razapinjuće stablo; algoritmi
• Ključne riječi (engleski): connected graph; minimum spanning tree; algorithms
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:202360
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 13:48:43