PricingLoginStart free
DSA Interview Prep · Lektion

Kahns algoritme: Topologisk sortering med BFS

Beregn indgraderne for alle noder, indsæt noder med indgrad nul i køen, og behandl køen for at skabe en topologisk rækkefølge og samtidig registrere cykler.

Lektion 1 af 413 trin

Kahns algoritme: Topologisk sortering med BFS er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Hvad er topologisk sortering

En topologisk sortering af en rettet acyklisk graf (DAG) er en rækkefølge af dens knuder, sådan at hver rettet kant u → v betyder, at u kommer før v i rækkefølgen. Den repræsenterer en gyldig udførelsesrækkefølge for opgaver med afhængigheder — f.eks. i byggesystemer, kursusplanlægning eller pakkehåndtering. Kun DAG'er har gyldige topologiske rækkefølger; en cyklus gør det umuligt.

Kahns algoritme: Grundidé

Kahns algoritme er en BFS-baseret tilgang til topologisk sortering. Den centrale indsigt er, at en knude med indgrad 0 (ingen forudsætninger) kan placeres først i rækkefølgen. Når den er placeret, fjernes den, og indgraden for dens naboer reduceres. Nye knuder med indgrad 0 bliver tilgængelige. Gentag, indtil alle knuder er placeret, eller en cyklus registreres (der er stadig knuder med indgrad større end 0).

Beregning af indgrad

Først opbygger du naboskabslisten og beregner indgraden (antallet af indgående kanter) for hver knude. Knuder med indgrad 0 er startpunkterne — de har ingen afhængigheder. For en graf med kanterne [(0,1),(0,2),(1,3),(2,3)] er indgraderne: 0→0, 1→1, 2→1, 3→2. Kun knude 0 starter med indgrad 0.

from collections import deque, defaultdict

def compute_in_degree(n, edges):
    in_degree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    return graph, in_degree

graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind)  # [0, 1, 1, 2]

Implementering af Kahns algoritme

Sæt alle knuder med indgrad 0 i en kø. Behandl hver knude: føj den til resultatet, reducer derefter indgraden for hver nabo, og sæt naboen i kø, hvis den når 0. Hvis resultatlisten indeholder færre knuder end grafen, findes der en cyklus — nogle knuder kunne aldrig tages ud af køen.

from collections import deque, defaultdict

def kahn_topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    if len(order) == n:
        return order   # valid topological sort
    return []          # cycle detected

print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))

Cyklusregistrering med Kahn

Kahns algoritme giver cyklusregistrering uden ekstra omkostning: Hvis len(order) < n, blev nogle knuder aldrig føjet til køen, fordi deres indgrad aldrig nåede 0 — de indgår i en cyklus. Returnér en tom liste for at angive, at der findes en cyklus.

# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result)  # [] (cycle detected)

# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result)  # [0, 1, 2]

Tids- og pladskompleksitet

Kahns algoritme behandler hver knude én gang (tages ud af køen én gang) og hver kant én gang (indgraden reduceres én gang). Tidskompleksitet: O(V + E). Pladsforbrug: O(V + E) for naboskabslisten og indgradsarrayet plus O(V) for køen. Dette er optimalt — du skal som minimum læse alle knuder og kanter for at producere en gyldig rækkefølge.

Leksikografisk mindste topologiske rækkefølge

Kahns algoritme med en min-heap i stedet for en kø producerer den leksikografisk mindste topologiske rækkefølge. Erstat deque med heapq: indsæt (node), og behandl altid den mindste tilgængelige knude først. Det garanterer den leksikografisk mindste gyldige rækkefølge blandt alle mulige topologiske sorteringer.

import heapq
from collections import defaultdict

def kahn_lex_order(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    order = []
    
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)
    
    return order if len(order) == n else []

print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))

Anvendelse: Course Schedule I

Course Schedule (LeetCode 207): Givet n kurser og forudsætninger, kan du gennemføre alle kurser? Modellér forudsætningerne som rettede kanter, og kontrollér, om der findes en gyldig topologisk sortering (altså ingen cyklus). Returnér True, hvis Kahn producerer en rækkefølge med længden n, og False, hvis der registreres en cyklus.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:   # b must be taken before a
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))       # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)

Anvendelse: Course Schedule II

Course Schedule II (LeetCode 210): Returnér den faktiske rækkefølge, som kurserne skal tages i. Det er det samme som ovenfor, men du skal returnere listen order i stedet for en boolesk værdi. Hvis der findes en cyklus, skal du returnere en tom liste. Her bruges resultatet fra Kahn direkte som svaret.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Planlægning af parallelle opgaver

En mere avanceret anvendelse er at finde det mindste antal 'runder', der er nødvendigt, når opgaver uden afhængigheder kan køre parallelt. Kør Kahn niveau for niveau (svarende til BFS' niveauorden): Sæt alle knuder med indgrad 0 i kø, behandl hele den aktuelle kø som én runde, og sæt derefter nyligt frigivne knuder i kø som næste runde. Tæl runderne.

from collections import deque, defaultdict

def min_rounds(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    rounds = 0
    while queue:
        rounds += 1
        for _ in range(len(queue)):  # process current level
            node = queue.popleft()
            for nxt in graph[node]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
    return rounds

print(min_rounds(4, [(0,2),(1,2),(2,3)]))  # 3

Topologisk sortering og dynamisk programmering på DAG'er

Topologisk sortering muliggør dynamisk programmering på DAG'er: Behandl knuder i topologisk rækkefølge, og når du beregner dp[v], er alle forgængeres dp[u]-værdier allerede endelige. Dette kombinerer topologisk sortering med DP til problemer som længste vej i en DAG, mindste omkostning ved at nå alle knuder eller størst muligt udbytte fra en afhængighedskæde. Rækkefølgen garanterer, at hver knudes DP-værdi beregnes præcis én gang, efter at alle dens afhængigheder er behandlet.

from collections import deque, defaultdict

def longest_path_dag(V, edges):
    graph = defaultdict(list)
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    dp = [0] * V
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    return max(dp)

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)]))  # 7

Hurtigt tjek

Afprøv din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.

Besvar den i den interaktive lektion

Opsummering af lektionen

I denne lektion har du lært: Kahns algoritme beregner en topologisk sortering ved iterativt at fjerne knuder med indgrad 0 ved hjælp af BFS, cyklusregistrering er gratis — hvis len(order) < n, findes der en cyklus, og ved at erstatte køen med en min-heap får du den leksikografisk mindste topologiske rækkefølge. Næste gang undersøger vi DFS-baseret topologisk sortering i efterrækkefølge som et alternativ til Kahn.

Gratis at komme i gang

Lær Python med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser
30
Lektioner
120
Start gratisSe hele kurset

Ofte stillede spørgsmål

Er lektionen “Kahns algoritme: Topologisk sortering med BFS” gratis?

Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Kahns algoritme: Topologisk sortering med BFS”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Kahns algoritme: Topologisk sortering med BFS”?

Beregn indgraderne for alle noder, indsæt noder med indgrad nul i køen, og behandl køen for at skabe en topologisk rækkefølge og samtidig registrere cykler. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på DSA Interview Prep?

Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.

Hvor lang tid tager lektionen “Kahns algoritme: Topologisk sortering med BFS”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?

Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

  1. Kahns algoritme: Topologisk sortering med BFS
  2. Topologisk sortering med DFS-efterorden
  3. Course Schedule I og II
  4. Stærkt sammenhængende komponenter med Kosaraju
← Tilbage til DSA Interview Prep