Um resumo sobre: grafos.
Tags: algorithms
Published: 2023-03-15 20:52:27

**<u>Introdução:</u>**

Embora os grafos tenham nós conectados por arestas, eles são diferentes das árvores, uma vez que os grafos não possuem uma estrutura hierárquica como a árvore que possui raiz, pais e filhos. Além disso, os grafos podem ter ciclos e possuem arestas direcionadas e não direcionadas, enquanto a árvore não tem ciclos e suas arestas não são direcionadas. 
A primeira figura é uma árvore, enquanto a segunda é um grafo:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ab43sq8kjqbety8ezuh3.png)

**<u>Conceitos Básicos:</u>**

Agora irei abordar alguns conceitos básicos sobre os grafos:
- Adjacência: Quando um nó é conectado ao outro por uma única aresta. Exemplo: o 5 é adjacente do: 6, 9, 4.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/66h3piy0bvggflzqr1ib.png)

- Caminhos: sequência de arestas;
- Grafos conectados e não conectados:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oo7mkj3p2ff9p94y5l5c.png)

- Grafos orientados: quando há uma orientação quanto a direção. Exemplo: o 7 vai até o 11, mas o 11 não vai até o 7.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fs7b0vvvtfxtmt8jkhl1.png)

- Grafos ponderados: Cada aresta tem um peso ou valor associados a ela.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/skj5kallsmlhhqc0qtv8.png)

- Logo abaixo está um exemplo de um grafo orientado e ponderado:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4471pqltr6140w2u8av1.png)

- Nós e arestas: Um nó pode representar um objeto da vida real (uma cidade, por exemplo) e uma aresta é o caminho até este nó.
- Representação: Matriz de adjacência e lista de adjacência.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eckrwg7zrinspzujq6d6.png)

**<u>Algoritmos de Busca:</u>**

**Busca em profundidade:**

A busca em profundidade (DFS, do inglês Depth-First Search) é um algoritmo de busca utilizado em grafos que percorre o grafo explorando o máximo possível em profundidade antes de retroceder para explorar outros ramos do grafo.
O algoritmo funciona da seguinte forma:

1. Começa-se a partir de um vértice inicial, marcando-o como visitado e empilhando-o em uma pilha.
2. O algoritmo escolhe um vértice da pilha e verifica se ele possui vértices adjacentes ainda não visitados. Se existirem, um deles é escolhido e marcado como visitado, empilhado na pilha e o passo 2 é repetido a partir deste vértice.
3. Se todos os vértices adjacentes já tiverem sido visitados, o algoritmo desempilha o vértice atual e continua no vértice anterior.
4. O algoritmo continua este processo até que a pilha esteja vazia.

A busca em profundidade visita todos os vértices e arestas do grafo que são alcançáveis a partir do vértice inicial. É possível modificar o algoritmo para encontrar caminhos específicos ou para percorrer o grafo de outras formas, por exemplo, visitando os vértices em ordem lexicográfica.
O tempo de execução do algoritmo de busca em profundidade depende do tamanho do grafo e da estrutura de dados utilizada para armazená-lo. Em geral, o tempo de execução é proporcional ao número de vértices e arestas do grafo, ou seja, O(V + E).

**Busca em Largura:**

A busca em largura (BFS, do inglês Breadth-First Search) é outro algoritmo de busca utilizado em grafos que percorre o grafo em largura, ou seja, visita todos os vértices em uma mesma profundidade antes de avançar para a próxima profundidade.
O algoritmo funciona da seguinte forma:

1. Começa-se a partir de um vértice inicial, marcando-o como visitado e inseri-lo em uma fila.
2. O algoritmo retira um vértice da fila e verifica se ele possui vértices adjacentes ainda não visitados. Se existirem, um deles é escolhido e marcado como visitado, inserido na fila e o passo 2 é repetido a partir deste vértice.
3. O algoritmo continua a retirar vértices da fila e adicionar seus vizinhos na fila até que a fila esteja vazia.
A busca em largura visita todos os vértices e arestas do grafo que são alcançáveis a partir do vértice inicial em ordem crescente de profundidade. O algoritmo também pode ser utilizado para encontrar caminhos mais curtos entre dois vértices.

