Ordenação Topológica

10.1 Definição de Ordenação Topológica

Ordenação Topológica é uma ordenação linear dos vértices de um grafo direcionado acíclico (DAG) tal que, para cada aresta (u, v), o vértice u precede o vértice v. Essa ordenação é possível apenas para DAGs e não pode ser executada em grafos que contêm ciclos.

E aí, curtiu a definição? Se você já sacou de primeira, provavelmente tem uma boa experiência com algoritmos.

Explicando de forma mais simples: você tem uma lista de tarefas (vértices do grafo) e uma lista de dependências entre elas (setas no grafo). Organize as tarefas (vértices) de modo que todas as tarefas das quais a "tarefa A" depende sejam realizadas antes dela. Agora ficou bem mais claro, né?

Ordenação Topológica é um algoritmo muito importante na prática, por isso ele tem um nome próprio, e não apenas o nome do autor. Vamos entender onde ele é necessário:

Aplicações:

1. Planejamento de Tarefas (Task Scheduling):

Determinar a ordem de execução de tarefas dependentes para que cada tarefa seja executada após todas as suas dependências.

Exemplo:

Planejamento de projetos em sistemas de gerenciamento de projetos.

2. Compilação de código:

Determinar a ordem de compilação de módulos ou arquivos de código fonte que dependem uns dos outros.

Exemplo:

Otimização de build de software em sistemas de build (como Makefile).

3. Resolução de dependências em gerenciadores de pacotes:

Organizar pacotes para que todas as dependências sejam instaladas antes do próprio pacote.

Exemplo:

Facilitação do processo de instalação de software em gerenciadores de pacotes (como npm, pip, apt).

4. Otimização de rotas:

Determinar a ordem de visita a pontos ou execução de ações, considerando as dependências entre eles.

Exemplo:

Logística e planejamento de rotas de entrega de mercadorias.

Complexidade temporal e espacial da ordenação topológica:

Complexidade Temporal:

Ambos os principais algoritmos de ordenação topológica (DFS e algoritmo de Kahn) têm complexidade temporal O(V + E), onde V é o número de vértices e E é o número de arestas no grafo.

Complexidade Espacial:

A complexidade espacial de ambos os algoritmos é O(V + E), pois é necessário armazenar o grafo, bem como arrays para monitorar vértices visitados e predecessores.

10.2 Implementação com busca em profundidade (DFS)

A ordenação topológica pode ser realizada de diferentes maneiras, uma delas é baseada na busca em profundidade — DFS. O algoritmo DFS para ordenação topológica utiliza uma pilha para rastrear os nós concluídos.

Exemplo de implementação:

def topological_sort_dfs(graph):
    def dfs(vertex, visited, stack):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor, visited, stack)
        stack.append(vertex)
        
    visited = set()
    stack = []
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex, visited, stack)
            
    return stack[::-1]  # Resultado em ordem reversa
    
# Exemplo de uso:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_dfs(graph)
print("Ordenação Topológica:", result)

Saída:

Ordenação Topológica: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']

10.3 Implementação: algoritmo de Kahn

Outra abordagem é chamada de algoritmo de Kahn (Kahn's Algorithm). O algoritmo de Kahn para ordenação topológica utiliza o conceito de grau de entrada dos vértices.

Exemplo de implementação:

from collections import deque, defaultdict

def topological_sort_kahn(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
            
    queue = deque([u for u in graph if in_degree[u] == 0])
    top_order = []
            
    while queue:
        u = queue.popleft()
        top_order.append(u)
            
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
            
    if len(top_order) == len(in_degree):
        return top_order
    else:
        raise ValueError("O grafo contém um ciclo")
            
# Exemplo de uso:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_kahn(graph)
print("Ordenação Topológica:", result)

Saída:

Ordenação Topológica: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']

1

Pesquisa/teste

Busca em largura e profundidade, nível 56, lição 4

Indisponível

Busca em largura e profundidade

Busca em largura e profundidade

Abrir