691081_Algoritmos de percorrimento

Prévia do material em texto

Algoritmos de Percorrimento em Grafos 
 
São algoritmos que permitem percorrer o grafo em uma sequência sistemática. 
 
Busca em profundidade 
 
Para cada componente conexo do grafo faça: 
1-Formar uma fila de um elemento consistindo de um nó escolhido aleatoriamente. 
2-Até que todos os nós tenham sido visitados faça: 
 2.1-Marque o primeiro elemento da fila como visitado 
2.2-Remova o primeiro elemento da fila; 
2.3-Insira (em ordem aleatória) todos os vizinhos do primeiro elemento da fila (o 
removido) que não tenham sido visitados e que não estejam na fila, na cabeça da fila. 
 
Exemplo 
 
 
 
Passo do algoritmo Nó 
visitado 
Fila 
1 - 0 (1º componente) 
2.1 0 0 
2.2 - VAZIA 
2.3 - 1-4-7-8 
2.1 1 1-4-7-8 
2.2 - 4-7-8 
2.3 - 2-4-7-8 
2.1 2 2-4-7-8 
2.2 - 4-7-8 
2.3 - 3-5-4-7-8 
2.1 3 3-5-4-7-8 
2.2 - 5-4-7-8 
2.3 - 6-5-4-7-8 
2.1 6 6-5-4-7-8 
2.2 - 5-4-7-8 
2.3 - 5-4-7-8 
2.1 5 5-4-7-8 
2.2 - 4-7-8 
2.3 - 4-7-8 
2.1 4 4-7-8 
2.2 - 7-8 
2.3 - 9-4-7-8 
2.1 9 9-7-8 
2.2 - 7-8 
2.3 - 7-8 
2.1 7 7-8 
2.2 - 8 
2.3 - A-8 
2.1 A A-8 
2.2 - 8 
2.3 - 8 
2.1 8 8 
2.2 - VAZIA 
2.3 - VAZIA (Fim 1º 
componente) 
1 - B (2º componente) 
2.1 B B 
2.2 - VAZIA 
2.3 - D-F 
2.1 D D-F 
2.2 - F 
2.3 - F 
2.1 F F 
2.2 - VAZIA 
2.3 - VAZIA (Fim 2º 
componente) 
1 - C(3º componente) 
2.1 C C 
2.2 - VAZIA 
2.3 - VAZIA (Fim 3º 
componente) 
 
 
Busca em largura (ou amplitude) 
 
Para cada componente conexo do grafo faça: 
1-Formar uma fila de um elemento consistindo de um nó escolhido aleatoriamente. 
2-Até que todos os nós tenham sido visitados faça: 
 2.1-Marque o primeiro elemento da fila como visitado 
2.2-Remova o primeiro elemento da fila; 
2.3-Insira (em ordem aleatória) todos os vizinhos do primeiro elemento da fila (o 
removido) que não tenham sido visitados e que não estejam na fila, no final da fila. 
 
Exemplo 
 
 
Passo do algoritmo Nó 
visitado 
Fila 
1 - 0 (1º componente) 
2.1 0 0 
2.2 - VAZIA 
2.3 - 1-4-7-8 
2.1 1 1-4-7-8 
2.2 - 4-7-8 
2.3 - 4-7-8-2 
2.1 4 4-7-8-2 
2.2 - 7-8-2 
2.3 - 7-8-2-9 
2.1 7 7-8-2-9 
2.2 - 8-2-9 
2.3 - 8-2-9-A 
2.1 8 8-2-9-A 
2.2 - 2-9-A 
2.3 - 2-9-A 
2.1 2 2-9-A 
2.2 - 9-A 
2.3 - 9-A-3-5 
2.1 9 9-A-3-5 
2.2 - A-3-5 
2.3 - A-3-5 
2.1 A A-3-5 
2.2 - 3-5 
2.3 - 3-5 
2.1 3 3-5 
2.2 - 5 
2.3 - 5-6 
2.1 5 5-6 
2.2 - 6 
2.3 - 6 
2.1 6 6 
2.2 - VAZIA 
2.3 - VAZIA (Fim 1º 
componente) 
1 - B (2º componente) 
2.1 B B 
2.2 - VAZIA 
2.3 - D-F 
2.1 D D-F 
2.2 - F 
2.3 - F 
2.1 F F 
2.2 - VAZIA 
2.3 - VAZIA(fim 2º 
componente) 
1 - C(3º componente) 
2.1 C C 
2.2 - VAZIA 
2.3 - VAZIA (fim 3º 
componente)