MST de Prim com uma Heap
Expanda a árvore a partir de um vértice.
MST de Prim com uma Heap é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Um caminho diferente para a MST
O algoritmo de Prim também encontra uma árvore geradora mínima, mas ele expande um único bloco conectado para fora, em vez de ordenar todas as arestas primeiro. 🌱
Comece por um vértice
Escolha qualquer vértice inicial e marque-o como visitado. A árvore começa como um único nó e se expande uma aresta por vez.
visited = [False] * nA ideia da fronteira
A cada etapa, observe todas as arestas que cruzam da árvore para a parte externa. Prim sempre escolhe a aresta de fronteira mais barata.
Uma fila de prioridade escolhe o mínimo
Uma fila de prioridade mínima torna rápida a busca pela aresta de fronteira mais barata. Insira nela as arestas candidatas e remova a de menor peso a cada rodada.
import heapq
heap = [(0, start)]Remova a aresta mais barata
Remova a menor entrada da fila de prioridade. Ela fornece o peso e o próximo vértice mais barato para conectar à árvore em crescimento.
w, u = heapq.heappop(heap)Ignore entradas obsoletas
Um vértice pode aparecer mais de uma vez na fila de prioridade. Se você remover um que já foi visitado, simplesmente ignore-o e remova o próximo.
if visited[u]:
continueAdicione e expanda
Marque como visitado o vértice removido e adicione seu peso ao total. Em seguida, insira na fila de prioridade cada uma das arestas que saem dele para as próximas etapas.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Repita até completar
Continue removendo elementos e expandindo até que todos os vértices estejam visitados. Nesse momento, o total acumulado será o peso da árvore geradora mínima.
O tempo de execução
Cada aresta pode ser inserida uma vez e removida uma vez, então Prim usando uma fila de prioridade é executado em O(E log V), de forma comparável a Kruskal.
Prim contra Kruskal
Use Prim em grafos densos com uma lista de adjacências, e Kruskal quando você já tiver uma lista simples de arestas. Ambos produzem o mesmo peso de MST.
Parece Dijkstra
O laço da fila de prioridade se parece com o de Dijkstra, mas você compara pesos brutos das arestas, não distâncias dos caminhos. Reconhecer esse padrão economiza tempo de programação. ⚡
Verificação rápida
Relembre como Prim escolhe sua próxima aresta a cada rodada.
Recapitulação
Você construiu uma MST com Prim: comece em qualquer lugar, use uma fila de prioridade mínima para adicionar a aresta de fronteira mais barata e ignore visitas obsoletas. Excelente trabalho! 🎉
Perguntas Frequentes
A aula “MST de Prim com uma Heap” é grátis?
Sim — o texto completo de “MST de Prim com uma Heap” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “MST de Prim com uma Heap”?
Expanda a árvore a partir de um vértice. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “MST de Prim com uma Heap”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- DSU com Compressão de Caminhos
- União por Classificação e Componentes
- Árvore Geradora Mínima de Kruskal
- MST de Prim com uma Heap