Baseando-se nas características e no funcionamento do algoritmo de Kruskal, assinale a alternativa correta. a. O algoritmo de Kruskal é mais efic...
Baseando-se nas características e no funcionamento do algoritmo de Kruskal, assinale a alternativa correta.
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 é utilizado para resolver problemas de caminho mais curto em grafos.
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 é utilizado para resolver problemas de caminho mais curto em grafos.
💡 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, pois sua complexidade é O(E log E), onde E é o número de arestas do grafo.
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
10 pág.
Compartilhar