Buscar

Qual é a ideia básica do algoritmo de Prim para AGCM? a) Escolher um vértice qualquer do grafo e fazer um corte, selecionando a aresta de menor p...

Qual é a ideia básica do algoritmo de Prim para AGCM?

a) 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.
b) Ordenar as arestas do grafo por ordem crescente de peso e, em seguida, unir os vértices pertencentes a árvores diferentes.
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

Vamos analisar as opções: a) Escolher um vértice qualquer do grafo e fazer um corte, selecionando a aresta de menor peso que conecta o vértice escolhido a um vértice fora do corte. - Esta descrição está incorreta, pois o algoritmo de Prim começa com um vértice inicial e expande a árvore geradora mínima a partir dele. b) Iniciar com uma árvore contendo um único vértice e expandir a árvore, sempre escolhendo a aresta de menor peso que conecta um vértice da árvore a um vértice fora dela. - Esta é a ideia básica correta do algoritmo de Prim. c) Selecionar aleatoriamente uma aresta do grafo e adicionar ao conjunto de arestas da árvore geradora mínima. - Esta descrição está incorreta, pois o algoritmo de Prim não seleciona arestas aleatoriamente. Portanto, a alternativa correta é a letra b) Iniciar com uma árvore contendo um único vértice e expandir a árvore, sempre escolhendo a aresta de menor peso que conecta um vértice da árvore a um vértice fora dela.

0
Dislike0

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

Você também pode ser Premium ajudando estudantes

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