Oversikt

En graf G = (V, E) bestar av en mengde noder V og en mengde kanter E. Grafen kan vaere rettet (kanter har retning) eller urettet (kanter gar begge veier). Grafer kan representeres som nabolister (et array av lister, en per node) eller som en nabomatrise (en V x V matrise). Nabolister er mest minneeffektivt for sparse grafer (fa kanter), mens nabomatriser gir O(1)-oppslag for a sjekke om en kant finnes.

BFS (bredde-forst-sok)

BFS utforsker grafen nivavis: forst alle naboer pa avstand 1, deretter avstand 2, osv. Algoritmen bruker en ko (FIFO) og en mengde med besoktenoder. BFS finner korteste sti i uvektede grafer (antall kanter). Kjoretid: O(|V| + |E|). Pa eksamen (H2024) ble BFS brukt til a finne venner innen k ledd -- en typisk anvendelse der du begrenser BFS til en gitt dybde.

DFS (dybde-forst-sok)

DFS utforsker grafen ved a ga sa dypt som mulig for den snur. Algoritmen bruker en stakk (eksplisitt eller via rekursjon) og en mengde besoktenoder. DFS er grunnlaget for mange grafalgoritmer: syklusdeteksjon, topologisk sortering, og sterkt sammenhengende komponenter. Kjoretid: O(|V| + |E|).

Topologisk sortering

En topologisk sortering av en rettet asyklisk graf (DAG) er en lineaer ordning av nodene slik at for hver kant (u, v) kommer u for v. Algoritmen bruker DFS eller en ko-basert tilnaerming (Kahns algoritme). Topologisk sortering finnes kun for DAG-er. Pa eksamen (H2022) ble det spurt om kjoretiden til TopSort -- den er O(|V| + |E|).

Syklusdeteksjon

For a oppdage sykler i en rettet graf bruker vi DFS med tre farger: hvit (ubesokt), gra (pabesokt, pa rekursjonsstakken), svart (ferdig). Hvis vi under DFS treffer en gra node, har vi funnet en sykel. Pa H2023 (Dependency hell) ble det eksplisitt bedt om a sjekke om en avhengighetsgraf inneholder sykliske avhengigheter.

Grafegenskaper

Du bor kjenne til sentrale begreper: grad (antall kanter til en node), inngrad/utgrad (i rettede grafer), sammenhengende (det finnes sti mellom alle par av noder), tre (sammenhengende asyklisk graf), isomorfi (to grafer har samme struktur). Pa H2022 ble det gitt to grafer og spurt om egenskaper som antall kanter, grader, og om grafene er isomorfe.

Eksempel 1: BFS med dybdegrense (H2024-stil)

Procedure BFS_k(G, s, k):
  queue = ny ko
  visited = ny mengde
  queue.enqueue((s, 0))
  visited.add(s)
  result = []
  while queue er ikke tom:
    (v, depth) = queue.dequeue()
    if depth > k: break
    result.append(v)
    for each nabo u av v i G:
      if u ikke i visited:
        visited.add(u)
        queue.enqueue((u, depth + 1))
  return result

Eksempel 2: Syklusdeteksjon med DFS (H2023-stil)

Procedure HasCycle(G):
  color = ny ordbok (alle noder -> WHITE)
  for each node v i G:
    if color[v] == WHITE:
      if DFS_Visit(G, v, color):
        return true
  return false

Procedure DFS_Visit(G, v, color):
  color[v] = GRAY
  for each nabo u av v:
    if color[u] == GRAY:
      return true  // Sykel funnet!
    if color[u] == WHITE:
      if DFS_Visit(G, u, color):
        return true
  color[v] = BLACK
  return false

Studieguide: Grafalgoritmer

Studieguide: Grafalgoritmer