Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos - Coggle Diagram

- - - - Tem o mesmo tempo que a pesquisa em profundidade
    - - Pode ser usado para buscar o menor caminho entre dois vértices, mas não pode ser usado para outras situações mais simples que a busca em profundidade resolve.
- - - - Um grafo com poucas arestas possíveis ausentes é chamado de denso, já o com poucas em relação ao número de vértices é chamado esparso.
  - - - Um caminho pode ser definido como uma sequência de vértices ligados por arestas que vão do ponto A para o ponto B
        
        Um grafo é dito conexo se cada cada par de vértices U e V tem um caminho de U para V.
- - - - Uma forma de resolver esse problema é usando a pesquisa em profundidade e invertendo a ordem quando alcançar uma aresta sem saída.
      - Outra forma de resolver é: repetidamente, identifique 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. Se não houver nenhuma, pare pois o problema não pode ser resolvido.