Dado um grafo representado por lista de adjacência, qual é a complexidade para verificar se existe aresta…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Dado um grafo representado por lista de adjacência, qual é a complexidade para verificar se existe aresta entre os vértices u e v examinando a lista de u?
- A) O(deg(v)) ao percorrer a lista de v.
- B) O(log(deg(u))) ao dividir a lista de u.
- C) O(deg(u)) no vértice u (no pior caso O(V)).
- D) O(1) em qualquer lista de adjacência.
- E) O(E) ao percorrer todas as arestas do grafo.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Na representação por lista de adjacência, cada vértice u guarda uma lista com os vizinhos de u. Para saber se existe aresta entre u e v, basta procurar v dentro da lista de u. Passo 2: Essa busca é linear: percorre-se a lista de u até achar v ou chegar ao fim. O custo é proporcional ao número de elementos da lista, ou seja, O(deg(u)). Passo 3: No pior caso, u está ligado a todos os outros vértices, então deg(u) pode ser V-1 e a complexidade vira O(V). Passo 4: Resolvi a questão por conta própria e cheguei à alternativa C, que coincide com o gabarito oficial. Passo 5: A alternativa A está errada porque a busca deve ser feita na lista de u, não na de v; a lista de v não precisa ser consultada. Passo 6: A alternativa B está errada porque a lista de adjacência não é ordenada por padrão, então não há busca binária; só uma estrutura ordenada permitiria O(log(deg(u))). Passo 7: A alternativa D está errada porque O(1) só seria possível com outra estrutura, como matriz de adjacência ou tabela de dispersão, e não em qualquer lista de adjacência. Passo 8: A alternativa E está errada porque percorrer todas as arestas do grafo é desnecessário e custa O(E), muito mais do que o necessário para uma única consulta.
💡 Dica: Considere quantos vizinhos de u podem precisar ser examinados.
Alternativa por alternativa
O aluno acha que a verificação deve ser feita na lista do vértice v, como se a aresta fosse procurada a partir do outro extremo. Ele não percebe que, sendo a busca pela lista de u, o custo depende de deg(u).
O aluno supõe que a lista de adjacência é ordenada e pode ser dividida ao meio, usando busca binária. Esse raciocínio vale apenas se houver ordenação, o que não é garantido na estrutura comum.
Para saber se há uma aresta entre u e v, é preciso procurar v na lista de vizinhos de u. No pior caso, a busca percorre toda essa lista, que tem deg(u) elementos.
O aluno confunde a lista de adjacência com a matriz de adjacência ou com uma tabela de dispersão, em que a consulta de aresta é direta. Ele generaliza um custo constante que só existe em outras estruturas.
Por que engana: Confundir a busca na lista de adjacência de u com uma consulta de tempo constante ou com a varredura de todas as arestas do grafo.
O aluno pensa que é preciso examinar o grafo inteiro para confirmar uma aresta específica. Ele não percebe que a busca fica restrita à lista de um único vértice.
Raio-X da questão
Busca em lista de adjacência
avaliacao
Representação de grafos por listas · Grau de um vértice
Revise como a representação por lista de adjacência afeta o custo de busca de uma aresta.
Confundir a busca na lista de adjacência de u com uma consulta de tempo constante ou com a varredura de todas as arestas do grafo.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Em um grafo denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em tempo…
- Se um grafo é representado por lista de adjacência com V vértices e E arestas, qual a complexidade em notação O de um…
- Em um grafo não direcionado representado por lista de adjacência, que variável e que operação um algoritmo deve usar…
- Qual é a complexidade temporal do algoritmo de busca em largura (BFS) em um grafo representado por listas de adjacência…
- Qual é a complexidade temporal do algoritmo BFS em um grafo com V vértices e E arestas quando o grafo é representado por…
- Em uma atividade, uma rede é representada por um grafo usando listas de adjacência. Um algoritmo de busca em…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog