Please enable JavaScript.
Coggle requires JavaScript to display documents.
Topological Sorting - Coggle Diagram
Topological Sorting
Busca em Profundidade (DFS) em Digraphs
Estrutura de florestas mais complexa
Tipos de arestas em uma floresta DFS
Tree edges
Back edges
Forward edges
Cross edges
Ciclos dirigidos:
Presença de back edge indica um ciclo dirigido
Ausência de back edges indica um grafo acíclico dirigido (DAG)
Problema de Ordenação Topológica
Modelagem de cursos com pré-requisitos como um digraph
Condição para ordenação topológica
Lista de vértices onde para cada aresta (u, v), u aparece antes de v
Necessário e suficiente que o digraph seja um DAG
Algoritmos para ordenação topológica:
Baseado em DFS
Remoção de fontes (decrease-by-one)
Introdução
Problema importante para grafos direcionados
Aplicações: tarefas com pré-requisitos
Aplicações e Importância
Verificação de pré-requisitos em grandes projetos
Aplicações em ciência da computação:
Agendamento de instruções na compilação de programas
Ordenação de avaliação de células em fórmulas de planilhas
Resolução de dependências de símbolos em linkers
Grafos Direcionados (Digraphs)
Direções especificadas para todas as arestas
Representações principais: Matriz de Adjacência, Listas de Adjacência
Diferenças para grafos não direcionados
Matriz de Adjacência não simétrica
Aresta tem apenas um nó correspondente nas listas de adjacência
Algoritmo Baseado em DFS
Executa uma busca em profundidade
Ordem dos vértices ao se tornarem dead-ends (desempilhados) é inversa da solução
Verifica se o digraph é um DAG
Ilustração com exemplo de cursos
Algoritmo de Remoção de Fontes
Identifica uma fonte (vértice sem arestas de entrada)
Remove a fonte e todas as arestas saindo dela
Ordem de remoção dos vértices é a solução
Diferentes soluções possíveis dependendo da escolha das fontes