**Busca Gulosa:**

A busca gulosa (também conhecida como busca heurística) é um algoritmo de busca em grafos que utiliza uma heurística para escolher o próximo nó a ser explorado. A heurística é uma função de avaliação que estima o quão promissor é um determinado nó em relação ao objetivo final da busca.
Em cada passo, a busca gulosa escolhe o nó com a melhor estimativa heurística e explora seus vizinhos. O objetivo é chegar ao nó objetivo com a menor quantidade de passos possível.
No entanto, a busca gulosa pode levar a soluções subótimas, já que a escolha do próximo nó a ser explorado é baseada apenas na heurística e não leva em consideração o caminho percorrido até o momento.
Por exemplo, imagine que um caminho longo pareça promissor com base na heurística, mas um caminho mais curto seria mais eficiente. A busca gulosa pode escolher o caminho longo e, portanto, não encontrar a solução mais otimizada.
Apesar dessa limitação, a busca gulosa pode ser uma boa opção para grafos muito grandes ou para problemas onde a solução ótima não é crucial. É importante, no entanto, escolher uma boa heurística para maximizar a eficiência do algoritmo.

O tempo de execução do algoritmo de busca em largura também depende do tamanho do grafo e da estrutura de dados utilizada para armazená-lo. Em geral, o tempo de execução é proporcional ao número de vértices e arestas do grafo, ou seja, O(V + E). No entanto, a busca em largura geralmente é mais lenta que a busca em profundidade em grafos densos, já que requer a criação de uma fila para armazenar todos os vértices a serem visitados.

**Busca A *:**

A busca A* (A-star) é um algoritmo de busca heurística que também é usado para encontrar o caminho mais curto entre um nó de partida e um nó de destino em um grafo ponderado. É semelhante à busca gulosa em que utiliza uma heurística para estimar a distância do nó atual até o nó de destino, mas também leva em consideração o custo do caminho percorrido até o momento.
O algoritmo A* usa uma função de avaliação que combina a heurística e o custo do caminho até o nó atual. A função de avaliação é definida como f(n) = g(n) + h(n), onde g(n) é o custo do caminho do nó inicial até o nó atual e h(n) é a estimativa heurística da distância do nó atual até o nó de destino. O objetivo da busca é encontrar o caminho com o menor valor de f(n).
A busca A* é considerada uma das melhores técnicas para encontrar o caminho mais curto em um grafo ponderado porque é completa (encontra uma solução se ela existe) e ótima (encontra a solução com o menor custo possível). No entanto, ela pode ser mais lenta do que a busca gulosa, dependendo da heurística escolhida e da complexidade do grafo.


Nestas duas imagens veremos a diferença entre a busca gulosa (imagem 1) e a busca A*:

Estas imagens representam um caminho entre uma cidade e outra, para montar um algoritmo eficiente para traçar um caminho entre as duas cidades, nós podemos utilizar a busca gulosa e a busca A*. Na busca gulosa foi levada em consideração somente a heurística, em que as cidades que seriam percorridas seriam a com menor distância entre o destino. Já na busca A*, além desse parâmetro, foi utilizado também o ‘peso’ do vetor, que seria a distância entre as cidades adjacentes. 


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lbz2s7lubsqz4i0dpfy9.png)



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r0fchoq6y0768tyczano.png)

**Algoritmo de Dijkstra:**

O algoritmo de Dijkstra é um método utilizado para encontrar o caminho mais curto em um grafo com arestas não negativas, partindo de um vértice de origem. Ele seleciona os vértices com as menores distâncias da origem e atualiza as distâncias dos vértices adjacentes caso seja possível encontrar um caminho mais curto. Esse processo continua até que todas as distâncias tenham sido determinadas. No final, o algoritmo retorna a distância mais curta de cada vértice para a origem e o caminho mais curto correspondente.

Veja na imagem que ele foi de A até F e escolheu o menor caminho vendo o todo:



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/li2ohejc7kpa939qpkvk.png)



Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: [Estruturas de dados e algoritmos em python](https://www.udemy.com/course/estrutura-de-dados-e-algoritmos-python-guia-completo/)