Busca em largura (breadth first search)

MarioRafael CoelhoMauricioAtila

BUSCA EM LARGURA (BREADTH-FIRST

SEARCH)

INTRODUÇÃO

É um algoritmo que recupera informações armazenadas dentro de alguma estrutura de dados.

DEFINIÇÃO DE ALGORITMO DE BUSCA

EXEMPLOS DE ALGORITMOS DE BUSCA

Busca SequencialBusca Binária Busca em

profundidadeBusca em Largura

A*Dijkstra

É um conjunto de vértices e um conjunto de arestas que conectam qualquer par de vértices.

ESTRUTURA DE DADOS: GRAFO

Busca em largura é um algoritmo de busca em grafos utilizado para realizar uma busca ou travesia num grafo e estrutura de dados do tipo árvore. Intuitivamente, você começa pelo vértice raiz e explora todos os vértices vizinhos. Então, para cada um desses vértices mais próximos, exploramos os seus vértices vizinhos inexplorados e assim por diante, até que ele encontre o alvo da busca. Em outras palavras, podemos dizer que o algoritmo realiza uma busca exaustiva num grafo passando por todas as arestas e vértices do grafo.

ALGORITMO BUSCA EM LARGURA

CLASSE GRAFO

def __init__(self, name_='', directed=False, copy_of=None):

if isinstance(copy_of, Graph): self.copy(copy_of) else: self.name = name_ self.nodes = {} self.directed = directed

def getWeight(self, n1, n2):

if n1 in self and n2 in self: if n2 in self.nodes[n1]: return self.nodes[n1][n2] elif n1 == n2: return 0 return float("inf") return False

def addEdge(self, n1, n2, weight=1):if not n1 in self.nodes:

self.nodes[n1] = {}self.nodes[n1][n2] = weight

if self.directed is False:if not n2 in self.nodes:

self.nodes[n2] = {}self.nodes[n2][n1] = weight

def add(self, n, G = None):if not n in self:

self.nodes[n] = {}if G:

if n in G: self.nodes[n]= G.getEdges(n)

ALGORITMO BFS

BUSCA EM LARGURA

É um algoritmo de busca em grafos utilizado para realizar uma busca ou travessia num grafo e estrutura de dados do tipo árvore.

A ideia é começar pelo vértice raiz e explora todos os vértices vizinhos. Então, para cada um desses vértices mais próximos, exploramos os seus vértices vizinhos inexplorados e assim por diante, até que ele encontre o alvo da busca.

BUSCA EM LARGURA

Realiza uma busca exaustiva num grafo passando por todas as arestas e vértices do grafo.

Deve garantir que nenhum vértice ou aresta será visitado mais de uma vez, então utiliza uma fila para tal.

BUSCA EM LARGURA

Cinza = esta na fila

Preto = já foi inspecionado

Complexidade de tempo: O(|E| + |V|).

Complexidade de espaço: O(|V|)

Sendo |E| = arestas

Sendo |V| = vértices

BUSCA EM LARGURA

Legenda:F - Fila(FIFO)G - Grafo s, v, w representam vértices do grafo onde listDeAdja

representa a lista de adjacência de um vértice

BUSCA EM LARGURA

BuscaEmLarguraescolha uma raiz s de Gmarque sinsira s em Fenquanto F não está vazia faça

veja v o primeiro vértice de Fpara cada w ∈ listaDeAdja de v faça

se w não está marcado entãovisite aresta entre v e w

marque w insira w em Fsenão se w ∈ F então visite aresta entre v e wfim se

fim pararetira v de F

fim enquanto

CÓDIGO PYTHON

def bfs (self,raiz):fila = []vertMarcados = []tamVertMarcados = 0

vertMarcados.append(raiz)tamVertMarcados += 1fila.append(raiz)

while(len(fila)>0):vert1 = fila[0]listaAdj = self.getEdges(vert1)for i in listaAdj:

if(i not in vertMarcados):vertMarcados.append(i)tamVertMarcados += 1fila.append(i)

fila.pop(0)

Rafael Coelho: 20151015020304

Átila Bastos:20151015020045

Mário Matheus:20151015020240

Maurício Torquato: 20151015020274

OBRIGADO!