Algoritmo de Prim
Prim
Kruskal
Pseudocódigo
Grafos
▾
Exemplos
Grafo aleatório
Vértices
8
Gerar grafo aleatório
Prim: no passo inicial, clique em um vértice para escolhê-lo como origem.
?
Como usar
Prim / Kruskal
escolhe o algoritmo (tecla
K
alterna); o grafo é o mesmo nos dois.
Avançar / Voltar
executa o algoritmo um passo por vez (teclas
→
/
←
ou
espaço
).
Automático
avança sozinho (tecla
A
);
Reiniciar
volta ao início (
Home
).
Pseudocódigo
mostra a linha executada em cada passo (tecla
P
); é o mesmo dos slides.
Grafos
carrega um exemplo ou gera um grafo aleatório conexo.
Prim:
o heap
H
guarda triplas (
c
,
v
,
u
), a aresta (
u
,
v
) de custo
c
, e começa só com (0,
s
, ⊥). Quando
v
entra em
X
(azul), as arestas de
v
para fora de
X
são inseridas. Triplas
cinza
são obsoletas (
v
já está em
X
) e são descartadas quando saem. O número junto de cada vértice é o custo da aresta que o ligou à árvore (ou, fora de
X
, da candidata mais barata em
H
). No passo inicial, clique em um vértice para escolhê-lo como origem
s
.
Kruskal:
as arestas são examinadas em ordem crescente de custo; a estrutura Union-Find (
pai
,
rank
) diz se as pontas estão na mesma componente. As componentes aparecem como manchas coloridas ao redor dos vértices.
Fechar