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

• Descreva um algoritmo em pseudocódigo que, dado um grafo dirigido acíclico e dois vértices s e t, encontra um caminho de…
• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
• Elabore um algoritmo em pseudocódigo que, dado um grafo representado por lista de adjacência e dois vértices (origem…
• Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
• Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de…

Todas as questões de Listas e grafos