Ordena vértices de um grafo direcionado acíclico (DAG) de forma que para toda aresta u->v, u aparece antes de v.
Topological Sort ordena vértices de um DAG (Directed Acyclic Graph) de forma que todas as dependências aparecem antes dos vértices que dependem delas. É como ordenar tarefas onde algumas precisam ser feitas antes de outras. Existem duas abordagens clássicas: Algoritmo de Kahn (BFS): Começa pelos vértices sem dependências (grau de entrada = 0) e vai removendo-os do grafo, atualizando os graus dos vizinhos. Quando um vizinho fica com grau 0, ele entra na fila. DFS com pós-ordem: Faz DFS normal, mas adiciona cada vértice ao resultado DEPOIS de visitar todos os vizinhos. No final, inverte o resultado. Ambos detectam ciclos: Kahn verifica se processou todos os vértices; DFS usa coloração para detectar back edges.
“Vértices sem dependências (grau de entrada 0) podem ser processados imediatamente. Ao processá-los, liberamos seus dependentes.”
Cada vértice é processado uma vez, cada aresta é examinada uma vez.
Calculamos grau de entrada em O(E), processamos cada vértice uma vez e cada aresta uma vez ao atualizar graus.
Armazenamos graus de entrada e a fila, ambos O(V).
Sempre precisamos examinar todo o grafo.
Mesmo com ciclo, detectamos após processar o grafo.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| Kahn (BFS)(atual) | O(V + E) | O(V) | Detectar ciclos facilmente, processar em paralelo |
| DFS pós-ordem(atual) | O(V + E) | O(V) | Implementação simples se já tem DFS |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1from collections import dequeInicializar Fila2 3 4def topological_sort_kahn(graph):Definição5 # Calcular grau de entrada6 in_degree = {v: 0 for v in graph}Calcular Grau de Entrada7 for v in graph:Calcular Grau de Entrada8 for neighbor in graph[v]:Calcular Grau de Entrada9 in_degree[neighbor] += 1Calcular Grau de Entrada10 11 # Vertices sem dependencias12 queue = deque([v for v in graph if in_degree[v] == 0])Inicializar Fila13 result = []14 15 while queue:Loop Principal16 v = queue.popleft()Desenfileirar17 result.append(v)Desenfileirar18 19 for neighbor in graph[v]:Processar Vizinhos20 in_degree[neighbor] -= 1Processar Vizinhos21 if in_degree[neighbor] == 0:Verificar Grau Zero22 queue.append(neighbor)Verificar Grau Zero23 24 if len(result) != len(graph):Verificar Ciclo25 return None # Ciclo detectadoVerificar Ciclo26 27 return result28 29 30def topological_sort_dfs(graph):Definição31 visited = set()32 result = []33 34 def dfs(v):Visitar DFS35 visited.add(v)36 for neighbor in graph[v]:Visitar DFS37 if neighbor not in visited:Visitar DFS38 dfs(neighbor)Visitar DFS39 result.append(v)Pós-Ordem40 41 for v in graph:42 if v not in visited:43 dfs(v)44 45 return result[::-1]Pós-Ordem46