Grafen uitgelegd: BFS, DFS, Dijkstra en topologisch sorteren

Een graaf (graph) is een verzameling knopen (vertices) die met kanten (edges) verbonden zijn. Dat klinkt abstract, maar bijna alles is een graaf: wegen tussen steden, vrienden op een sociaal netwerk, links tussen webpagina's, vakken met hun voorkennis, of pakketten die van elkaar afhangen.

Wie grafen beheerst, kan een hele klasse problemen oplossen met een handvol algoritmen. Op het tentamen traceer je BFS, DFS en Dijkstra met de hand. In sollicitaties vermomt een graafprobleem zich vaak als iets anders ("hoeveel eilanden staan er in dit raster?"). En in de praktijk draaien routeplanners, build-tools en package managers op precies deze algoritmen.

Begrippen

• Ongericht (undirected): een kant A–B kun je in beide richtingen volgen (vriendschap).
• Gericht (directed): een kant A → B heeft één richting (volgen op sociale media, "A is voorkennis voor B").
• Gewogen (weighted): elke kant heeft een getal, bijvoorbeeld een afstand of een reistijd.
• Buren (neighbours): de knopen die met één kant bereikbaar zijn.
• Graad (degree): het aantal kanten aan een knoop. Bij een gerichte graaf onderscheid je ingangsgraad (in-degree) en uitgangsgraad (out-degree).
• V is het aantal knopen, E het aantal kanten.

Knopen noteren we als hoofdletters. Buren bekijk je altijd in alfabetische volgorde; anders zijn er meerdere goede antwoorden op een traceervraag.

We gebruiken deze ongerichte graaf met zes knopen en zeven kanten:

A --- B --- C
|     |     |
D --- E --- F

Representatie: lijst of matrix

Een adjacency list (buurlijst) slaat per knoop de lijst van buren op. Een adjacency matrix (buurmatrix) is een V × V-tabel met een 1 als er een kant is.

De meeste echte grafen zijn ijl (sparse): een wegennet heeft miljoenen kruispunten, maar elk kruispunt maar een paar wegen. Daarom is de adjacency list de standaard. Bij een ongerichte graaf staat elke kant twee keer in de lijst (en is de matrix symmetrisch).

Breedte-eerst zoeken (BFS)

Breedte-eerst zoeken (breadth-first search) verkent de graaf in lagen: eerst de startknoop, dan alle buren, dan de buren daarvan. Het gebruikt een wachtrij. Een knoop telt als bezocht zodra hij in de wachtrij komt, zodat hij er nooit twee keer in staat.

BFS vanaf A:

Bezoekvolgorde: A, B, D, C, E, F. In een ongewogen graaf vindt BFS de kortste route (in aantal kanten): F ligt op afstand 3 van A, en BFS bereikt hem pas in de derde laag.

Diepte-eerst zoeken (DFS)

Diepte-eerst zoeken (depth-first search) gaat zo diep mogelijk één kant op, en keert pas terug als er geen onbezochte buur meer is. Recursief is dat het natuurlijkst; de recursie werkt als een stapel.

DFS vanaf A:

Daarna heeft D geen onbezochte buren meer; de recursie keert helemaal terug naar A, waar D nu al bezocht is. Bezoekvolgorde: A, B, C, F, E, D.

Zelfde graaf, zelfde start, toch een andere volgorde dan BFS. DFS gebruik je voor het vinden van cycli, samenhangende componenten en doolhoven.

from collections import deque

graaf = {
    "A": ["B", "D"], "B": ["A", "C", "E"], "C": ["B", "F"],
    "D": ["A", "E"], "E": ["B", "D", "F"], "F": ["C", "E"],
}


def bfs(graaf, start):
    bezocht = {start}
    wachtrij = deque([start])
    volgorde = []
    while wachtrij:
        u = wachtrij.popleft()
        volgorde.append(u)
        for v in sorted(graaf[u]):  # buren alfabetisch
            if v not in bezocht:
                bezocht.add(v)  # bezocht zodra hij in de wachtrij komt
                wachtrij.append(v)
    return volgorde


def dfs(graaf, u, bezocht=None, volgorde=None):
    if bezocht is None:
        bezocht, volgorde = set(), []
    bezocht.add(u)
    volgorde.append(u)
    for v in sorted(graaf[u]):  # buren alfabetisch
        if v not in bezocht:
            dfs(graaf, v, bezocht, volgorde)
    return volgorde


