Noder med vekter (weighted-nodes).
Mengder representeres som trær vha. foreldrepekere v.p Roten er en representant for mengden, lat som det er et slags mengdeobjekt. Self-loop i rot (fjerner spesialtilfeller i FIND-SET).
For union by rank-heuristikk: Rang er øvre grense for nodehøyde
function make_set(x)
x.p = x
x.rank = 0
end
function union(x, y) #Merk at union allerede er definert i julia
link(find_set(x), find_set(y))
end
function link(x, y)
if x.rank > y.rank
y.p = x
else
x.p = y
if x.rank == y.rank
y.rank = y.rank + 1
end
end
end
function find_set(x)
if x!= x.p
x.p = find_set(x.p)
end
end
$m$ operasjoner: $O(m \times \alpha(n))$. (med komprimering og union by rank)
Hva er et spenn tre?
Vi innfører nå vekter på kantene. Disse omtales også som lengder eller kostnader.
Input: En urettet graf $G = (V, E)$ og en vekt-funksjon $w: E \rightarrow R$
Output: En asyklisk delmengde $T ⊆ E$ som kobler sammen nodene i $V$ og minimerer vektsummen $w(T) = \sum_{(u,v) ∈ T} w(u,v)$.
function generic_mst(G, w)
A = []
while A does not form a spanning tree,
find an edge (u, v) that is safe for A
push!(A, (u, v))
end
return A
end
Lette kanter: den som har minimal kant kost fra en node til en annen
Hva om det går i sikk-sakk, og har flere? Holder argumentet fortsatt?
Kruskal: En kant med minimal vekt balnt de gjenværende er trygg så lenge den ikke danner sykler.
Prim: Bygger et tre gradvis; en lett kant over snittet rundt treet er alltid trygg.
Boûvka: En slags blanding. Kobler hvert tre til det nærmeste av det andre.
Construction A. Perform the following step as many times as possible: Among the edges of G not yet chosen, choose the shortest edge which does not form any loops with those edges already chosen. Clearly the set of edges eventually chosen must form a spanning tree of G, and infact it forms the shortest spanning tree.
Til å begynne med er hver node en komponent i en partiell løsning
Komponenter: Disjunkte nodemengder. Starter med v.p = v
Hvis vi vil legge til en kant mellom to komponenter, må vi passe på at kanten ikke danner en syklus og deretter oppdatere v.p for den ene komponenten.
Tilsammen kan v.p-pekerene våre utgjøre MST-et vårt…
Ofte mer effektivt om de ikke gjør det!
function mst_kruskal(G, w)
A = []
for each vertex v in G.V
make_set(v)
end
sort G.E by w # Sorter etter vekting
for each edge (u,v) in G.E
if find_set(u) != find_set(v)
# en trygg kant
push!(A, (u, v))
union(u, v) #Egen definert union funksjon, se lenger oppe
end
end
return A
| Operasjon | Antall | Kjøretid |
|---|---|---|
| MAKE-SET | $V$ | $O(1)$ |
| Sortering | $1$ | $O(E log(E))$ |
| FIND-SET | $O(E)$ | $O(log(V))$ |
| UNION | $O(E)$ | $O(log(V))$ |
The two fundamental construction principles(P1 and P2) for shortest connection networks can be stated as follows: Principle 1: Any isolated terminal can be connected to a nearest neighbor Principle 2: Any isolated fragment can be connected to nearest neighbor by a shortest available link
function mst_prim(G, w, r)
for each u in G.V
u.key = Inf
u.pi = nothing
end
r.key = 0
Q = G.V
while Q != empty
u = extract_min(Q)
for each v in G.adj(u)
if v in Q and w(u,v) < v.key
v.pi = u
v.key = w(u, v)
end
end
end
| Operasjon | Antall | Kjøretid |
|---|---|---|
| BUILD-MIN-HEAP | $1$ | $O(V)$ |
| EXTRACT-MIN | $V$ | $O(log(V))$ |
| DECREASE-KEY | $E$ | $O(log(V))$ |
Dette gjelder om vi bruker en binærhaug
Kan forbedres med en Fib.haug (Fib heap). Blir da $O(E + V log(V))$.