Algoritmo de Prim

Prévia do material em texto

Algoritmo de Prim 
O que o Algoritmo de Prim busca encontrar em um grafo ponderado e nao direcionado?
a) Um ciclo minimo.
b) Um caminho hamiltoniano.
c) Uma arvore geradora minima.
d) Uma sequencia de vertices desconexos.
Resposta explicativa: O Algoritmo de Prim tem como objetivo construir uma arvore geradora minima
(AGM), conectando todos os vertices de um grafo de forma que o custo total das arestas seja o
menor possivel e sem formar ciclos.
Como o Algoritmo de Prim inicia seu processo de construcao da arvore geradora minima?
a) Selecionando todas as arestas de menor peso de uma vez.
b) Escolhendo um vertice inicial aleatoriamente.
c) Ordenando todas as arestas antes de comecar.
d) Eliminando ciclos do grafo antes da execucao.
Resposta explicativa: O algoritmo comeca escolhendo um vertice inicial, e a partir dele vai
adicionando gradualmente as arestas de menor peso que conectam vertices ainda nao incluidos na
arvore.
O Algoritmo de Prim e classificado como qual tipo de algoritmo?
a) Aleatorio.
b) Guloso (Greedy).
c) Recursivo.
d) Probabilistico.
Resposta explicativa: Prim e um algoritmo guloso, pois em cada passo escolhe a aresta de menor
custo possivel que expande a arvore de forma localmente otima, resultando em uma solucao
globalmente otima.
O que impede o Algoritmo de Prim de formar ciclos durante sua execucao?
a) O uso da estrutura de uniao e busca (Union-Find).
b) O controle dos vertices ja visitados.
c) A ordenacao previa das arestas.
d) A utilizacao de pesos negativos.
Resposta explicativa: O algoritmo mantem um conjunto de vertices ja incluidos na arvore. Ele so
adiciona arestas que conectam um vertice dentro da arvore a outro que ainda nao foi visitado, o
que evita a formacao de ciclos.
Qual estrutura de dados e comumente usada para otimizar o desempenho do Algoritmo de Prim?
a) Lista encadeada.
b) Fila de prioridade (heap).
c) Pilha.
d) Tabela hash.
Resposta explicativa: Uma fila de prioridade e frequentemente utilizada para selecionar
rapidamente a aresta de menor peso que conecta o conjunto de vertices ja visitados com o restante
do grafo, melhorando a eficiencia do algoritmo.
Qual e a complexidade de tempo do Algoritmo de Prim quando implementado com uma fila de
prioridade baseada em heap binario?
a) O(V2)
b) O(E log V)
c) O(V log V)
d) O(E2)
Resposta explicativa: A complexidade do algoritmo e O(E log V), onde E representa o numero de
arestas e V o numero de vertices, devido as operacoes de insercao e extracao na fila de prioridade.
Qual e o principal criterio usado para escolher a proxima aresta a ser adicionada no Algoritmo de
Prim?
a) A que conecta dois vertices ainda nao visitados.
b) A aresta mais pesada disponivel.
c) A aresta de menor peso que conecta a arvore com um novo vertice.
d) A aresta que gera o menor ciclo possivel.
Resposta explicativa: O algoritmo sempre escolhe a aresta de menor peso que liga um vertice ja na
arvore a outro que ainda nao foi incluido, expandindo gradualmente a arvore geradora minima.
O Algoritmo de Prim pode ser aplicado em grafos desconexos?
a) Sim, gerando uma arvore unica.
b) Sim, mas resultara em uma floresta geradora minima.
c) Nao, ele so funciona com grafos completos.
d) Nao, ele so pode ser usado com grafos direcionados.
Resposta explicativa: Em grafos desconexos, o Algoritmo de Prim gera uma floresta geradora
minima, ou seja, uma colecao de arvores, uma para cada componente conectado do grafo.
Qual a principal diferenca entre os algoritmos de Prim e Kruskal?
a) O de Prim trabalha com vertices e o de Kruskal com arestas.
b) O de Kruskal e mais rapido em qualquer caso.
c) O de Prim funciona apenas com grafos direcionados.
d) O de Kruskal nao pode formar arvores minimas.
Resposta explicativa: Prim foca em expandir uma arvore a partir de um vertice inicial, adicionando
vertices gradualmente, enquanto Kruskal escolhe arestas de menor peso de forma global, unindo
componentes diferentes ate formar a arvore minima.
Em qual tipo de grafo o Algoritmo de Prim tende a ser mais eficiente que o de Kruskal?
a) Em grafos esparsos.
b) Em grafos densos.
c) Em grafos direcionados.
d) Em grafos bipartidos.
Resposta explicativa: O Algoritmo de Prim e mais eficiente em grafos densos, onde ha muitas
arestas, pois sua implementacao com fila de prioridade evita a necessidade de ordenar todas as
arestas previamente.
O que representa o conjunto de vertices marcados durante a execucao do Algoritmo de Prim?
a) Os vertices que ainda nao foram visitados.
b) Os vertices ja incluidos na arvore geradora minima.
c) Os vertices de maior grau.
d) Os vertices que nao tem arestas de saida.
Resposta explicativa: Os vertices marcados indicam os que ja foram incorporados a arvore
geradora minima, servindo de referencia para escolher novas arestas que expandam a arvore.
Qual condicao indica o fim da execucao do Algoritmo de Prim?
a) Quando todas as arestas forem visitadas.
b) Quando todos os vertices tiverem sido incluidos na arvore.
c) Quando o menor peso total for atingido.
d) Quando o grafo ficar desconexo.
Resposta explicativa: O algoritmo termina quando todos os vertices do grafo foram adicionados a
arvore geradora minima, ou seja, quando a arvore conecta todos os vertices sem ciclos.
O Algoritmo de Prim e sensivel a escolha do vertice inicial?
a) Sim, pois o resultado pode mudar dependendo do ponto de partida.
b) Nao, pois o custo total da arvore geradora minima sera o mesmo, independentemente do vertice
inicial.
c) Sim, e pode gerar arvores com pesos diferentes.
d) Nao, mas altera a quantidade de arestas.
Resposta explicativa: Embora a ordem das arestas escolhidas possa mudar, o custo total final da
arvore geradora minima e o mesmo, independentemente do vertice inicial escolhido.
Qual e uma aplicacao pratica comum do Algoritmo de Prim?
a) Criptografia assimetrica.
b) Compressao de dados.
c) Planejamento de redes de comunicacao ou energia.
d) Geracao de numeros aleatorios.
Resposta explicativa: O Algoritmo de Prim e amplamente usado em problemas de otimizacao de
redes, como o planejamento de cabos de energia, fibra optica e conexoes de roteadores, buscando
sempre o menor custo total.
Quem foi Robert C. Prim, criador do algoritmo?
a) Um engenheiro eletrico americano que trabalhou na Bell Labs.
b) Um fisico teorico britanico.
c) Um matematico russo especializado em teoria dos grafos.
d) Um programador alemao da IBM.
Resposta explicativa: Robert C. Prim foi um engenheiro eletrico americano que desenvolveu o
algoritmo em 1957 enquanto trabalhava na Bell Labs, contribuindo significativamente para o estudo
de otimizacao em redes e teoria dos grafos.