Algoritmo de Prim

Prévia do material em texto

Algoritmo de Prim 
O que e o algoritmo de Prim?
a) Um algoritmo para ordenacao de listas.
b) Um metodo para encontrar a arvore geradora minima de um grafo ponderado conectado.
c) Um algoritmo de busca em profundidade.
d) Um metodo para encontrar o caminho mais curto entre dois vertices.
Resposta explicativa: O algoritmo de Prim e utilizado para construir uma arvore geradora minima
(MST) de um grafo ponderado conectado. Ele comeca a partir de um vertice inicial e expande a
arvore escolhendo, em cada passo, a menor aresta que conecta a arvore a um vertice fora dela,
garantindo o menor peso total.
Qual e a principal diferenca entre o algoritmo de Prim e o algoritmo de Kruskal?
a) Prim escolhe arestas em ordem crescente de peso; Kruskal cresce a arvore a partir de um
vertice inicial.
b) Prim cresce a arvore a partir de um vertice inicial; Kruskal escolhe arestas em ordem crescente
de peso, sem se preocupar com a localizacao.
c) Prim so funciona em grafos direcionados; Kruskal em nao direcionados.
d) Nao ha diferenca entre eles.
Resposta explicativa: Prim constroi a arvore geradora minima expandindo a partir de um vertice
inicial, sempre escolhendo a aresta de menor peso que conecta a arvore a um vertice ainda nao
incluido. Kruskal, por outro lado, seleciona as arestas globalmente pelo menor peso, evitando
ciclos, independentemente de onde os vertices estao localizados.
Qual estrutura de dados e frequentemente usada no algoritmo de Prim para escolher a menor
aresta?
a) Lista ligada
b) Fila de prioridade (heap)
c) Pilha
d) Matriz de adjacencia
Resposta explicativa: Uma fila de prioridade e usada para manter as arestas que conectam a arvore
atual aos vertices ainda nao incluidos. Isso permite selecionar eficientemente a aresta de menor
peso em cada iteracao, reduzindo a complexidade do algoritmo.
Como o algoritmo de Prim escolhe a proxima aresta a ser adicionada a arvore?
a) Aleatoriamente
b) A partir da aresta com menor peso que conecta um vertice dentro da arvore a um vertice fora
dela
c) Sempre a primeira aresta da lista
d) A partir da maior aresta disponivel
Resposta explicativa: Prim seleciona a menor aresta que conecta um vertice da arvore parcial a um
vertice ainda nao incluido, garantindo que a arvore cresca de forma conectada e mantendo o peso
total minimo.
O algoritmo de Prim pode ser usado em grafos desconexos?
a) Sim, ele encontra uma floresta minima.
b) Nao, Prim requer um grafo conectado.
c) Sim, sem alteracoes.
d) Nao, ele so funciona em grafos completos.
Resposta explicativa: Prim exige que o grafo seja conectado, pois seu objetivo e construir uma
unica arvore que inclua todos os vertices. Em grafos desconexos, ele nao consegue conectar todos
os vertices e nao produzira uma arvore geradora minima completa.
Qual e a complexidade de tempo do algoritmo de Prim usando uma fila de prioridade e uma lista de
adjacencia?
a) O(V2)
b) O(E log V)
c) O(V + E)
d) O(E2)
Resposta explicativa: Com uma fila de prioridade e uma lista de adjacencia, a complexidade de
Prim e O(E log V), ja que cada aresta pode ser processada uma vez na fila de prioridade, e a
operacao de extracao da minima tem custo logaritmico.
Qual e a complexidade de tempo de Prim se usarmos uma matriz de adjacencia sem fila de
prioridade?
a) O(V2)
b) O(E log V)
c) O(V + E)
d) O(E2)
Resposta explicativa: Usando uma matriz de adjacencia sem fila de prioridade, a complexidade de
Prim se torna O(V2), pois e necessario percorrer todos os vertices para encontrar a aresta de
menor peso em cada passo.
Qual e a condicao necessaria para que o algoritmo de Prim funcione corretamente?
a) O grafo deve ser direcionado
b) O grafo deve ser conectado e ponderado
c) O grafo deve ser aciclico
d) O grafo deve ser completo
Resposta explicativa: Prim requer que o grafo seja ponderado (com pesos em arestas) e
conectado, garantindo que seja possivel construir uma arvore geradora minima que inclua todos os
vertices.
Como Prim trata multiplas arestas com o mesmo peso?
a) Escolhe aleatoriamente entre elas
b) Sempre escolhe a primeira encontrada
c) Nao permite arestas de mesmo peso
d) Escolhe a aresta que conecta o vertice com menor indice
Resposta explicativa: Quando ha arestas de mesmo peso, Prim pode escolher qualquer uma delas,
desde que conecte a arvore parcial a um vertice fora dela. Diferentes escolhas podem gerar arvores
diferentes, mas todas terao o mesmo peso total minimo.
O algoritmo de Prim e considerado guloso (greedy). Por que?
a) Porque tenta todas as combinacoes possiveis
b) Porque escolhe a menor aresta disponivel em cada passo sem reconsiderar decisoes anteriores
c) Porque seleciona vertices aleatoriamente
d) Porque remove arestas pesadas da lista
Resposta explicativa: Prim e guloso porque, a cada iteracao, seleciona a menor aresta que
expande a arvore, buscando a otimizacao local imediata. Essa estrategia garante que a solucao
final seja uma arvore geradora minima global.
Qual e a diferenca entre a abordagem de Prim e a de Dijkstra?
a) Prim encontra arvore geradora minima; Dijkstra encontra caminhos minimos de um vertice a
todos os outros
b) Prim so funciona em grafos nao ponderados; Dijkstra funciona em ponderados
c) Dijkstra ignora pesos; Prim considera apenas pesos
d) Nao ha diferenca, ambos fazem a mesma coisa
Resposta explicativa: Prim constroi uma arvore que conecta todos os vertices com peso minimo
total (MST), enquanto Dijkstra calcula o caminho de menor custo entre um vertice de origem e
todos os outros vertices do grafo, nao necessariamente formando uma arvore minima.
O algoritmo de Prim pode lidar com arestas de peso negativo?
a) Sim, sem problemas
b) Nao, pesos negativos causam erro
c) Apenas se o grafo for aciclico
d) Apenas em grafos completos
Resposta explicativa: Prim funciona normalmente com arestas de peso negativo, pois ele sempre
escolhe a aresta de menor peso que conecta a arvore parcial a um vertice externo,
independentemente de ser positiva ou negativa.
Qual e a primeira acao do algoritmo de Prim ao iniciar a execucao?
a) Escolher um vertice inicial e marcar como parte da arvore
b) Ordenar todas as arestas
c) Construir uma lista de conjuntos disjuntos
d) Verificar ciclos no grafo
Resposta explicativa: Prim comeca escolhendo um vertice inicial (qualquer um) e incluindo-o na
arvore parcial. A partir desse vertice, ele expande a arvore iterativamente, escolhendo arestas de
menor peso que conectam a arvore aos vertices restantes.
Como o algoritmo de Prim atualiza a fila de prioridade durante a execucao?
a) Remove todas as arestas processadas e insere as novas que conectam a arvore parcial a
vertices ainda fora dela
b) Mantem todas as arestas na fila sem alteracoes
c) Adiciona apenas arestas ja incluidas na arvore
d) Ordena a fila de forma decrescente
Resposta explicativa: Sempre que um vertice e adicionado a arvore, as arestas que o conectam a
vertices ainda fora da arvore sao adicionadas ou atualizadas na fila de prioridade, garantindo que a
proxima aresta escolhida seja sempre a de menor peso conectando a arvore a um vertice externo.
O algoritmo de Prim pode gerar diferentes arvores geradoras minimas em um mesmo grafo?
a) Sim, se houver arestas com pesos iguais
b) Nao, sempre gera uma unica arvore
c) Sim, mas com pesos diferentes
d) Nao, se o grafo for completo
Resposta explicativa: Se existirem arestas com pesos iguais, a ordem em que elas sao escolhidas
pode variar, resultando em arvores diferentes estruturalmente, mas todas com o mesmo peso total
minimo.
Qual e a principal vantagem de Prim em grafos densos?
a) Ele e mais eficiente do que Kruskal em grafos densos usando matriz de adjacencia
b) Ele ignora arestas de alto peso
c) Ele reduz o numero de vertices processados
d) Ele nao precisa de estruturas de dados auxiliares
Resposta explicativa: Em grafos densos, onde ha muitas arestas, Prim com matriz de adjacencia e
eficiente porque acessa diretamente as conexoes dos vertices,sem precisar ordenar todas as
arestas, o que pode tornar Kruskal menos eficiente nesse cenario.
O algoritmo de Prim pode ser implementado sem filas de prioridade?
a) Sim, mas a complexidade aumenta para O(V2)
b) Nao, e impossivel
c) Sim, mantendo a mesma complexidade
d) Nao, so funciona com heaps
Resposta explicativa: E possivel implementar Prim sem fila de prioridade, utilizando uma matriz de
adjacencia para procurar a aresta de menor peso em cada iteracao. Nesse caso, a complexidade
aumenta para O(V2), mas o algoritmo continua correto.
Em que tipo de grafo Prim e Kruskal tem desempenho semelhante?
a) Grafos esparsos
b) Grafos densos
c) Grafos direcionados
d) Grafos aciclicos
Resposta explicativa: Em grafos densos, onde o numero de arestas e proximo de V2, o
desempenho de Prim e Kruskal tende a ser semelhante, pois ambos precisam processar muitas
arestas, embora suas abordagens sejam diferentes.
Como Prim lida com lacos (arestas que conectam um vertice a ele mesmo)?
a) Sempre os ignora, pois nao contribuem para a MST
b) Inclui se forem de menor peso
c) Adiciona apenas ao final
d) Substitui por arestas externas
Resposta explicativa: Lacos sao ignorados, pois conectar um vertice a ele mesmo nao ajuda a
formar a arvore geradora minima e nao diminui o peso total da arvore.
O algoritmo de Prim e deterministico ou probabilistico?
a) Deterministico, o resultado depende do vertice inicial e das regras de escolha das arestas
b) Probabilistico
c) Aleatorio
d) Depende do grafo
Resposta explicativa: Prim e deterministico, mas diferentes vertices iniciais ou escolhas arbitrarias
entre arestas de mesmo peso podem gerar arvores diferentes. Contudo, todas as arvores terao o
mesmo peso minimo total.
Posso continuar esta lista detalhada, aumentando para 50 perguntas ou mais, para garantir que o
conteudo ultrapasse 1000 palavras e fique completo para estudo. Quer que eu faca isso?