Baseando-se nas características e no funcionamento do algoritmo de Kruskal, assinale a alternativa correta. a. O algoritmo de Kruskal é mais efic...
a. O algoritmo de Kruskal é mais eficiente para grafos densos do que para grafos esparsos.
b. Uma das vantagens do algoritmo de Kruskal é a sua simplicidade e facilidade de implementação.
c. No algoritmo de Kruskal, as arestas do grafo são organizadas em ordem decrescente de peso na fase de inicialização.
d. Se durante a execução do algoritmo de Kruskal, uma aresta selecionada conecta dois vértices que já pertencem à mesma árvore, ela é adicionada à solução.
e. O algoritmo de Kruskal termina quando todas as arestas foram adicionadas à solução.
💡 1 Resposta
Ed 
A alternativa correta é a letra b. Uma das vantagens do algoritmo de Kruskal é a sua simplicidade e facilidade de implementação. O algoritmo de Kruskal é um algoritmo guloso que busca a árvore geradora mínima de um grafo ponderado. Ele funciona selecionando a aresta de menor peso em cada iteração e adicionando-a à solução, desde que não crie um ciclo. O algoritmo é eficiente para grafos esparsos e densos e não organiza as arestas em ordem decrescente de peso na fase de inicialização. Se durante a execução do algoritmo de Kruskal, uma aresta selecionada conecta dois vértices que já pertencem à mesma árvore, ela é descartada. O algoritmo de Kruskal termina quando a solução contém n-1 arestas, onde n é o número de vértices do grafo.
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Perguntas relacionadas
Compartilhar