Oversikt

Et spenntre for en sammenhengende, urettet graf G = (V, E) er et undertre som inneholder alle noder og er sammenhengende. Et minimum spenntre (MST) er spenntreet med lavest total kantvekt. Nyttig når du skal koble sammen alle noder til lavest mulig kostnad.

Prims algoritme

Prim bygger MST ved å starte fra en vilkårlig node og gradvis legge til den billigste kanten som forbinder en node i treet med en node utenfor treet. Algoritmen bruker en prioritetskø for å effektivt finne billigste kant. Kjøretid: O((|V| + |E|) * log(|V|)) med binær heap.

På H2022 ble det eksplisitt spurt om kjøretiden til Prim -- den er O((|V| + |E|) log(|V|)). På H2023 (Blindern-problemet) var oppgaven å finne det mest kostnadseffektive tunnelsystemet, noe som er et klassisk MST-problem. Oppgaven ba om å beskrive datastrukturene Prim bruker og forklare hvordan algoritmen fungerer.

Kruskals algoritme

Kruskal sorterer alle kanter etter vekt og legger til kanter en etter en, sa lenge de ikke danner en sykel. For å sjekke om en kant danner sykel brukes Union-Find (disjunkte mengder). Kjøretid: O(|E| * log(|E|)), dominert av sorteringssteget.

Blindern-problemet (H2023)

Et typisk MST-scenario: du har bygninger (noder) og mulige tunneler med kostnader (vektede kanter). Du skal finne den billigste maten å koble sammen alle bygninger. Grafen er urettet og vektet. Løsningen er Prim eller Kruskal. Etter at MST er bygget, er korteste sti mellom to noder i treet unik og kan finnes med BFS/DFS i O(|V|).

Egenskaper ved MST

Et MST har nøyaktig |V| - 1 kanter. Hvis alle kantvekter er unike, er MST unikt. Cut-egenskapen: for ethvert kutt i grafen, er den billigste kanten som krysser kuttet i MST. Sykel-egenskapen: for enhver sykel i grafen, er den dyreste kanten i sykelen ikke i MST.

Eksempel 1: Prims algoritme

Procedure Prim(G, w):
  s = velg en vilkarlig startnode
  key = ny ordbok (alle noder -> uendelig)
  inMST = ny mengde
  parent = ny ordbok
  key[s] = 0
  pq = ny min-heap med alle noder
  while pq er ikke tom:
    u = pq.removeMin()
    inMST.add(u)
    for each nabo v av u:
      if v ikke i inMST og w(u,v) < key[v]:
        key[v] = w(u,v)
        parent[v] = u
        pq.decreaseKey(v, key[v])
  return parent  // Foreldrearrayet definerer MST

Eksempel 2: Tunnelsystem (H2023-stil)

// Modeller problemet:
// Noder = bygninger
// Kanter = mulige tunneler med kostnad
// Graf: urettet, vektet

// Finn MST med Prim:
mst = Prim(G, w)
// MST gir billigste tunnelsystem

// Korteste sti i MST (som er et tre):
// Bruk BFS/DFS fra start til mal
// Kjoretid: O(|V|) fordi treet har |V|-1 kanter

Studieguide: Minimum spenntrær

Studieguide: Minimum spenntrær