Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de…

Questão

Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de adjacência, compute o número de componentes conexas. Indique as variáveis-chave e a complexidade temporal.

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

Resposta esperada

Pseudocódigo: visited[v]=false for all v components=0 for v in V: if not visited[v]: components+=1 stack=[v] while stack: u=stack.pop() if not visited[u]: visited[u]=true for w in adj[u]: if not visited[w]: stack.push(w) return components Variáveis-chave: visited[], stack (ou fila), components, adj. Complexidade: O(n + m) considerando n vértices e m arestas.

Explicação

O algoritmo utiliza uma abordagem de busca em profundidade (DFS) para explorar todos os vértices de um grafo, marcando-os como visitados. Cada vez que um novo vértice não visitado é encontrado, uma nova componente conexa é identificada, incrementando o contador. A complexidade O(n + m) reflete a necessidade de visitar todos os vértices e arestas, garantindo que todas as partes do grafo sejam consideradas.

Raio-X da questão

Questões parecidas com resolução

• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não…
• Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em uma rede…
• Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência dos bairros…
• Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência…

Todas as questões de Programação - Projetos com programação