O seguinte pseudocódigo é uma forma simplificada do algoritm...

Próximas questões
Com base no mesmo assunto
Q113263 Engenharia de Automação
O seguinte pseudocódigo é uma forma simplificada do algoritmo de busca depht first num grafo direcionado. O procedimento principal dfs(N,Adj) recebe como entrada o inteiro N e a matriz Adj, de dimensões NxN. Adj(u,v) representa o elemento da linha u e coluna v da matriz Adj. O procedimento dfs(N,Adj) faz a chamada recursiva do procedimento dfs-visit(u), onde u é um inteiro de 1 a N. Ao término dos dois procedimentos, os vetores cor e b, indexados pelos inteiros u de 1 até N, são preenchidos de acordo com a regra de busca prevista no algoritmo

Alternativas

Comentários

Veja os comentários dos nossos alunos

  1. Começamos pelo vértice 1 (índice 0):
  • Visitamos o vértice 1.
  • Visitamos os vértices 2 e 3.
  • Não visitamos os vértices 4, 5 e 6 a partir do vértice 3 porque o grafo está direcionado para os vértices 2 e 3 apenas.
  1. Partimos então do vértice 2 (índice 1):
  • Visitamos o vértice 2.
  • Visitamos o vértice 3.
  • Não visitamos os vértices 4, 5 e 6 a partir do vértice 3 por já terem sido visitados.
  1. Passamos para o vértice 4 (índice 3):
  • Visitamos o vértice 4.
  • Não visitamos o vértice 5 a partir do vértice 4 por já ter sido visitado.
  1. Agora partimos do vértice 5 (índice 4):
  • Visitamos o vértice 5.
  • Visitamos o vértice 6.

O vetor que armazena os predecessores dos vértices visitados durante o DFS seria b=[0,1,2,3,3,5] , representando os predecessores dos vértices 1 a 6, respectivamente.

Dessa forma, considerando o percurso da busca em profundidade, a sequência correta de predecessores é b=[0,1,2,3,3,5] , e não b=[0,1,2,3,0,5] .

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo