Introdução:
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:
Conceitos Básicos:
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.
- Caminhos: sequência de arestas;
- Grafos conectados e não conectados:
- 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.
- Grafos ponderados: Cada aresta tem um peso ou valor associados a ela.
- Logo abaixo está um exemplo de um grafo orientado e ponderado:
- 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.
Algoritmos de Busca:
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:
- Começa-se a partir de um vértice inicial, marcando-o como visitado e empilhando-o em uma pilha.
- 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.
- Se todos os vértices adjacentes já tiverem sido visitados, o algoritmo desempilha o vértice atual e continua no vértice anterior.
- 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:
- Começa-se a partir de um vértice inicial, marcando-o como visitado e inseri-lo em uma fila.
- 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.
- 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.
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:
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
Top comments (0)