Grafos
📚 Introdução
Um grafo é uma estrutura que consiste em um conjunto de pontos, chamados de vértices, e um conjunto de linhas que conectam esses vértices, chamadas de arestas. Em outras palavras, um grafo é uma representação visual de objetos (vértices) e suas conexões (arestas).
Essa estrutura é usada para modelar relações entre diferentes elementos, como redes de computadores, mapas de estradas, redes sociais e muito mais. Em um grafo, os vértices representam os pontos e as arestas representam as ligações entre esses pontos.
Existem diversos tipos de grafos, sendo os mais comuns:
Grafo direcionado: um grafo onde as arestas possuem uma direção, ou seja, uma aresta do vértice
a
para o vérticeb
não implica que existe uma aresta do vérticeb
para o vérticea
.Grafo não direcionado: um grafo onde as arestas não possuem uma direção, ou seja, uma aresta do vértice
a
para o vérticeb
implica que existe uma aresta do vérticeb
para o vérticea
.
🔗 Representação de grafos
Uma ótima forma de representar grafos em python é usando listas de adjacência. Uma lista de adjacência é uma lista onde cada elemento representa um vértice e contém uma lista com os vértices adjacentes a ele.
O código fica mais ou menos assim:
🧮 Busca em largura
A busca em largura (BFS - Breadth First Search) é um algoritmo de busca em grafos que explora os vértices de um grafo em camadas.
O algoritmo funciona da seguinte forma:
Começamos a busca em um vértice inicial
s
, colocando-o em uma fila.Enquanto a fila não estiver vazia, retiramos um vértice da fila e exploramos todos os vértices adjacentes a ele.
Se um vértice adjacente não foi visitado ainda, colocamos ele na fila e marcamos como visitado.
O algoritmo termina quando não há mais vértices na fila.
🧮 Busca em profundidade
A busca em profundidade (DFS - Depth First Search) é um algoritmo de busca em grafos que explora o máximo possível de um grafo antes de voltar.
O algoritmo funciona da seguinte forma:
Começamos a busca em um vértice inicial
s
, marcando-o como visitado.Para cada vértice adjacente a
s
, se ele não foi visitado ainda, visitamos ele e repetimos o processo recursivamente.
O algoritmo termina quando não há mais vértices adjacentes a s
que não foram visitados ainda.
⚔️ DFS vs BFS
Podemos ver a diferença entre os dois algoritmos no gif abaixo:
Como podemos ver a DFS, explora o máximo possível de um caminho antes de voltar, enquanto a BFS explora em "camadas".
🧑🏫 Exercícios
Last updated