0Pricing
DSA Interview Prep · Aula

Algoritmo de Kahn: ordenação topológica por BFS

Calcule os graus de entrada de todos os nós, enfileire os nós com grau de entrada zero e processe a fila para produzir uma ordem topológica enquanto detecta ciclos.

Algoritmo de Kahn: ordenação topológica por BFS é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.

O que é a ordenação topológica?

Uma ordenação topológica de um grafo acíclico direcionado (DAG) é uma ordenação de seus nós tal que toda aresta direcionada u → v significa que u vem antes de v na ordenação. Ela representa uma ordem de execução válida para tarefas com dependências — como sistemas de compilação, agendamento de cursos ou gerenciamento de pacotes. Apenas DAGs têm ordenações topológicas válidas; um ciclo torna isso impossível.

Algoritmo de Kahn: ideia central

O algoritmo de Kahn é uma abordagem baseada em BFS para a ordenação topológica. A ideia principal é que um nó com grau de entrada 0 (sem pré-requisitos) pode ser colocado primeiro na ordenação. Depois de colocá-lo, remova-o e diminua o grau de entrada de seus vizinhos. Novos nós com grau de entrada zero ficam disponíveis. Repita até que todos os nós sejam colocados ou um ciclo seja detectado (restam nós com grau de entrada diferente de zero).

Cálculo do grau de entrada

Primeiro, construa a lista de adjacência e calcule o grau de entrada (número de arestas que entram) de cada nó. Os nós com grau de entrada 0 são os pontos iniciais — eles não têm dependências. Para um grafo com arestas [(0,1),(0,2),(1,3),(2,3)], os graus de entrada são: 0→0, 1→1, 2→1, 3→2. Apenas o nó 0 começa com grau de entrada 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]

Implementação do algoritmo de Kahn

Enfileire todos os nós com grau de entrada zero em uma fila. Processe cada nó: adicione-o ao resultado e, em seguida, para cada vizinho, diminua seu grau de entrada e enfileire-o quando chegar a 0. Se a lista de resultados tiver menos nós que o grafo, existe um ciclo — alguns nós nunca poderiam ser retirados da fila.

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)]))

Detecção de ciclos com Kahn

O algoritmo de Kahn oferece detecção de ciclos sem custo adicional: se len(order) < n, alguns nós nunca foram adicionados à fila porque seu grau de entrada nunca chegou a 0 — eles fazem parte de um ciclo. Isso é mais simples que manter um vetor de visitados codificado por cores. Retorne uma lista vazia para indicar que existe um ciclo.

# 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]

Complexidade de tempo e espaço

O algoritmo de Kahn processa cada nó uma vez (é retirado da fila uma vez) e cada aresta uma vez (o grau de entrada é diminuído uma vez). Complexidade de tempo: O(V + E). Espaço: O(V + E) para a lista de adjacência e o vetor de graus de entrada, além de O(V) para a fila. Isso é ótimo — para produzir uma ordenação válida, é necessário no mínimo ler todos os nós e as arestas.

Ordenação topológica lexicograficamente menor

O algoritmo de Kahn com um heap mínimo em vez de uma fila produz a ordenação topológica lexicograficamente menor. Substitua deque por heapq: insira (node) e sempre processe primeiro o menor nó disponível. Isso garante a ordenação válida lexicograficamente menor entre todas as ordenações topológicas possíveis.

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)]))

Aplicação: Course Schedule I

Course Schedule (LeetCode 207): dados n cursos e seus pré-requisitos, é possível concluir todos os cursos? Modele os pré-requisitos como arestas direcionadas e verifique se existe uma ordenação topológica válida (isto é, sem ciclo). Retorne verdadeiro se o algoritmo de Kahn produzir uma ordem com comprimento n e falso se um ciclo for detectado.

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)

Aplicação: Course Schedule II

Course Schedule II (LeetCode 210): retorne a ordem real em que os cursos devem ser feitos. É igual ao caso anterior, mas retorne a lista order em vez de um valor booleano. Se existir um ciclo, retorne uma lista vazia. Isso usa diretamente a saída de Kahn como resposta.

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]]))

Agendamento de tarefas em paralelo

Um uso mais avançado: dado um conjunto de tarefas com dependências, encontre o número mínimo de “rodadas” necessário quando as tarefas sem dependências podem ser executadas em paralelo. Processe Kahn nível a nível (de forma semelhante à BFS por níveis): enfileire todos os nós com grau de entrada zero, processe toda a fila atual como uma rodada e, em seguida, enfileire os nós recém-liberados como a rodada seguinte. Conte as rodadas.

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

Ordenação topológica e DP em DAGs

A ordenação topológica permite a programação dinâmica em DAGs: processe os nós na ordem topológica e, ao calcular dp[v], todos os predecessores dp[u] já estarão definidos. Isso combina a ordenação topológica com DP para problemas como encontrar o caminho mais longo em um DAG, o custo mínimo para alcançar todos os nós ou o lucro máximo em uma cadeia de dependências. A ordenação garante que o valor de DP de cada nó seja calculado exatamente uma vez, depois que todas as suas dependências forem processadas.

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

Verificação rápida

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.

Recapitulação da lição

Nesta lição, você aprendeu que: o algoritmo de Kahn calcula a ordenação topológica removendo iterativamente os nós com grau de entrada zero por meio de BFS, a detecção de ciclos não tem custo adicional — se len(order) < n, existe um ciclo e substituir a fila por um heap mínimo produz a ordenação topológica lexicograficamente menor. Em seguida, exploraremos a ordenação topológica baseada na pós-ordem de DFS como alternativa ao algoritmo de Kahn.

Perguntas Frequentes

A aula “Algoritmo de Kahn: ordenação topológica por BFS” é grátis?

Sim — o texto completo de “Algoritmo de Kahn: ordenação topológica por BFS” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.

O que vou aprender em “Algoritmo de Kahn: ordenação topológica por BFS”?

Calcule os graus de entrada de todos os nós, enfileire os nós com grau de entrada zero e processe a fila para produzir uma ordem topológica enquanto detecta ciclos. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “Algoritmo de Kahn: ordenação topológica por BFS”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de DSA Interview Prep?

Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Algoritmo de Kahn: ordenação topológica por BFS
  2. Ordenação topológica por pós-ordem de DFS
  3. Cronograma de cursos I e II
  4. Componentes fortemente conexos com Kosaraju
← Voltar para DSA Interview Prep