Please enable JavaScript.

Coggle requires JavaScript to display documents.

M10 - Coggle Diagram

- - - - Sua eficiência temporal é de Θ(|V |+|E|) para a representação de listas adjacentes, com |V| e |E| sendo o número do
        vértices e arestas do gráfico e Θ(|V |^2) para a representação de matriz
    - - Ele tem a mesma eficiência da depht search
  - - - Também dizemos que a aresta (u, v) sai de u e entra em v. A O gráfico em que cada aresta é direcionada é chamado de direcionado Gráficos direcionados também são
        chamados dígrafos.
- - - - Acontece que ser um dag não é apenas necessário mas também suficiente para que a topological sorting seja possível; ou seja, se um dígrafo não tem ciclos direcionados, o problema de topological sorting para ele tem uma solução
      - Além disso existe dois algoritmo eficientes que verificam se um dígrafo é um dag
        e, se for, produz uma ordenação de vertices que resolve a topological sorting
      - O primeiro algoritmo é uma aplicação simples depth search: execute um DFS
        traversal e observe a ordem em que os vértices se tornam dead ends.
        Inverter esta ordem resulta em uma solução para o problema de topological sorting desde que nenhum edge tenha sido encontrado.
        O dígrafo não é um dag e o topological sorting de vértices é impossível
      - O segundo algoritmo é baseado em uma implementação direta do decrease and conquer: repetidamente, identificar em um dígrafo restante uma fonte, que é um vértice sem arestas de entrada, e exclua-o junto com todas as arestas
        saindo dele. A ordem em que os vértices são excluídos produz uma solução
        para o problema de classificação topológica