Grafer — adjacency-liste/matrix, BFS, DFS

Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer

💻 Grafer

En graf består af noder (vertices) og kanter (edges). Bruges til netværk, veje, sociale relationer.

Repræsentation:

• Adjacency-liste: {A: [B, C], B: [D], C: [D]} — effektiv for sparse grafer
• Adjacency-matrix: 2D-tabel med 0/1 — effektiv for dense grafer

BFS (Bredde-Først Søgning) — bruger kø:

```python

from collections import deque

def bfs(graf, start):

besøgt = set()

kø = deque([start])

while kø:

node = kø.popleft()

if node not in besøgt:

besøgt.add(node)

kø.extend(graf[node])

```

Findet korteste sti (uvægtet). O(V+E).

DFS (Dybde-Først Søgning) — bruger stak/rekursion:

```python

def dfs(graf, node, besøgt=set()):

besøgt.add(node)

for nabo in graf[node]:

if nabo not in besøgt:

dfs(graf, nabo, besøgt)

```

Findet stier, topologisk sortering. O(V+E).

Læringsmål

• Repræsentere grafer med adjacency-liste og -matrix
• Implementere BFS og DFS korrekt
• Anvende BFS til korteste-sti-problemer
• Forklare kompleksiteten O(V+E) for grafalgoritmer

Sådan kan du arbejde med emnet

• Tegn en graf med 5 noder og repræsentér den som både adjacency-liste og adjacency-matrix
• Udfør BFS og DFS på grafen fra et givet startpunkt og sammenlign rækkefølgen
• Giv et eksempel på en problemstilling hvor BFS er bedre end DFS

Træningsforslag

• Implementér en labyrint-løser med BFS
• Byg en social-netværk-simulator og find korteste vej mellem to brugere
• Løs LeetCode #200 (Number of Islands) med DFS/BFS