Atps Michele 1

FACULDADE ANHANGUERA EDUCACIONAL –
FAC II
UNIDADE DE CAMPINAS

Análise e Complexidade de Algoritmos

Jovane Marques Brandão Patrick Cabral Nascimento Michele Alcântara da Silva

Campinas 2015
Etapa 3
Passo 1

inicialize v:gin para todos os vértices (com DFS); rotulo G := 0; para i:=1 até n faça se vi
:gin = 0 então coloque vi na fila; repita remova um vértice v da fila; rotulo G := rotulo G + 1;
v.rotulo := rotulo G; para toda aresta (v; w) faça
w.gin := w.gin – 1; se w.gin = 0 então coloque w na fila; até que a fila esteja vazia

Passo 2

Passo 3

A
B
C
D
E
A

3

12
B

3
2
7
C

2 D

E

6

Etapa 4

Um algoritmo de busca (ou varredura) é um algoritmo que visita, sistematicamente, todos os vértices e todos osarcos 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 estratégia de busca é caracterizada pela ordem em que os vértices são visitados. A busca em largura começa por um vértice, digamos s, especificado pelo usuário. O algoritmo visita s, depois visita todos os vértices que estão à distância 1 de s, depois todos os vértices que estão à distância 2 de s, e assim por diante. Para implementar essa ideia, o algoritmo usa uma fila de vértices. Essa fila contém todos os vértices já visitados cujos vizinhos ainda não foram todos visitados. A fila é manipulada por alguma funções como por exemplo: QUEUEinit, QUEUEput, QUEUEget, QUEUEempty e QUEUEfree. A primeira cria uma fila vazia, a segunda insere um vértice na fila, a terceira retira um vértice da fila, a quarta verifica se a fila está vazia e a última libera o espaço ocupado pela fila.A ordem em que os vértices são visitados é registrada num vetor lbl indexado pelos vértices. Se v é o k-ésimo vértice visitado então lbl[v] vale k-1.A