Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado conectado e um vértice raiz…

Questão

Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado conectado e um vértice raiz, construa a árvore de busca em largura (BFS tree) e retorne o nível (distância em número de arestas) de cada vértice em relação à raiz. Explique as variáveis principais.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: function BFS_tree(grafo, raiz): para cada v em grafo.vertices: nivel[v] = -1 visitado[v] = false pai[v] = null fila = novaFila() visitado[raiz] = true nivel[raiz] = 0 fila.enqueue(raiz) enquanto not fila.vazia(): u = fila.dequeue() para cada v em grafo.adj[u]: se not visitado[v]: visitado[v] = true pai[v] = u nivel[v] = nivel[u] + 1 fila.enqueue(v) retornar pai, nivel Variáveis principais: - fila: controla a ordem de exploração por níveis (FIFO). - visitado[v]: booleano que evita revisitar vértices e previne ciclos. - nivel[v]: inteiro com a distância em número de arestas desde a raiz. - pai[v]: referência ao antecessor na árvore de busca (opcional, constrói a BFS tree). Complexidade: O(n + m) onde n = número de vértices e m = número de arestas.

Explicação

O algoritmo utiliza a abordagem de busca em largura, que explora todos os vértices em um nível antes de passar para o próximo, garantindo que a distância em arestas de cada vértice em relação à raiz seja corretamente calculada. As variáveis principais, como a fila e os arrays de visitados, níveis e pais, organizam a exploração e armazenamento das informações necessárias para construir a árvore de busca. A complexidade O(n + m) reflete a eficiência do algoritmo, uma vez que cada vértice e aresta é processado uma única vez.

Raio-X da questão

Questões parecidas com resolução

• Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…
• Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de articulação (cut…
• Projete um algoritmo em pseudocódigo que, dada uma árvore enraizada representada por nós com referências a filhos e uma…
• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de adjacência…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…

Todas as questões de Programação - Programação usando grafos e árvores