Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim’s Algorithm - Coggle Diagram
Prim’s Algorithm
se um gráfico é representado por sua matriz de peso e a fila de prioridade é implementada como uma fila de prioridade matriz desordenada
A resposta depende das estruturas de dados escolhidas para o próprio grafo e para a fila de prioridades do conjunto V − VT cujas prioridades de vértices são as distâncias aos vértices da árvore mais próximos
se um gráfico é representado por sua matriz de peso e a fila de prioridade é implementada como uma fila de prioridade matriz desordenada
-
Se um grafo é representado por suas listas de adjacências e a fila de prioridade é implementada como um heap mínimo
-
Cada uma dessas operações, conforme observado anteriormente, é uma operação O(log |V |)
o tempo de execução desta implementação do algoritmo de Prim está em (|V | − 1 + |E|)O(log |V |) = O(|E| log |V |). porque, em um grafo conexo, |V | − 1 ≤ |E|.
O algoritmo de Prim constrói uma árvore geradora mínima por meio de uma sequência de subárvores em expansão.
A subárvore inicial em tal sequência consiste em um único vértice selecionado arbitrariamente do conjunto V dos vértices do grafo
Em cada iteração, o algoritmo expande a árvore atual de maneira gulosa
-
Após identificarmos um vértice u∗ a ser adicionado à árvore, precisamos realizar duas operações:
-
-
-