Neki algoritmi za razapinjuća stabla u grafu

završni rad

• Naslov (engleski): Some Algorithms for Spanning Trees in a Graph
• Autor: Dominik Novosel
• Mentor: Mario Krnić (mentor)
• Član povjerenstva: Mario Krnić (predsjednik povjerenstva)
• Član povjerenstva: Tomislav Burić (član povjerenstva)
• Član povjerenstva: Lenka Mihoković (č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: 2024-06-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: razapinjuće stablo; graf; Kruskalov algoritam; Primov algoritam; minimalni produkt; svakodnevne primjene
• Ključne riječi (engleski): spanning tree; graph; Kruskal's algorithm; Prim's algorithm; minimum product; everyday applications
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:035261
• 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: 2024-10-12 21:41:32