Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos Pesquisas Classificação - Coggle Diagram
Grafos
Pesquisas
Classificação
Grafos:
Um par de dois conjuntos;
Tem vértices e arestas;
Os pares podem ser desordenados
(u,v) = (v,u) chamamos adjacentes
entre si com aresta não direcionada (u,v)
..
Já se (u,v) é diferente de (v,u)
temos que a aresta (u,v) é
direcionada de u (cauda da
aresta) atté v (cabeça da borda).
Um grafo direcionado também
pode ser chamado de dígrafo.
Sua representação é por meio
de setas, indicando a ordem de
relação.
Um grafo é dito direcionado
se TODAS suas arestas forem
direcionadas
Para ser não direcionado
TODAS arestas nele devem
ser não direcionadas
Quando não direcionados,
chamamos u e v de extremidades
da aresta (u,v) onde u e v são incidentes
Dependendo da proporção
entre a quantidade de vértices
e arestas, um grafo pode ser:
Completo
Denso
Esparso
Em algoritmos podem
ser representados por
meio de matrizes booleanas
ou listas de adjacências.
A matriz de um grafo não direcionado
é sempre simétrica
Já as listas de adjacências
são uma coleção de listas
cada uma representando um
vértice do grafo e indicando
todos os vértices ao qual ele
conecta
Se o grafo for esparso, usar
uma lista pode ser melhor que
uma matriz já que ocupará menos
espaço. O oposto se aplica para
grafos densos.
Um grafo é chamado de ponderado
quando há números atribuídos a seus
vértices, indicando pesos/custos.
Numa matriz, o valor
do elemento a[ i , j ] terá a
os valores de suas arestas.
Quando não há arestas o
valor será um o símbolo ∞
Propriedades
importantes
Se todos os vértices de um
caminho são difernetes, ele é simples
O comprimento de um
caminho é o número de
vértices da sequência menos 1.
Um grafo é conectado quando
para cada par de vértice há
uma aresta entre eles
Um grafo é dito cíclico quando
seu caminho começa e termina no
mesmo vértice, passando apenas 1
vez por vértice.
Aciclicidade
Conectividade
Algoritmos de pesquisas
em grafos
Em profundidade (DFS)
Inicia a travessia de um vértice
qualquer e tenta percorrer os não
visitados adjacentes aquele que está.
Isto ocorre até achar um beco sem
saída. Ao encontrar isto ele faz uma volta
ao último vértice e vai fazendo até encontrar
um vértice que ainda não visitou.
A busca termina quando ele faz uma
volta ao vértice que iniciou a travessia
Útil usar pilhas para a operação.
Em largura (BFS)
Diferente do outro tipo de busca
este ao invés de ir até achar um
vértice sem saída, escaneia primeiro
todos os adjacentes ao vértice inicial
e após ele vértices a 2 arestas de dist
do inicial, depois 3, 4, e assim até todos
serem visitados.
Útil usar filas para a operação.
Classificação topológica
Só funciona em grafos
acíclicos e direcionados
Quer ordenar um grafo em forma
de árvore e por ele de forma a
ser uma lista lienar
A lista ligada é formada pelo
tempo final usando uma DFS