Neki algoritmi za razapinjuća stabla u grafu

undergraduate thesis

• Title (english): Some Algorithms for Spanning Trees in a Graph
• Author: Dominik Novosel
• Mentor: Mario Krnić (mentor)
• Committee member: Mario Krnić (predsjednik povjerenstva)
• Committee member: Tomislav Burić (član povjerenstva)
• Committee member: Lenka Mihoković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-06-27, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Rad istražuje različite algoritme pronalaska razapinjućih stabala u grafovima poput
Kruskalovog, Primovog te algoritma za minimalni produkt. Analizira se vremenska i
prostorna složenost svakog algoritma te se uspoređuju prednosti i nedostaci.
Također su prikazani primjeri stvarne implementacije u svakodnevnom životu. Kroz
teorijsku podlogu i praktične primjere rad daje sveobuhvatan pregled funkcioniranja i
korištenja ovih algoritama za rješavanje konkretnih problema.
Za svaki algoritam i obrađeno poglavlje prikazan je primjer pokretanja konkretnog
programa te dobiveni ispisi i grafovi.

Abstract (english)

This paper explores various algorithms for finding spanning trees in graphs, such as
Kruskal's algorithm, Prim's algorithm, and the minimum product algorithm. It analyzes the
time and space complexity of each algorithm, comparing their advantages and
disadvantages.
Additionally, examples of real-world implementation in everyday life are presented.
Through theoretical background and practical examples, the paper provides a
comprehensive overview of the functioning and usage of these algorithms for solving
specific problems.
For each algorithm and discussed chapter, an example of running a specific program is
provided, along with the resulting outputs and graphs.

• Keywords: razapinjuće stablo; graf; Kruskalov algoritam; Primov algoritam; minimalni produkt; svakodnevne primjene
• Keywords (english): spanning tree; graph; Kruskal's algorithm; Prim's algorithm; minimum product; everyday applications
• Language: croatian
• URN:NBN: urn:nbn:hr:168:035261
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 21:41:32