Questão 861542

O pseudocódigo abaixo é uma forma simplificada de um algoritmo de busca breadth-first de um grafo direcionado. O procedimento bfs(N,Adj) recebe como entradas o inteiro N e a matriz NxN Adj, significando, respectivamente, o total de vértices do grafo, sendo estes numerados de 1 até N, e a matriz de adjacência. Se Adj(u,v) = 1, existe um arco direcionado que liga o vértice u ao vértice v. O procedimento preenche os vetores cor e , indexados de 1 até N. Durante o procedimento de busca, utiliza-se a fila Q, do tipo FIFO (First-In-First-Out). O procedimento ENQUEUE(Q,u) insere o elemento u ao final da fila Q e o procedimento u <-DEQUEUE(Q) remove o elemento u do início da fila Q.

bfs(N,Adj)

Para u de 1 até N faça

cor[u] <- branco;

[u] <- 0;

Fim-Para

cor[1] <- 0;

Q <- ∅;

ENQUEUE(Q,1);

Enquanto Q ≠ ∅ faça

u <- DEQUEUE(Q);

Para v de 1 até N faça

Se Adj(u,v) = 1 e cor[v] = branco faça

ENQUEUE(Q,v);

cor[v] <- cinza;

[v] <- u;

Fim-Se

Fim-Para

cor[u] <- preto;

Fim-Enquanto

Fim

O resultado do vetor após a aplicação do procedimento bfs, com entradas N = 4 e Adj = \(\begin{vmatrix} 0 & 1 &1 &0 \\ 0 &0 &1 & 0 \\ 0 &0 &0 &1 \\ 1 & 1 & 0 &0 \\ \end{vmatrix}\) \(\begin{vmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 \end{vmatrix}\)