Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos, Topological sorting, Depth-First Search and Breadth-First Search,…
Grafos
Caminho e ciclos
Um caminho (u,v) é uma sequência de arestas que começa em u e termina em v
-
-
-
-
Um caminho que começa em um vértice e termina nele mesmo é chamado de ciclo, grafos sem ciclos são chamados de acíclicos
Formas de representar
Matriz adjacente
Matriz em que as linhas são os grafos e as colunas também, em que se houver uma aresta ligando o vértice i com j, a matriz[i][j] = 1, caso contrário = 0
-
Lista adjacente
Uma coleção de linked lists, onde existe um header para cada vértice do grafo
-
Peso em grafos
É um grafo normal, porém cada aresta tem um custo de travessia
-
Coleção de pontos, conhecida como nós ou vértices ligados ou não por arestas
A arestas são definidas por pares disordenados, (a,b) é a mesma coisa que (b,a)
-
Se for ordenado, o grafo é chamado de dirigido
-
-
Topological sorting
Tipo de problema relacionado a digrafos, onde para os vértices de destino, tem que primeiro ser listados os de chegada
-
Executar uma DFS e anotar a ordem em que os vértices se tornam dead ends, ao inverter essa ordem a solução é encontrada
Se algum vértice for encontrado novamente, não há solução
Outra forma de fazer o algoritmo, é deletando todos os vértices que não possuem arestas incidentes, até sobrar nenhum elemento e anotar essa ordem
Se não houver vértices sem arestas incidentes, o problema não tem solução
Possui várias soluções, por isso uma resposta muito importante é se existe ordem topológica
-
-