Neste artigo, discutiremos o algoritmo do prim. Junto com o algoritmo, veremos também a complexidade, funcionamento, exemplo e implementação do algoritmo de prim.
Antes de iniciar o tópico principal, devemos discutir os termos básicos e importantes, como árvore geradora e árvore geradora mínima.
Árvore geradora - Uma árvore geradora é o subgrafo de um grafo conectado não direcionado.
Árvore geradora mínima - A árvore geradora mínima pode ser definida como a árvore geradora em que a soma dos pesos da aresta é mínima. O peso da árvore geradora é a soma dos pesos atribuídos às arestas da árvore geradora.
Agora, vamos começar o tópico principal.
Algoritmo de Prim é um algoritmo ganancioso usado para encontrar a árvore geradora mínima de um gráfico. O algoritmo de Prim encontra o subconjunto de arestas que inclui todos os vértices do gráfico, de modo que a soma dos pesos das arestas possa ser minimizada.
O algoritmo de Prim começa com um único nó e explora todos os nós adjacentes com todas as arestas de conexão em cada etapa. As arestas com pesos mínimos que não causam ciclos no gráfico foram selecionadas.
Como funciona o algoritmo do prim?
O algoritmo de Prim é um algoritmo ganancioso que começa a partir de um vértice e continua adicionando as arestas com menor peso até que o objetivo seja alcançado. As etapas para implementar o algoritmo do prim são fornecidas a seguir -
- Primeiro, temos que inicializar um MST com o vértice escolhido aleatoriamente.
- Agora, temos que encontrar todas as arestas que conectam a árvore na etapa acima com os novos vértices. A partir das arestas encontradas, selecione a aresta mínima e adicione-a à árvore.
- Repita a etapa 2 até que a árvore geradora mínima seja formada.
As aplicações do algoritmo de prim são -
- O algoritmo de Prim pode ser usado no projeto de redes.
- Pode ser usado para fazer ciclos de rede.
- Também pode ser usado para instalar cabos de fiação elétrica.
Exemplo de algoritmo de prim
Agora, vamos ver o funcionamento do algoritmo de prim usando um exemplo. Será mais fácil entender o algoritmo do prim usando um exemplo.
Suponha que um gráfico ponderado seja -
Passo 1 - Primeiro, temos que escolher um vértice do gráfico acima. Vamos escolher B.
configuração do caminho python
Passo 2 - Agora, temos que escolher e adicionar a aresta mais curta do vértice B. Existem duas arestas do vértice B que são B a C com peso 10 e aresta B a D com peso 4. Entre as arestas, a aresta BD tem o peso mínimo . Então, adicione-o ao MST.
Etapa 3 - Agora, novamente, escolha a aresta com peso mínimo entre todas as outras arestas. Neste caso, as arestas DE e CD são tais arestas. Adicione-os ao MST e explore o adjacente de C, ou seja, E e A. Então, selecione a aresta DE e adicione-a ao MST.
Passo 4 - Agora, selecione o CD Edge e adicione-o ao MST.
Etapa 5 - Agora, escolha a aresta CA. Aqui, não podemos selecionar a aresta CE, pois isso criaria um ciclo para o gráfico. Então, escolha a aresta CA e adicione-a ao MST.
Portanto, o gráfico produzido na etapa 5 é a árvore geradora mínima do gráfico fornecido. O custo do MST é fornecido abaixo -
Custo do MST = 4 + 2 + 1 + 3 = 10 unidades.
Algoritmo
Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT
Complexidade do algoritmo de Prim
Agora, vamos ver a complexidade de tempo do algoritmo de Prim. O tempo de execução do algoritmo do prim depende do uso da estrutura de dados do gráfico e da ordenação das arestas. A tabela abaixo mostra algumas opções -
| Estrutura de dados usada para o peso mínimo da aresta | Complexidade de tempo |
|---|---|
| Matriz de adjacência, pesquisa linear | O(|V|2) |
| Lista de adjacências e heap binário | O(|E| log |V|) |
| Lista de adjacência e pilha de Fibonacci | O(|E|+ |V| log |V|) |
O algoritmo de Prim pode ser simplesmente implementado usando a matriz de adjacência ou a representação gráfica da lista de adjacências, e adicionar a aresta com o peso mínimo requer a busca linear de uma matriz de pesos. Requer O(|V|2) tempo de execução. Ele pode ser melhorado ainda mais usando a implementação de heap para encontrar as arestas de peso mínimo no loop interno do algoritmo.
A complexidade de tempo do algoritmo do prim é O(E logV) ou O(V logV), onde E é o não. de arestas, e V é o não. de vértices.
Implementação do algoritmo de Prim
Agora, vamos ver a implementação do algoritmo de prim.
Programa: Escreva um programa para implementar o algoritmo de prim em linguagem C.
#include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
weight
'); printf(' %d
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that's all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>