Projete um algoritmo em pseudocódigo que, dado um grafo dirigido que modela rotas entre cidades (vértices)…

Questão

Projete um algoritmo em pseudocódigo que, dado um grafo dirigido que modela rotas entre cidades (vértices), uma origem s, um destino t e uma lista de vértices bloqueados (não atravessáveis), determine se existe um caminho simples de s a t que não passe por vértices bloqueados. Use termos como grafo, nó, aresta, algoritmo e variável.

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

Resposta esperada

PSEUDOCÓDIGO: Entrada: grafo G(V,E) como listas de adjacência, vértices s,t, conjunto Bloqueados Função ExisteCaminho(G,s,t,Bloqueados): if s in Bloqueados or t in Bloqueados: return falso criar fila/stack ou usar DFS recursivo criar conjunto Visitado vazio usar pilha P e empilhar s; marcar Visitado[s]=true while P não vazia: v = desempilhar(P) if v == t: return verdadeiro for cada (v->u) em adj[v]: if u not in Bloqueados and not Visitado[u]: Visitado[u]=true empilhar(P,u) return falso EXPLICAÇÃO E CORREÇÃO: O algoritmo realiza busca (DFS ou BFS) desde s, ignorando vértices do conjunto Bloqueados. Marcar Visitado evita ciclos e garante caminho simples (não repete vértices). Se t for alcançado retorna verdadeiro; caso contrário, não existe caminho permitido. Complexidade: O(n + m) em listas de adjacência, pois cada vértice e cada aresta válida são processados no máximo uma vez.

Explicação

O algoritmo utiliza uma abordagem de busca em profundidade (DFS) ou largura (BFS) para explorar o grafo, evitando vértices bloqueados e garantindo que não haja repetições de vértices, o que assegura um caminho simples. A marcação de vértices visitados impede a formação de ciclos e garante que cada vértice e aresta sejam processados apenas uma vez, resultando em uma complexidade eficiente. A verificação se o destino é alcançado permite determinar a existência de um caminho válido entre as cidades.

Raio-X da questão

Questões parecidas com resolução

• Antes de ir à feira, Bia anotou: pão, bananas e sabonete. Que objeto do dia a dia é esse e como Bia pode mudar a ordem…
• No mapa da sala, há círculos para a porta, a mesa da professora, a estante e o quadro. As linhas ligam porta-mesa…
• — A mensagem não chegou ao abrigo do bairro Serra — avisou uma moradora pelo rádio comunitário. Após a enchente, a…
• — O painel da praça ficou cheio de bilhetes sobre lâmpadas apagadas — observou Caio, voluntário do bairro. Em cada…
• — Quem contracena com Caio? — perguntou a responsável pelo grupo de teatro do bairro. Para organizar os próximos…
• Por que uma mesma caminhada pela área verde pode produzir fichas tão diferentes? Para organizar os registros de…

Todas as questões de Listas e grafos