Motivation
Lição 2 de 9 do curso Algoritmo de Prim - Algoritmos de Grafos da Coddy.
Enquanto o Kruskal ordena todas as arestas globalmente e usa union-find, o Prim mantém uma única árvore em crescimento e busca repetidamente o vértice externo mais próximo.
Por que aprender Prim?
- Grafos densos: O Prim com as estruturas certas é eficiente quando há muitas arestas.
- Propriedade do corte: é uma ilustração prática de por que a aresta mais barata que sai da árvore atual é sempre segura para adicionar.
- Duas visões de um problema: comparar Prim e Kruskal aprofunda seu entendimento sobre árvores geradoras mínimas.
Como todas as MSTs de um grafo compartilham os mesmos pesos de aresta, Prim e Kruskal sempre reportam o mesmo peso total.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
