Grafalgoritmer

Question 1

Når kan vi bruker dybde-først søk (DFS)?

Answer 1

For å traversere en graf, og for å finne spenntre for uvektede grafer.

DFS er også skjelettet til Hopcroft-Tarjan algoritmen.

Question 2

Når kan vi bruker bredde-først søk (BFS)?

Answer 2

For å traversere en graf, og for å finne spenntre for uvektede grafer.
Kan også brukes for å finne korteste stier i uvektet graf.

Question 3

Når kan vi bruker Topologisk sortering?

Answer 3

For rettede, asykliske grafer (DAG) til å beskriver avhengigheter mellom nodene.

Question 4

Når kan vi bruke Prims algoritme og hva er kjernen til algoritmen?

Answer 4

For å finne det minimale spenntre av en vektet graf.
- Grådig valg av noder

Benytter et tomt tree og en heap med oversikt over nodene og den billigste kantene.

Heap: for hver node u, Q.add(((u, None), D[u]))
- Alle noder u initialiseres med D[u] = uendelig,

Question 5

Når kan vi bruke Kruskals algortime og hva kjernen til algoritmen?

Answer 5

For å finne det minimale spenntre av en vektet graf.

• Grådig valg av kanter.
• Ofte raskest på tynne grafer, og om kantene er sortert etter vekt.

Bruker et tomt tree, en heap og clustere for oversikt over forskjellige “trær”.

Question 6

Når kan vi bruke Borûvkas algoritme og hva kjernen til algoritmen?

Answer 6

For å finne det minimale spenntre av en vektet graf.
- Grådig valg av kanter, parallelliserbar

Starter med å la hver node være sin egen komponent i et tre T, og deretter knytter sammen komponenter ved å finne den billigste kanten helt til det bare er en komponent igjen i T.

Question 7

Når kan vi bruke Djikstra og hva er kjernen til algoritmen?

Answer 7

Brukes for å finne korteste stier i vektede, rettede grafer, når kantene kun har positiv vekt.

Ideen er en BFS som tar høyde for kantenes vekt.
Vi bruker en prioritetskø/heap istedenfor en FIFO kø, som holder noder som elementer, og bruker en “estimert avstand” D til sammenligning.

Question 8

Når kan vi bruke Bellman-Ford og hva er kjernen til algoritmen?

Answer 8

Brukes for å finne korteste stier i vektede, rettede grafer hvor kanter har både positive og negativ vekt.
Eller for å finne negative sykler i grafer.

Oppdaterer estimert avstand D for alle noder |V| - 1 ganger.
- Hvis det finnes en node hvor estimert avstand fortsatt blir mindre etter dette, inneholder grafen en negativ sykel.

Question 9

Når kan vi bruke Hopcroft-Tarjan og hva er kjernen til algoritmen?

Answer 9

For å sjekke om en biconnected (2-sammenhengende) graf inneholder separasjonsnoder.

Bruker DFS til å lage et spenntre hvor vi:

• Indekserer rekkefølgen nodene blir besøkt
• Markerer discovery edges i treet (kanter som fører til nye noder).
• Markerer back edges (kanter som fører tilbake til allerede besøkte noder).

Deretter finner vi separasjonsnoder ut fra indeks og low-nummer til nodene.

Question 10

Hva er poenget med sterkt sammenhengende komponenter og hva er ideen for algoritmen?

Answer 10

Brukes for å finne de maksimale sterkt sammenhengende komponentene i en retted graf.

Vi bruker DFS, og ideen er at de sterkt sammenhengende komponentene i grafen forblir uendret hvis vi reverserer alle kantene.

Question 11

Hvordan kan vi implementere dybde-først søk (DFS)?

Answer 11

Benytter en stack og en besøkt-liste:
- Plasserer noder på stacken og plukker dem av når det ikke finnes en kant til en ubesøkt node.

• Alle noder listes i besøkt-listen når de blir palssert på stacken.

Question 12

Hvordan kan vi implementere bredde-først søk (BFS)?

Answer 12

Benytter en kø og en besøkt-liste:

• En første node blir plasser på køen, og satt som besøkt.
• Så blir den poppet av køen og så skriver vi alle naboene til denne noden inn på køen og setter som besøkt.
• Deretter poper vi neste node, og legger til de nabo nodene som ikke er besøkt inn på køen.
• Fortsetter til køen er tom.

Question 13

Hvordan kan vi implementere topologisk sortering?

Answer 13

Benytter en stack.
- Finner først alle noder med inngrad lik 0, og legger dem på stacken.

Så lenge stacken ikke er tom:

• pop en node av stacken.
• legg til noden i resultatliste.
• for hver nabo, sett inngraden til naboen lik inngrad - 1 (slik at graden reduseres for hver nabo som fjernes).
• om inngraden da er lik 0, legg til nabo på stacken.
• en teller i inkrementerer hver gang noe blir poppet fra S, om i > n avslutt og returner resultat.
• om i <= n og stacken er tom, da er det noder som er avhngig av hverandre, altså en sykel.

