Algoritmos de Grafos

Prévia do material em texto

Algoritmos e Complexidade
Algoritmos de Grafos
Algoritmos de Grafos
Agora que já compreendemos as principais estruturas, nomenclaturas e definições
dos Grafos, vamos estudar três importantes algoritmos deste contexto
Dois algoritmos de busca
Busca em profundidade
Busca em largura
Algoritmo de caminho mais curto.
O algoritmo de Dijkstra
Algoritmos de Grafos
Um algoritmo de busca (ou de varredura) é qualquer algoritmo que visita todos os
vértices de um grafo andando pelos arcos de um vértice a outro.
Há muitas maneiras de fazer uma tal busca. 
Cada algoritmo de busca é caracterizado pela ordem em que visita os vértices. 
Algoritmos de Grafos
O poderoso algoritmo de busca em profundidade (= depth-first search), ou busca
DFS.
Aqui, é objetivo é visitar todos os vértices e numerá-los na ordem em que são
descobertos.
Assim poderemos saber se um elemento está, ou não, em um determinado grafo e,
também, analisar caminho e conectividade entre eles!
A busca em profundidade não resolve um problema específico.
Ela é apenas um arcabouço, ou pré-processamento, para a resolução eficiente de
vários problemas concretos. 
A busca DFS nos ajuda a "compreender" o grafo com que estamos lidando,
revelando sua "forma" e reunindo informações (representadas pela numeração dos
vértices) que ajudam a responder perguntas sobre o grafo.
São vários os problemas solucionados através dele!
Algoritmos de Grafos
O algoritmo se inicia buscando um vértice aleatoriamente!
Se estamos buscando um vértice específico e já ele, podemos encerrar a busca!
Se não, chamamos recursivamente a busca para cada vértice adjacente ainda não
visitado!
Veremos que ele é uma representação genérica da “busca pré-ordem” que
efetuamos para o caminhamento em árvores
Conhecendo o custo de deslocamento de cada vértice como |V|
E o custo de transitar para cada aresta é |A|
A complexidade de pior caso é O(|V| + |A|)
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
A busca em largura (= breadth-first search), ou busca BFS, começa por um vértice,
digamos s, especificado pelo usuário.
O algoritmo visita s, depois visita todos os vizinhos de s, depois todos os vizinhos
dos vizinhos, e assim por diante.
O algoritmo numera os vértices, em sequência, na ordem em que eles são
descobertos (ou seja, visitados pela primeira vez).
Para fazer isso, o algoritmo usa uma fila (= queue) de vértices.
No começo de cada iteração, a fila contém vértices que já foram numerados mas
têm vizinhos ainda não numerados.
O processo iterativo consiste no seguinte: 
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
O custo se mantém O(V+A), mas por motivos diferentes
O custo de inserir e remover da fila é constante!
Os vértices são enfileirados e removidos uma vez: O(V)
As arestas são todas percorridas: O(A)
Logo teremos O(V+A)
Algoritmos de Grafos
Um problema muito comum em DIVERSOS cenários (não apenas geográficos e de
percursos) é o do caminho mais curto!
Roteamento
Tubulação
O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger
Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais
curto num grafo dirigido ou não dirigido com arestas de peso não negativo.
O tempo computacional é de O(A + V log (V))
Algoritmos de Grafos
O algoritmo considera um conjunto S de menores caminhos, iniciado com um
vértice inicial I.
A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S
aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo
os passos até que todos os vértices alcançáveis por I estejam em S.
Arestas que ligam vértices já pertencentes a S são desconsideradas.
Algoritmos de Grafos
Algoritmos de Grafos
De forma iterativas poderemos ter o algoritmo representado da seguinte forma!
Depois de uma boa olhada, você perceberá que o caminho A → C → D → F nos
dará o caminho mais curto. 
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Algoritmos de Grafos
Vamos pensar em alguns casos:
Suponha que, em um determinado espaço do tabuleiro, se você passar por ele,
você ganha uma carta que te dá um bônus de -3 casas (ou seja, você retrocede 3
casas).
Nesse caso, você pode representar o tabuleiro como um grafo, onde cada espaço é
um nó e as movimentações entre eles são as arestas. A aresta que conecta o
espaço onde você ganha a carta ao próximo espaço teria um peso negativo de -3.
Algoritmos de Grafos
I imagine um sistema de transporte público onde algumas rotas têm bônus ou
descontos em horários específicos (como horários de menor movimento). Se um
ônibus, por exemplo, oferece um desconto de 5 reais para uma determinada rota,
isso poderia ser representado como uma aresta com peso negativo em um grafo,
onde os nós representam as paradas e as arestas representam os custos das rotas
entre elas.
Outro exemplo é em redes de comunicação, onde a latência entre dois pontos pode
ser reduzida por um incentivo (como priorização de tráfego), criando uma aresta
negativa entre os nós que representam os dois pontos da rede.
O que esses exemplos implicariam no algoritmo de Dijkstra?
Algoritmos de Grafos
Imagine um sistema de transporte público onde algumas rotas têm bônus ou
descontos em horários específicos (como horários de menor movimento). Se um
ônibus, por exemplo, oferece um desconto de 5 reais para uma determinada rota,
isso poderia ser representado como uma aresta com peso negativo em um grafo,
onde os nós representam as paradas e as arestas representam os custos das rotas
entre elas.
Outro exemplo é em redes de comunicação, onde a latência entre dois pontos pode
ser reduzida por um incentivo (como priorização de tráfego), criando uma aresta
negativa entre os nós que representam os dois pontos da rede.
O que esses exemplos implicariam no algoritmo de Dijkstra?
Algoritmos de Grafos
O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um
digrafo (grafo orientado ou dirigido) ponderado, ou seja, cujas arestas têm peso,
inclusive negativo.
O Algoritmo de Dijkstra resolve o mesmo problema, num tempo menor, porém
exige que todas as arestas tenham pesos positivos. Portanto, o algoritmo de
Bellman-Ford é normalmente usado apenas quando existem arestas de peso
negativo.
Algoritmos de Grafos
No link abaixo temos uma implementação simples do algoritmo de Dijkstra para o
grafo a seguir!
https:
//github.com/yurifarod/Algorithms/blob/master/Estrutura%20de%20Dados/10_dijs
kstra.c
Algoritmos de Grafos
Reimplemente-a para o grafo abaixo (vale ponto)
Lembre-se que agora os caminhos são de ida e volta (não é direcionado, dígrafo)
https:
//github.com/yurifarod/Algorithms/blob/master/Estrutura%20de%20Dados/10_dijs
kstra.c