Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Ordenação topológica
DFS e BFS são os principais algoritmos de travessias para dígrafos também, porém, as estruturas de suas florestas correspondentes podem ser mais complexas do que para grafos não-direcionados.
Existem 4 tipos de arestas possíveis em uma floresta DFS dígrafa:
tree edges
,
back edges
dos vértices aos seus ancestrais,
forward edges
dos vértices aos seus descendentes na árvore, que não são seus filhos, e,
cross edges
que são os que não se encaixam nas categorias acima, as exceções.
A presença de back edges indica que o dígrafo tem um ciclo direcionado. Um
ciclo direcionado
em um dígrafo é uma sequência de três ou mais vértices, que começa e termina em um mesmo vértice, e, no qual, todo vértice está conectado ao seu predecessor imediato por uma aresta direcionada do predecessor ao sucessor.
Se a floresta DFS de um dígrafo não tiver back edges, o dígrafo é um
dag
, acrônimo para
directed acyclic graph (grafo acíclico direcionado)
.
Em um dígrafo, podemos listar seus vértices de uma maneira que para cada aresta do grafo, o vértice onde a aresta começa é listado antes do vértice onde a aresta termina?
Este problema é chamado
topological sorting (ordenação topológica)
.
Ou seja, não existe uma solução para o problema se existirem ciclos no dígrafo.
Então, para a ordenação topológica ser possível o dígrafo precisa ser um dag.
Existem 2 algoritmos eficientes que checam se o dígrafo é um dag, e se for, apresenta uma ordenação dos vértices que resolve o problema de ordenação topológica.
O primeiro é uma simples aplicação da travessia DFS, onde são notados quais os vértices que se tornaram os "becos sem saída" (foram removidos da pilha). Quando essa ordem é revertida temos a solução para o problema, previsto que não sejam encontrados back edges durante a travessia.
O segundo algoritmo é baseado em uma implementação da técnica diminuir(por um) e conquistar: repetidamente identificando no dígrafo restante uma
fonte (source)
, na qual o vértice não tem arestas direcionadas a ele e removendo-o junto com todas as arestas saindo dele.
Se existirem diversas fontes, o empate é quebrado arbitrariamente, se não existirem fontes, o problema não tem solução.
A ordem que os vértices são removidos é a solução para o problema de ordem topológica.
Caminhos e Ciclos
Entre as diversas propriedades de grafos, duas são muito importantes para diversas aplicações:
conectividade
e
aciclicidade
.
Ambas são baseadas na noção de caminho.
Um
caminho
de um vértice
u
para um vértice
v
de um grafo
G
pode ser definido como uma sequência de vértices adjacentes que começam com
u
e terminam com
v
.
Se todos os vértices do caminho são distintos, o caminho é dito como
simples
. O
tamanho
do caminho é o número total de vértices na sequência de vértices definindo o caminho menos 1, que é igual a qtde. de arestas no caminho.
Um
caminho direcionado
é uma sequência de vértices, na qual todo par consecutivo de vértices, está conectado por uma aresta direcionada do vértice listado antes, ao vértice listado depois.
Um
ciclo
é um caminho de tamanho positivo que começa e termina no mesmo vértice e não passa pela mesma aresta mais de uma vez.
Um grafo sem ciclos é dito
acíclico
.
Representações de Grafos
Grafos em computação são normalmente representados de dois jeitos: matriz de adjacência e listas de adjacência.
A
matriz de adjacência
de um grafo com
n
vértices é uma matriz booleana
n x n
, com uma linha e uma coluna para cada vértice do grafo, na qual os elementos da linha
i
e da coluna
j
, são iguais a 1 se existir uma aresta do vértice
i
para o vértice
j
, e 0 se não existirem arestas.
A matriz de adjacência de um grafo não-direcionado é sempre simétrica.
As
listas de adjacência
de um grafo ou dígrafo é uma coleção de listas ligadas, uma para cada vértice, que contêm todos os vértices adjacentes ao vértice da lista.
Se um grafo for escasso, a representação de listas de adjacência pode usar menos espaço que uma matriz de adjacência, apesar do armazenamento extra consumido por apontadores das listas ligadas; a situação é exatamente a oposta para grafos densos.
Grafos Ponderados
Um
grafo ponderado
(ou dígrafo) é um grafo com números designados às suas arestas. Esses números são chamados
pesos
ou
custos
.
Esses grafos tem várias aplicações no mundo real, como encontrar o menor caminho entre dois pontos em uma network de transportação ou de comunicação.
Se um grafo ponderado for representado por uma matriz de adjacência, seus elementos
A[i, j]
vão simplesmente substituir os 1's com seus respectivos pesos, e os 0's com um símbolo especial. Essa matriz é chamada
matriz de peso
ou
matriz de custo
.
Listas de adjacência para um grafo ponderado, têm que incluir em seus nós não só o nome de um vértice adjacente, mas também o peso da aresta correspondente.
Processamento de todos os vértices e arestas de um grafo
DFS(Depth-First Search)
Esse processo continua até um beco sem saída, um vértice sem vértices adjacentes não-visitados, é encontrado. A partir daí o algoritmo volta uma aresta em direção ao vértice de onde começou e tenta continuar visitando não-visitados vértices.
O algoritmo eventualmente para depois de voltar ao vértice de onde começou. Então, se pressupõe que todos os vértices no mesmo componente conectado foram visitados. Se ainda existirem vértices não-visitados, a DFS recomeça em um deles.
É conveniente usar pilhas para rastrear a operação de DFS. Um vértice é empilhado quando a visita desse vértice começa, e desempilhado quando a visita desse vértice termina.
Também é útil usar a
depth-first search forest
para acompanhar a travessia DFS.
O vértice que começa a travessia serve como a raiz da primeira árvore na floresta. Quando um novo vértice não-visitado é visitado, ele é anexado a árvore como um filho do vértice anterior. E sua aresta é chamada
aresta de árvore (tree edge)
porque o conjunto de todas as suas arestas formam uma árvore.
O algoritmo pode, também, encontrar uma aresta que liga um vértice à um vértice previamente visitado que não é o seu predecessor. Esta aresta é chamada de
back edge
porque conecta um vértice ao seu ancestral, que não é seu pai.
Quão eficiente é o DFS?
O seu tamanho é proporcional ao tamanho da estrutura de dados usada para representar o grafo em questão.
Então, para a representação de matriz de adjacência, o tempo de travessia está em Θ(
|V|
²), e, para a lista de adjacência, está em Θ(
|V| + |E|
), onde |V|=qtde. de vértices, e, |E|= qtde. de arestas.
A travessia DFS e sua representação de floresta, provaram ser extremamente úteis no desenvolvimento de algoritmos eficientes de checagens de algumas propriedades dos grafos.
Que são elas: checar conectividade e checar a aciclicidade de um grafo.
Para checar a conectividade, a travessia DFS começa em um vértice arbitrário e checa, depois que o algoritmo para é analisado se todos os vértices do grafo foram visitados, se sim, o grafo é conectado, se não, então o grafo não é conectado.
Para checar a aciclicidade, é usada a floresta DFS, se ela não tiver back edges, então o grafo é acíclico, se tiver back edges, então o grafo é cíclico.
Depth-First Search (DFS)
começa a travessia de um grafo por um vértice arbitrário, marcando ele como visitado. A cada iteração o algoritmo procede à um vértice não-visitado que é adjacente ao atual
BFS(Breadth-First Search)
A BFS procede de uma maneira concêntrica, visitando todos os vértices que são adjacentes ao vértice que começou, só depois vai aos vértices não-visitados duas arestas distante dele, e continua até todos os vértices no mesmo componente conectado do vértice que começou serem visitados.
Se ainda existirem vértices não-visitados, o algoritmo recomeça em outro vértice arbitrário de outro componente conectado.
Em BFS a estrutura de dados Fila é usada para rastrear sua operação. A fila é inicializada com o vértice que começa a travessia, marcando-o como visitado. A cada iteração, o algoritmo identifica todos os vértices não-visitados que são adjacentes ao vértice da frente, marcando-os como visitados, e adicionando-os à fila, depois disso o vértice da frente é removido da fila.
Similarmente à travessia DFS, é possível acompanhar a travessia BFS construindo uma floresta, a
breadth-first florest
.
O vértice que começa a travessia serve como a raiz da primeira árvore na floresta. Sempre que um vértice não-visitado é visitado, esse vértice é anexado como um filho do vértice anterior, com uma aresta chamada
tree edge
.
Se uma aresta que liga um vértice à um vértice previamente visitado, que não é seu predecessor imediato, ou seu pai, é encontrada, a aresta é tida como
cross edge
.
Quão eficiente é o BFS?
Tem a mesma eficiência que o DFS.
BFS também pode ser usado para checar a conectividade e aciclicidade de um grafo.
Também pode ser usado para encontrar um caminho com a menor qtde. de arestas entre dois vértices. Começando a travessia no primeiro vértice e parando logo que o segundo vértice é alcançado.
Informalmente, é uma coleção de pontos no plano chamados "vértices" ou "nós", com alguns deles conectados por segmentos de linhas chamados "arestas" ou "arcos".
Formalmente, um grafo G = {V,E} é definido como um par de dois conjuntos: um conjunto
V
finito, não-vazio, de itens chamados vértices, e um conjunto
E
de pares desses itens chamados arestas.
Se esses pares de vértices forem desordenados, ou seja, se um par de vértice (
u, v
) for o mesmo que o par (
v, u
), dizemos que os vértices
u
e
v
são
adjacentes
e conectados por uma
aresta não-direcionada
.
Os vértices
u
e
v
são chamados pontos finais da aresta (
u, v
) e dizemos que
u
e
v
são
incidentes
à esta aresta, com a aresta (u, v) sendo incidente aos pontos finais
u
e
v
.
O grafo G é
não-direcionado
se todas as suas arestas forem não-direcionadas.
Se o par de vértices (
u, v
) não for o mesmo que o par (
v, u
), dizemos que a aresta (
u, v
) é
direcionada
do vértice
u
, chamado
tail
, ao vértice
v
, chamado
head
, com a aresta (
u, v
) que sai em
u
e entra em
v
.
O grafo G é
direcionado
ou
dígrafo
se todas as suas arestas forem direcionadas.
Como nessa definição não são permitidas múltiplas arestas entre os mesmos vértices de um grafo não-direcionados, nós temos a seguinte desigualdade para a qtde. de arestas
|E|
possíveis com
|V|
vértices e sem loops:
0 <=
|E|
<=
|V|
(
|V|
- 1)/2
Um grafo com todos os pares de seus vértices conectados por uma aresta é chamado de
completo
. Um grafo faltando relativamente poucas arestas é chamado de
denso
. Um grafo com poucas arestas relativas à qtde. de vértices é chamado de
escasso(sparse)
.