Algoritmo de Kruskal

Prévia do material em texto

Algoritmo de Kruskal 
O que e o Algoritmo de Kruskal?
a) Um algoritmo para ordenacao de elementos
b) Um algoritmo para encontrar o menor caminho em um grafo
c) Um algoritmo para encontrar a arvore geradora minima de um grafo
d) Um algoritmo de busca em largura
Resposta correta: c) Um algoritmo para encontrar a arvore geradora minima de um grafo
Explicacao: O Algoritmo de Kruskal e um algoritmo utilizado para resolver o problema da arvore
geradora minima em grafos ponderados. Ele seleciona as arestas de menor peso e as adiciona ao
conjunto da arvore geradora, evitando ciclos.
Qual a principal caracteristica do Algoritmo de Kruskal em relacao a construcao da arvore geradora
minima?
a) Ele constroi a arvore geradora minima atraves da escolha do caminho de menor custo
b) Ele sempre comeca pela aresta de maior peso
c) Ele usa a abordagem de dividir e conquistar
d) Ele utiliza uma estrutura de heap para priorizar arestas
Resposta correta: a) Ele constroi a arvore geradora minima atraves da escolha do caminho de
menor custo
Explicacao: O Algoritmo de Kruskal trabalha selecionando as arestas de menor peso e as
adicionando a arvore geradora minima, garantindo que nao sejam formados ciclos durante o
processo.
Em que tipo de grafos o Algoritmo de Kruskal e mais eficaz?
a) Grafos dirigidos e com pesos negativos
b) Grafos nao dirigidos e com pesos positivos
c) Grafos nao ponderados
d) Grafos com lacos e multiplas arestas
Resposta correta: b) Grafos nao dirigidos e com pesos positivos
Explicacao: O Algoritmo de Kruskal e mais eficiente para grafos nao dirigidos e com arestas
ponderadas (com pesos positivos), onde o objetivo e encontrar a arvore geradora minima.
Qual e a principal estrutura de dados usada no Algoritmo de Kruskal para evitar ciclos durante a
construcao da arvore geradora minima?
a) Pilha
b) Fila de prioridade
c) Uniao-find (ou disjoint-set)
d) Arvore binaria balanceada
Resposta correta: c) Uniao-find (ou disjoint-set)
Explicacao: O Algoritmo de Kruskal utiliza a estrutura de dados chamada uniao-find para agrupar os
vertices em componentes conectados. Isso e essencial para garantir que, ao adicionar uma nova
aresta, nao se formem ciclos.
Qual e o objetivo do Algoritmo de Kruskal ao adicionar arestas ao grafo durante sua execucao?
a) Maximizar a soma dos pesos das arestas
b) Formar uma arvore geradora minima sem ciclos
c) Minimizar a quantidade de vertices na arvore geradora
d) Encontrar o caminho mais curto entre dois vertices especificos
Resposta correta: b) Formar uma arvore geradora minima sem ciclos
Explicacao: O objetivo do Algoritmo de Kruskal e formar uma arvore geradora minima, ou seja,
conectar todos os vertices do grafo com o menor custo possivel, evitando a formacao de ciclos.
Como o Algoritmo de Kruskal seleciona as arestas que serao incluidas na arvore geradora minima?
a) De forma aleatoria, buscando minimizar a quantidade de arestas
b) De forma ordenada, selecionando sempre a aresta de menor peso que nao forma ciclo
c) De forma deterministica, selecionando sempre a aresta de maior peso
d) Pelo grau dos vertices envolvidos
Resposta correta: b) De forma ordenada, selecionando sempre a aresta de menor peso que nao
forma ciclo
Explicacao: O Algoritmo de Kruskal seleciona as arestas de menor peso de forma crescente,
garantindo que a aresta escolhida nao forme ciclos, utilizando a estrutura de uniao-find para manter
o controle dos componentes conectados.
Qual a complexidade de tempo do Algoritmo de Kruskal, considerando que o grafo possui E arestas
e V vertices?
a) O(log E)
b) O(E log E)
c) O(V log V)
d) O(E + V)
Resposta correta: b) O(E log E)
Explicacao: A complexidade do Algoritmo de Kruskal e O(E log E), devido ao processo de
ordenacao das arestas e a aplicacao das operacoes de uniao-find, que tem custo logaritmico.
O Algoritmo de Kruskal pode ser utilizado para encontrar a arvore geradora minima em grafos com
pesos negativos?
a) Sim, mas ele nao garante a menor arvore geradora em grafos com pesos negativos
b) Nao, ele nao pode ser utilizado em grafos com pesos negativos
c) Sim, ele encontra a arvore geradora minima independentemente dos pesos das arestas
d) Sim, mas e necessario fazer uma modificacao no algoritmo
Resposta correta: c) Sim, ele encontra a arvore geradora minima independentemente dos pesos
das arestas
Explicacao: O Algoritmo de Kruskal pode ser usado em grafos com pesos negativos, pois a logica
de escolha das arestas e baseada apenas na ordenacao dos pesos, independentemente de serem
positivos ou negativos.
Qual e a principal diferenca entre o Algoritmo de Kruskal e o Algoritmo de Prim?
a) O Algoritmo de Kruskal trabalha com grafos dirigidos, enquanto o de Prim trabalha com grafos
nao dirigidos
b) O Algoritmo de Kruskal comeca com um vertice especifico, enquanto o de Prim nao precisa
c) O Algoritmo de Kruskal constroi a arvore geradora minima a partir das arestas, enquanto o de
Prim a constroi a partir dos vertices
d) O Algoritmo de Kruskal e mais rapido do que o de Prim em todos os casos
Resposta correta: c) O Algoritmo de Kruskal constroi a arvore geradora minima a partir das arestas,
enquanto o de Prim a constroi a partir dos vertices
Explicacao: A principal diferenca e que o Algoritmo de Kruskal trabalha adicionando arestas de
menor peso sem se preocupar com a origem dos vertices, enquanto o de Prim expande a arvore a
partir de um vertice inicial, adicionando uma aresta de menor peso que conecta o vertice a arvore
geradora.
Em um grafo com E arestas e V vertices, qual seria a operacao mais cara durante a execucao do
Algoritmo de Kruskal?
a) A busca pelo vertice de menor peso
b) A ordenacao das arestas
c) A atualizacao da estrutura de uniao-find
d) A verificacao de ciclos
Resposta correta: b) A ordenacao das arestas
Explicacao: A operacao mais cara no Algoritmo de Kruskal e a ordenacao das arestas, que tem
complexidade O(E log E). As outras operacoes, como a verificacao de ciclos e as atualizacoes de
uniao-find, tem complexidade logaritmica.
Qual e a funcao da estrutura de uniao-find no Algoritmo de Kruskal?
a) Armazenar os vertices ja incluidos na arvore geradora
b) Organizar as arestas de maneira eficiente para a ordenacao
c) Verificar se dois vertices pertencem ao mesmo componente conectado
d) Armazenar as arestas ja selecionadas
Resposta correta: c) Verificar se dois vertices pertencem ao mesmo componente conectado
Explicacao: A estrutura de uniao-find e usada no Algoritmo de Kruskal para verificar se dois vertices
pertencem ao mesmo componente conectado, garantindo que a adicao de uma aresta nao forme
um ciclo.
Qual e a principal vantagem do Algoritmo de Kruskal em relacao a outros algoritmos para encontrar
a arvore geradora minima?
a) Ele e mais eficiente para grafos densos
b) Ele pode ser implementado de maneira simples e direta
c) Ele e mais adequado para grafos com poucos vertices
d) Ele utiliza uma estrutura de dados mais complexa que melhora sua performance
Resposta correta: b) Ele pode ser implementado de maneira simples e direta
Explicacao: O Algoritmo de Kruskal e relativamente simples de implementar, especialmente porque
trabalha diretamente com a ordenacao das arestas e utiliza uma estrutura de dados eficiente para
gerenciar os componentes conectados.
O que ocorre se o grafo fornecido ao Algoritmo de Kruskal for desconexo?
a) O algoritmo ainda ira funcionar, mas nao encontrara uma arvore geradora minima
b) O algoritmo falha, pois assume que o grafo esta completamente conectado
c) O algoritmo encontra uma arvore geradora minima para cada