Föreläsning 4 Flashcards
(9 cards)
1
Q
Vad är Djikstras algorithm?
A
En algorithm för att hitta optimala trädet genom en viktad graf från en viss nod n
2
Q
Vad kallas mängden noder och kanter för vanligtvis? Det är två bokstäver
A
n för noderna = |V|
m för kanterna = |E|
3
Q
Fungerar Djikstras algorithm för negativa vikter?
A
Nej, det krävs positiva vikter
4
Q
Vad är tidskomplexiteten för Djikstras algorithm?
A
O(m log n)
m = antal kanter
n = antal noder
5
Q
Vad är en union-find struktur?
A
En datastruktur optimerad för två operationer, union och find.
6
Q
Hur fungerar kruskals algoritm?
A
Det är en algorithm för bygga ett MST
- Vi sorterar alla kanter baserat på vikt
- Vi bygger iterativt en skog genom att ta den billigaste kanten
- Inför varje ny kant kollar vi om en cykel bildas med find
- Vi avslutar när alla noder är kopplade
7
Q
Hur fungerar Prims algoritm?
A
- Välj en godtycklig nod och placera i trädet
- Välj den billigaste kant som förbinder noden med en ny nod utanför trädet
- Lägg till denna nod och kant i trädet
- Fortsätt så tills alla noder är i trädet
8
Q
Vad är tidskomplexiteten för Prims algoritm?
A
O(m log n)
9
Q
Vad är tidskomplexiteten för Kruskals algoritm
A
O(m log n)
