Grafalgoritmer: BFS, DFS, topologisk ordning

En graf är noder och kanter. AI-grafens kunskapskarta är en graf: 509 noder och 850 förkunskapsrelationer.

Två sätt att gå igenom den:

Skillnaden är en enda rad: tar du från början av samlingen (kö) blir det BFS, tar du från slutet (stack) blir det DFS.

Topologisk ordning är den viktigaste för den här plattformen: en ordning där varje nod kommer efter alla sina förkunskaper. Det är precis vad en lärväg är.

Den finns om och endast om grafen är acyklisk. En cykel — A kräver B som kräver A — betyder att ingen ordning är möjlig, och därför kontrollerar graph_invariants.py just det.

Kahns algoritm för topologisk ordning:

1. Räkna hur många inkommande kanter varje nod har (ingrad).
2. Lägg alla noder med ingrad 0 i en kö.
3. Plocka en nod, lägg den i resultatet, minska ingraden för dess grannar.
4. Hamnar en granne på 0, lägg den i kön.
5. Upprepa.

Om resultatet innehåller färre noder än grafen finns en cykel — de noder som saknas ingår i den. Det gör Kahns algoritm till både sorterare och cykeldetektor i ett, vilket är varför den används i tools.graph_invariants.

Komplexitet: $O(V + E)$ för alla tre algoritmerna.

Fyra tillämpningar i den här plattformen:

Den sista är grafinvarianten: varje publicerad nod måste nås från minst ett mål.

Viktade grafer kräver mer. Har kanterna kostnad — till exempel uppskattad tid per nod — ger BFS inte längre kortaste vägen. Då behövs Dijkstra (icke-negativa vikter, med prioritetskö) eller, i en DAG, topologisk ordning följd av en enda genomgång, vilket är både enklare och snabbare.

Det sista är värt att komma ihåg: i en DAG är kortaste och längsta vägen lätta — bara relaxera kanterna i topologisk ordning. I en allmän graf är längsta vägen NP-svårt.

from collections import deque, defaultdict

def bfs(graf, start):
    """Besökta noder i ordning, samt avstånd från start."""
    besokt, avstand, ko = [start], {start: 0}, deque([start])
    while ko:
        n = ko.popleft()                    # popleft → BFS
        for g in graf.get(n, []):
            if g not in avstand:
                avstand[g] = avstand[n] + 1
                besokt.append(g); ko.append(g)
    return besokt, avstand

def dfs(graf, start):
    besokt, stack = [], [start]
    sedda = {start}
    while stack:
        n = stack.pop()                     # pop → DFS. Enda skillnaden.
        besokt.append(n)
        for g in reversed(graf.get(n, [])):
            if g not in sedda:
                sedda.add(g); stack.append(g)
    return besokt

def topologisk(graf):
    """Kahns algoritm. Returnerar (ordning, cykliska_noder)."""
    noder = set(graf) | {g for gs in graf.values() for g in gs}
    ingrad = dict.fromkeys(noder, 0)
    for n in graf:
        for g in graf[n]:
            ingrad[g] += 1
    ko = deque(sorted(n for n in noder if ingrad[n] == 0))
    ordning = []
    while ko:
        n = ko.popleft()
        ordning.append(n)
        for g in graf.get(n, []):
            ingrad[g] -= 1
            if ingrad[g] == 0:
                ko.append(g)
    cykliska = sorted(noder - set(ordning))
    return ordning, cykliska

# En liten lärväg: kant a → b betyder "a är förkunskap till b"
kurs = {
    "aritmetik": ["algebra"],
    "algebra": ["ekvationer", "funktioner"],
    "ekvationer": ["derivator"],
    "funktioner": ["derivator"],
    "derivator": ["gradientnedstigning"],
}
ordning, cykler = topologisk(kurs)
print(ordning)
# ['aritmetik', 'algebra', 'ekvationer', 'funktioner', 'derivator', 'gradientnedstigning']
print("cykler:", cykler or "inga")

_, avstand = bfs(kurs, "aritmetik")
print(avstand)   # {'aritmetik': 0, 'algebra': 1, 'ekvationer': 2, 'funktioner': 2, ...}

# En cykel upptäcks av att ordningen blir för kort
trasig = {"a": ["b"], "b": ["c"], "c": ["a"]}
ordning, cykler = topologisk(trasig)
print(ordning, cykler)          # [] ['a', 'b', 'c']

# Längsta vägen i en DAG — enkelt, tack vare topologisk ordning
def langsta_vag(graf, tid):
    ordning, _ = topologisk(graf)
    langst = {n: tid.get(n, 0) for n in ordning}
    for n in ordning:
        for g in graf.get(n, []):
            langst[g] = max(langst[g], langst[n] + tid.get(g, 0))
    return max(langst.items(), key=lambda kv: kv[1])

tid = {k: 45 for k in ("aritmetik", "algebra", "ekvationer", "funktioner",
                       "derivator", "gradientnedstigning")}
print(langsta_vag(kurs, tid))    # ('gradientnedstigning', 180) — 4 noder à 45 min