Neste artigo, discutiremos o algoritmo de Kruskal. Aqui também veremos a complexidade, funcionamento, exemplo e implementação do algoritmo de Kruskal.
Mas antes de prosseguirmos diretamente para o algoritmo, devemos primeiro entender os termos básicos, 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 com o tópico principal.
Algoritmo de Kruskal é usado para encontrar a árvore geradora mínima para um gráfico ponderado conectado. O objetivo principal do algoritmo é encontrar o subconjunto de arestas com o qual podemos percorrer cada vértice do gráfico. Segue a abordagem gananciosa que encontra uma solução óptima em todas as fases, em vez de se concentrar num óptimo global.
Como funciona o algoritmo de Kruskal?
No algoritmo de Kruskal, começamos pelas arestas com menor peso e continuamos adicionando as arestas até que o objetivo seja alcançado. As etapas para implementar o algoritmo de Kruskal estão listadas a seguir -
- Primeiro, classifique todas as bordas de baixo para alto.
- Agora, pegue a aresta com o peso mais baixo e adicione-a à árvore geradora. Se a aresta a ser adicionada criar um ciclo, rejeite a aresta.
- Continue adicionando as arestas até chegarmos a todos os vértices e uma árvore geradora mínima for criada.
As aplicações do algoritmo de Kruskal são -
- O algoritmo de Kruskal pode ser usado para traçar a fiação elétrica entre cidades.
- Ele pode ser usado para estabelecer conexões LAN.
Exemplo do algoritmo de Kruskal
Agora, vamos ver o funcionamento do algoritmo de Kruskal usando um exemplo. Será mais fácil entender o algoritmo de Kruskal usando um exemplo.
Suponha que um gráfico ponderado seja -
O peso das arestas do gráfico acima é dado na tabela abaixo -
| Borda | AB | AC | DE ANÚNCIOS | MAS | AC | CD | DE |
| Peso | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Agora, classifique as arestas fornecidas acima em ordem crescente de seus pesos.
| Borda | AB | DE | AC | CD | MAS | AC | DE ANÚNCIOS |
| Peso | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Agora, vamos começar a construir a árvore geradora mínima.
janelas.open javascript
Passo 1 - Primeiro, adicione a borda AB com peso 1 ao MST.
Passo 2 - Adicione a borda DE com peso 2 ao MST porque não está criando o ciclo.
Etapa 3 - Adicione a borda AC com peso 3 ao MST, pois não está criando nenhum ciclo ou loop.
Passo 4 - Agora, escolha a borda CD com peso 4 ao MST, pois não está formando o ciclo.
Etapa 5 - Depois disso, escolha a borda MAS com peso 5. Incluir esta aresta criará o ciclo, então descarte-o.
Etapa 6 - Escolha a borda AC com peso 7. Incluir esta aresta criará o ciclo, então descarte-o.
Etapa 7 - Escolha a borda DE ANÚNCIOS com peso 10. Incluir esta aresta também criará o ciclo, então descarte-o.
Portanto, a árvore geradora mínima final obtida do gráfico ponderado fornecido usando o algoritmo de Kruskal é -
O custo do MST é = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Agora, o número de arestas na árvore acima é igual ao número de vértices menos 1. Portanto, o algoritmo para aqui.
Algoritmo
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
Complexidade do algoritmo de Kruskal
Agora, vamos ver a complexidade de tempo do algoritmo de Kruskal.
A complexidade de tempo do algoritmo de Kruskal é O(E logE) ou O(V logV), onde E é o não. de arestas, e V é o não. de vértices.
Implementação do algoritmo de Kruskal
Agora, vamos ver a implementação do algoritmo de Kruskal.
Programa: Escreva um programa para implementar o algoritmo de Kruskal em C++.
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>