Buscar

Qual é a estratégia utilizada pelo algoritmo de Kruskal para encontrar a árvore geradora de custo mínimo? a) Ordenar as arestas do grafo por ordem...

Qual é a estratégia utilizada pelo algoritmo de Kruskal para encontrar a árvore geradora de custo mínimo?

a) Ordenar as arestas do grafo por ordem crescente de peso e, em seguida, unir os vértices pertencentes a árvores diferentes.
b) Escolher um vértice qualquer do grafo e fazer um corte, selecionando a aresta de menor peso desse corte e incluindo-a na árvore geradora de custo mínimo.
c) Inicializar um heap binário com os vértices do grafo e, em seguida, executar um loop para selecionar a aresta de menor peso em cada iteração.

Essa pergunta também está no material:

TeX output 2002 06 16_21723
51 pág.

Didática Universidade Estácio de SáUniversidade Estácio de Sá

Respostas

User badge image

Ed Verified user icon

Para encontrar a árvore geradora de custo mínimo, o algoritmo de Kruskal utiliza a estratégia de ordenar as arestas do grafo por ordem crescente de peso e, em seguida, selecionar a próxima aresta de menor peso que não forme um ciclo com as arestas já selecionadas. Portanto, a alternativa correta é a letra A) Ordenar as arestas do grafo por ordem crescente de peso.

0
Dislike0

Responda

SetasNegritoItálicoSublinhadoTachadoCitaçãoCódigoLista numeradaLista com marcadoresSubscritoSobrescritoDiminuir recuoAumentar recuoCor da fonteCor de fundoAlinhamentoLimparInserir linkImagemFórmula

Para escrever sua resposta aqui, entre ou crie uma conta

User badge image

Mais conteúdos dessa disciplina