Question 14

Hvordan kan vi implementere Prims algoritme?

Answer 14

Benytter et tomt tree, og en heap med oversikt over nodene og den billigste kanten.

Lager treet ved å starte i en vilkårlig node, og så legge til den kanten knyttet til noden som har lavest verdi. Deretter velges kanten med lavest verdi som er knyttet til én av nodene som nå er en del av treet. Dette fortsetter til alle nodene er blitt en del av treet.

Question 15

Hvordan kan vi implementere Kruskals algoritme?

Answer 15

Bruker et tomt tree, en heap og clustere for oversikt over forskjellige “trær”.

Kruskals algoritme lager treet ved å finne de minste kantene i grafen en etter en, og lage en skog av trær. Deretter settes disse trærne gradvis sammen til ett tre, som blir det minimale spenntreet. Først finnes kanten i grafen med lavest vekt. Denne kanten legges til et tre. Deretter ser algoritmen etter den neste laveste kantvekten. Er ingen av nodene til denne kanten med i noe tre, så lages et nytt tre. Er én av nodene knyttet til et tre, så legges kanten til i det eksisterende treet. Er begge nodene knyttet til hver sitt tre settes de to trærne sammen. Er begge nodene knyttet til samme tre ignoreres kanten. Sånn fortsetter det til vi har ett tre.

Question 16

Hvordan kan vi implementere Borûvkas algoritme?

Answer 16

Benytter et tomt tre, og knytter sammen komponenter ved å finne den billigste kanten.

• Alle noder legges til i det tomme treet som sin egen komponent.
• Finn så billigste kant som går ut fra hver komponent (noen vil ha samme kant).
• Slå sammen komponentene etter disse kantene.
• Gjør det samme igjen helt til det kun er en komponent.

Question 17

Hvordan kan vi implementere Djikstra?

Answer 17

Ideen er en BFS som tar høyde for kantenes vekt.
Vi bruker en prioritetskø (heap) istedenfor en FIFO kø, som holder noder som elementer, og bruker en “estimert avstand” D til sammenligning.
- D inneholder den korteste veien vi har funnet så langt.
- input node s, får D[s] = 0
- Hver gang vi fjernet et element u fra prioritetskøen, ser vi på naboene v til u og ser om vi har funnet en kortere vei til v, og oppdaterer evt. D[v]

Vi starter med å intialisere D[u] = uendelig for hver node.
Vi poper en node v av heapen, sjekker om den nye veien til alle naboer av v er mindre enn den som er i D, om så, oppdaterer vi D[nabo] til nye vekten og oppdaterer verdien for naboen i heapen (slik at den får korrekt prioritet).

v = heap.pop()
for hver kant (v,t)
- om D[v] + w((v, t)) < D[t]
-- D[t] = D[v] + w(v,t)
-- oppdater verdi for t i heapen til D[t]

Question 18

Hvordan kan vi implementere Bellman-Ford?

Answer 18

Oppdaterer estimert avstand D for alle noder |V| - 1 ganger.

- Hvis det finnes en node hvor estimert avstand fortsatt blir mindre etter dette, inneholder grafen en negativ sykel.

Question 19

Hvordan kan vi implementere Hopcroft-Tarjan?

Answer 19

Bruker DFS til å lage et spenntre

• Indekserer rekkefølgen nodene blir besøkt
• Discovery edges i treet er kanter som fører til nye noder.
• Back edges er kanter som fører tilbake til allerede besøkte noder.

Deretter finner vi separasjonsnoder ut fra indeks og low-nummer til nodene.

…. trenger litt mer info på denne …

Question 20

Hvordan defineres en separasjonsnode ifht. Hopcroft-Tarjan algoritmen?

Answer 20

En node u er en separasjonsnode hvis

1. u er rot i T og har mer enn ett barn, eller
2. u ikke er roten, og har et barn v, slik at ingen etterkommere av v (inkludert v selv) har en back-edge til en forgjenger av u.

2 (formelt):
u er en sparasjonsnode hvis det finnes en kant u,v i T, slik at index(u) <= low(v)

Question 21

Hvordan defineres low-nummer ifht. Hopcroft-Tarjan algoritmen?

Answer 21

Low-nummer til en node er definert som indeksen til den noden med lavest indeks som kan nås ved å følge:

1. 0 eller flere kanter (discovery edges) (i spenntreet T av graf G) etterfulgt av
2. 0 eller 1 back-edge.

Question 22

Hvordan kan vi implementere en algoritme for å finne sterkt sammenhengende komponenter?

Answer 22

For å finne de maksimale sterkt sammenhengende komponentene i en retted graf kan vi bruke DFS.

Ideen er at de sterkt sammenhengende komponentene i grafen forblir uendret hvis vi reverserer alle kantene.

• Vi kjører to DFS, en på grafen og en på den reverserte grafen.
• I første DFS pusher vi noder på en stack når de er ferdig behandlet.
• I andre DFS begynner vi på toppen av stacken.

.. mer info ..