Algoritmo de prims

Árvore de abrangência mínima:

Um gráfico que não tem instruções é chamado de gráfico não direcionado. Cada gráfico deve ter um caminho de um nó para outro nó. Uma árvore de extensão também é um gráfico conectado não direcionado, onde todos os nós do gráfico estão presentes com bordas mínimas. Se uma árvore de extensão não tem todos os nós do gráfico, não podemos dizer que é uma árvore de extensão. O total de pesos totais da árvore será menor que o peso original do gráfico enquanto o conectamos através das bordas mínimas de peso. A árvore spanning também não tem um ciclo. Qualquer gráfico tem mais de uma árvore de extensão, mas apenas um deles será único. Chamamos isso de uma árvore de abrangência mínima, pois estamos tentando criar um gráfico completo com todos os nós, mantendo o peso baixo.

Podemos desenhar uma árvore de extensão com a ajuda dos dois métodos a seguir:

1. Algoritmo de Kruskal
2. Algoritmo de Prim

Neste artigo, vamos discutir o algoritmo de Prim. O algoritmo de Kruskal será discutido no próximo artigo.

Algoritmo de Prim:

O algoritmo de Prim é usado para encontrar a árvore de abrangência mínima de um gráfico. O algoritmo do Prim começa em qualquer nó e depois adiciona qualquer nó adjacente cujo peso seja o mínimo, e esse processo continua até que todos os nós nos gráficos sejam visitados. Ao criar a árvore de abrangência mínima de um gráfico, também precisamos criar ciclos porque os ciclos não devem estar na árvore mínima de abrangência.

Etapas do algoritmo de Prim:

O algoritmo do Prim emprega a abordagem gananciosa para a árvore de abrangência mínima. Temos que escolher qualquer vértice do gráfico e, em seguida.

Passo 1: Escolha qualquer vértice de origem no gráfico.

Passo 2: Encontre a borda mínima de peso adjacente à fonte e depois conecte -a à árvore de extensão.

Etapa 3: Repita a etapa 2 até que todos os nós não sejam adicionados à árvore mínima.

Exemplo :

O abaixo é um exemplo para pesquisar uma árvore de abrangência mínima usando o algoritmo de Prim.

1. Escolhemos qualquer nó aleatório no gráfico G e o adicionamos ao MST (árvore de abrangência mínima). Selecionamos aqui o nó 0.

2. Agora, selecionamos a borda adjacente ao nó de origem (0), mas com o menor peso e adicione o menor nó de peso à árvore de abrangência mínima.

3. Agora, selecionamos a borda adjacente ao nó de origem (0 ou 1), mas com o menor peso e adicione o menor nó de peso à árvore mínima.

4. Agora, selecionamos a borda adjacente ao nó de origem (0, 1 ou 3), mas com o menor peso e adicione o menor nó de peso à árvore mínima.

5. Agora, selecionamos a borda adjacente ao nó de origem (0, 1, 3 ou 4), mas com o menor peso e adicione o menor nó de peso à árvore mínima.

6. Agora, selecionamos a borda adjacente ao nó de origem (0, 1, 3, 4 ou 6), mas com o menor peso e adicione o menor nó de peso à árvore mínima.

7. Agora, selecionamos a borda adjacente ao nó de origem (0, 1, 3, 4, 6 ou 2), mas com o menor peso e adicione o menor nó de peso à árvore mínima.

Acima está o nosso MST final (árvore de abrangência mínima), e o custo total é 6.

Programa MST (árvore mínima de abrangência) do C ++ Prim:

#incluir
#incluir
#incluir
#incluir
#incluir
typedef std :: par Sii;
typedef std :: vetor SSII;
int primsmst (int sourcenode, std :: vetor & gráfico)
// Esta fila armazenará detalhes de cada nó
// junto com seu valor de peso.
std :: priority_queue, std :: maior> k;
k.push (std :: make_pair (0, sourcenode));
Bool Sodesadded [Gráfico.tamanho()];
MEMSEST (SodesAdded, False, Sizeof (Bool)*Gráfico.tamanho());
int mst_tree_cost = 0;
enquanto (!k.vazio())
// estamos selecionando aqui o nó que tem custo mínimo
Sii itemNode;
itemNode = k.principal();
k.pop ();
int node = itemNode.segundo;
int custo = itemNode.primeiro;
// Aqui estamos verificando se algum nó não foi adicionado ao MST,
// então adicionando esse nó.
se (!SodesAdded [Node])
mst_tree_cost += custo;
modesadded [nó] = true;
// itera sobre os nós negativos que foram recentemente tomados
// da fila de prioridade.
// e adicionado ao MST que ainda não foi adicionado
para (Auto & par_node_cost: gráfico [nó])
int adjency_node = par_node_cost.segundo;
if (modesadded [adjency_node] == false)
k.push (par_node_cost);




retornar mst_tree_cost;

int main ()
// Os detalhes do gráfico com o nó de custo e adjência.
Ssii fromnode_0_in_graph_1 = 1,1, 2,2, 1,3,
1,4, 2,5, 1,6;
Ssii fromnode_1_in_graph_1 = 1,0, 2,2, 2,6;
Ssii fromnode_2_in_graph_1 = 2,0, 2,1, 1,3;
Ssii denode_3_in_graph_1 = 1,0, 1,2, 2,4;
Ssii fromnode_4_in_graph_1 = 1,0, 2,3, 2,5;
Ssii fromnode_5_in_graph_1 = 2,0, 2,4, 1,6;
Ssii fromnode_6_in_graph_1 = 1,0, 2,2, 1,5;
int num_of_nodes = 7; // Total de nós (0 a 6)
std :: vetor primsgraph;
PrimsGraph.redimensionar (num_of_nodes);
primsgraph [0] = denode_0_in_graph_1;
primsgraph [1] = denode_1_in_graph_1;
primsgraph [2] = denode_2_in_graph_1;
primsgraph [3] = denode_3_in_graph_1;
primsgraph [4] = denode_4_in_graph_1;
primsgraph [5] = denode_5_in_graph_1;
primsgraph [6] = denode_6_in_graph_1;
// Como já sabemos, temos que escolher o vértice da fonte,
// então começamos no nó do vértice 0.
std :: cout << "Total cost of minimum spanning tree after Prim's algorithm : "
"" << PrimsMST(0, primsgraph) << std :: endl;
retornar 0;

Saída:

Custo total da árvore de abrangência mínima após o algoritmo de Prim: 6

Complexidade do tempo do algoritmo MST de Prim:

1. O tempo total necessário para processar e selecionar o nó da fila de prioridade específico que ainda não foi adicionado ao MST é logv.Mas, como funciona para todos os vértices, a complexidade total do tempo é V (logv).

2. O gráfico não é direcionado e as bordas totais serão 2e. Como precisamos empurrar os nós para a fila de prioridade, será necessário um log de tempo total (v). No entanto, como temos um total de 2e bordas, nossa operação total de push será 2e (log (v)).

3. Complexidade total após a operação 1 e 2 é O ((e + v) log (v)).

Conclusão:

Estudamos a árvore mínima de abrangência do prim, que é a primeira preferência da maioria das pessoas quando elas precisam encontrar o gráfico MST de um gráfico. O algoritmo do Prim é simples de entender e implementar em um aplicativo do mundo real.O algoritmo de Prim é muito útil em aplicações da vida real, por exemplo, conectando trilhos de trem a toda as cidades. Portanto, é apenas um exemplo, mas sua aplicação é enorme, então devemos ter que entender esse algoritmo.