Pesquisa Grafos

UNIVERSIDADE DE UBERABA
LUCAS FREITAS SISCONETTO
PEDRO DUARTE

GRAFOS: BUSCA EM LARGURA, PROFUNDIDADE E MAIS UTILIZADOS

UBERABA – MG
2015
LUCAS FREITAS SISCONETTO
PEDRO DUARTE

GRAFOS: BUSCA EM LARGURA, PROFUNDIDADE E MAIS UTILIZADOS

Trabalho apresentado ao professor André Luís Silva de Paula, como pré-requisito para aprovação na disciplina de Estruturas de Dados II.

UBERABA – MG
2015

Busca em largura (BFS)

Um algoritmo de busca é um algoritmo que examina, sistematicamente, os vértices e os arcos de um digrafo. Cada arco é examinado no máximo uma vez. Depois de examinar a ponta inicial de um arco, o algoritmo percorre o arco e examina sua ponta final.
Há muitas maneiras de organizar a busca. Cada estratégia de busca é caracterizada pela ordem em que os vértices são examinados. Esta página introduz a busca em largura (= breadth-first search = BFS). Essa estratégia, também conhecida como busca bfs, está intimamente relacionada com os conceitos de distância e caminho mínimo. Quando aplicada a uma arborescência, por exemplo, a busca bfs faz uma varredura por níveis.

No início de cada iteração valem as seguinte propriedades: todo vértice que está na fila já foi visitado; se um vértice v já foi visitado mas algum de seus vizinhos ainda não foi visitado, então v está na fila.
(Dizemos que um vértice x já foi visitado se e somente se lbl[x] é diferente de -1.)
Observe que a fila foi dimensionada corretamente na linha QUEUEinit( G->V): Cada vértice de G entra no máximo uma vez na fila e portanto a fila não precisa de mais do que G->V posições.

Busca em profundidade (DFS)

Um algoritmo de busca (ou varredura) é um algoritmo que visita, sistematicamente, todos os vértices e todos os arcos de um digrafo. Cada arco é visitado uma e uma só vez. Depois de visitar a ponta inicial de um arco, o algoritmo percorre o arco e visita sua ponta final.
Há muitas maneiras de fazer uma tal busca. Cada