print(bfs(graaf, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']
print(dfs(graaf, "A"))  # ['A', 'B', 'C', 'F', 'E', 'D']

import java.util.*;

static List<String> bfs(Map<String, List<String>> graaf, String start) {
    Set<String> bezocht = new HashSet<>(List.of(start));
    Deque<String> wachtrij = new ArrayDeque<>(List.of(start));
    List<String> volgorde = new ArrayList<>();
    while (!wachtrij.isEmpty()) {
        String u = wachtrij.poll();
        volgorde.add(u);
        List<String> buren = new ArrayList<>(graaf.get(u));
        Collections.sort(buren); // buren alfabetisch
        for (String v : buren) {
            if (bezocht.add(v)) { // bezocht zodra hij in de wachtrij komt
                wachtrij.add(v);
            }
        }
    }
    return volgorde;
}

static List<String> dfs(Map<String, List<String>> graaf, String start) {
    List<String> volgorde = new ArrayList<>();
    dfsBezoek(graaf, start, new HashSet<>(), volgorde);
    return volgorde;
}

private static void dfsBezoek(Map<String, List<String>> graaf, String u,
                              Set<String> bezocht, List<String> volgorde) {
    bezocht.add(u);
    volgorde.add(u);
    List<String> buren = new ArrayList<>(graaf.get(u));
    Collections.sort(buren); // buren alfabetisch
    for (String v : buren) {
        if (!bezocht.contains(v)) dfsBezoek(graaf, v, bezocht, volgorde);
    }
}

Kortste paden: Dijkstra

In een gewogen graaf is de route met de minste kanten niet altijd de kortste. Het algoritme van Dijkstra vindt de kortste afstand van één startknoop naar alle andere knopen, zolang alle gewichten niet-negatief zijn.

Het idee: houd voor elke knoop de beste bekende afstand bij (start op 0, de rest op ∞). Kies steeds de nog niet afgeronde knoop met de kleinste afstand; die afstand is definitief. Bekijk dan zijn buren: is de route via deze knoop korter, verlaag dan hun afstand (relaxatie).

Dezelfde graaf, nu met gewichten:

A --4-- B --3-- C
|       |       |
1       1       2
|       |       |
D --2-- E --5-- F

Dijkstra vanaf A (de tabel toont de afstanden na het verwerken van de gekozen knoop):

Twee momenten om op te letten:

• In stap 3 levert de route A → D → E → B afstand 3 + 1 = 4 op. Dat is niet kleiner dan de huidige 4, dus B verandert niet.
• In stap 5 levert A → B → C → F afstand 7 + 2 = 9 op, langer dan de 8 via E. F blijft 8.

Antwoord (alfabetisch): A = 0, B = 4, C = 7, D = 1, E = 3, F = 8.

Met negatieve gewichten werkt Dijkstra niet, omdat een "definitieve" afstand later toch nog korter kan worden. Daarvoor gebruik je Bellman-Ford.

import heapq

gewogen = {
    "A": {"B": 4, "D": 1}, "B": {"A": 4, "C": 3, "E": 1},
    "C": {"B": 3, "F": 2}, "D": {"A": 1, "E": 2},
    "E": {"B": 1, "D": 2, "F": 5}, "F": {"C": 2, "E": 5},
}


def dijkstra(graaf, start):
    afstand = {v: float("inf") for v in graaf}
    afstand[start] = 0
    klaar = set()
    heap = [(0, start)]  # (afstand, knoop)
    while heap:
        d, u = heapq.heappop(heap)  # knoop met kleinste afstand
        if u in klaar:
            continue  # verouderde invoer in de heap
        klaar.add(u)
        for v, gewicht in sorted(graaf[u].items()):
            if d + gewicht < afstand[v]:  # relaxatie
                afstand[v] = d + gewicht
                heapq.heappush(heap, (afstand[v], v))
    return dict(sorted(afstand.items()))


print(dijkstra(gewogen, "A"))
# {'A': 0, 'B': 4, 'C': 7, 'D': 1, 'E': 3, 'F': 8}

import java.util.*;

record Item(int afstand, String knoop) {}

static Map<String, Integer> dijkstra(Map<String, Map<String, Integer>> graaf, String start) {
    Map<String, Integer> afstand = new TreeMap<>(); // TreeMap: alfabetische volgorde
    for (String v : graaf.keySet()) afstand.put(v, Integer.MAX_VALUE);
    afstand.put(start, 0);
    Set<String> klaar = new HashSet<>();
    PriorityQueue<Item> heap = new PriorityQueue<>(
            Comparator.comparingInt(Item::afstand).thenComparing(Item::knoop));
    heap.add(new Item(0, start));
    while (!heap.isEmpty()) {
        Item it = heap.poll(); // knoop met kleinste afstand
        if (!klaar.add(it.knoop())) continue; // verouderde invoer in de heap
        for (Map.Entry<String, Integer> kant : new TreeMap<>(graaf.get(it.knoop())).entrySet()) {
            int nieuw = it.afstand() + kant.getValue();
            if (nieuw < afstand.get(kant.getKey())) { // relaxatie
                afstand.put(kant.getKey(), nieuw);
                heap.add(new Item(nieuw, kant.getKey()));
            }
        }
    }
    return afstand;
}

Topologisch sorteren met Kahn

Een topologische sortering (topological sort) van een gerichte graaf zonder cycli (DAG, directed acyclic graph) is een volgorde waarin elke kant u → v van links naar rechts wijst: u komt vóór v. Denk aan vakken met voorkennis of build-stappen die van elkaar afhangen.

Het algoritme van Kahn werkt met ingangsgraden:

1. Tel voor elke knoop de ingangsgraad (aantal inkomende kanten).
2. Kies een knoop met ingangsgraad 0; zijn er meerdere, neem de alfabetisch kleinste.
3. Zet hem in het resultaat en verlaag de ingangsgraad van elk van zijn opvolgers met 1.
4. Herhaal tot er geen knopen met ingangsgraad 0 meer zijn.

Voorbeeld met zes vakken en deze voorkennis-kanten:

C → A    C → D    B → D    A → E    D → E    E → F

Ingangsgraden bij de start: A = 1, B = 0, C = 0, D = 2, E = 2, F = 1.

Topologische volgorde: B, C, A, D, E, F. Bevat de graaf een cyclus, dan komen de knopen in die cyclus nooit op ingangsgraad 0 en is het resultaat korter dan V. Zo detecteert Kahn meteen cycli.

import heapq

voorkennis = {
    "A": ["E"], "B": ["D"], "C": ["A", "D"],
    "D": ["E"], "E": ["F"], "F": [],
}


def kahn(graaf):
    ingang = {v: 0 for v in graaf}
    for u in graaf:
        for v in graaf[u]:
            ingang[v] += 1
    klaar = [v for v in graaf if ingang[v] == 0]
    heapq.heapify(klaar)  # min-heap: alfabetisch kleinste eerst
    volgorde = []
    while klaar:
        u = heapq.heappop(klaar)
        volgorde.append(u)
        for v in graaf[u]:
            ingang[v] -= 1
            if ingang[v] == 0:
                heapq.heappush(klaar, v)
    if len(volgorde) < len(graaf):
        raise ValueError("graaf bevat een cyclus")
    return volgorde


print(kahn(voorkennis))  # ['B', 'C', 'A', 'D', 'E', 'F']

import java.util.*;

static List<String> kahn(Map<String, List<String>> graaf) {
    Map<String, Integer> ingang = new HashMap<>();
    for (String v : graaf.keySet()) ingang.put(v, 0);
    for (List<String> opvolgers : graaf.values()) {
        for (String v : opvolgers) ingang.merge(v, 1, Integer::sum);
    }
    PriorityQueue<String> klaar = new PriorityQueue<>(); // alfabetisch kleinste eerst
    for (String v : graaf.keySet()) if (ingang.get(v) == 0) klaar.add(v);
    List<String> volgorde = new ArrayList<>();
    while (!klaar.isEmpty()) {
        String u = klaar.poll();
        volgorde.add(u);
        for (String v : graaf.get(u)) {
            if (ingang.merge(v, -1, Integer::sum) == 0) klaar.add(v);
        }
    }
    if (volgorde.size() < graaf.size()) throw new IllegalStateException("graaf bevat een cyclus");
    return volgorde;
}

Complexiteit

BFS en DFS bekijken elke knoop één keer en elke kant (bij een ongerichte graaf) twee keer, vandaar V + E. Dijkstra doet daarbovenop heap-operaties van O(log V); zie heaps. Kahn met de alfabetische keuze via een heap kost O(V log V + E); zonder die eis volstaat een gewone wachtrij en is het O(V + E). Meer over deze notatie lees je bij complexiteit.

Veelgemaakte fouten op het tentamen

1. Buren niet alfabetisch bekijken. Bij B zijn de buren A, C, E, in die volgorde. Neem je ze in de volgorde waarin de kanten in de opgave staan, dan krijg je een ander antwoord.
2. BFS: een knoop pas markeren als hij uit de wachtrij komt. Dan kan hij er twee keer in komen. Markeer hem als bezocht zodra hij erin gaat.
3. DFS als BFS uitvoeren. Bij DFS ga je na B meteen door naar de eerste onbezochte buur van B (C), niet eerst terug naar de andere buren van A.
4. Dijkstra: een afgeronde knoop opnieuw aanpassen of bij gelijke afstand overschrijven. Een afstand verandert alleen als de nieuwe route strikt korter is.
5. Kahn: de ingangsgraden niet bijwerken. Verlaag na elke keuze de ingangsgraad van alle opvolgers; pas dan zie je welke knopen nieuw beschikbaar zijn.

Samenvatting

• Een graaf bestaat uit knopen en kanten, gericht of ongericht, gewogen of niet; meestal sla je hem op als adjacency list (O(V + E) geheugen).
• BFS gebruikt een wachtrij en verkent laag voor laag; DFS gaat recursief zo diep mogelijk. Beide O(V + E), buren altijd alfabetisch.
• Dijkstra kiest steeds de knoop met de kleinste voorlopige afstand en werkt alleen met niet-negatieve gewichten: O((V + E) log V) met een heap.
• Kahn sorteert een DAG topologisch door steeds een knoop met ingangsgraad 0 te kiezen (bij ons de alfabetisch kleinste) en detecteert zo ook cycli.