Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos, Depth-first search, Topological Sorting, breadth-first search -…
Grafos
Caminhos
Vértices conectados
Comprimento = nV-1
Ciclos = caminhos que inicial e acabam no mesmo lugar
Matriz de adjacências
Matriz de 0 e 1
Melhor para denso
Lista de adjacências
Linked Lists pra cada vértice
Melhor para esparso
Grafos com peso
Podem ser representados das duas formas
Vértices + edges
Direcionados ou não
Completos / Densos / Esparsos
Depth-first search
Floresta
Procura tree edges a partir da root
Visita adjacentes marcando eles como "visitados"
*stack
Matriz: (-) V^2
Lista: (-) V + E
Topological Sorting
Grafos direcionados
Matriz não simétrica || Só um nó correspondente
Listar coisas em uma certa ordem
Precisa ser um dag
Source removal
DFS-based
breadth-first search
Visita os adjacentes ao início
Mesma eficiência do DFS