Algoritmo Kruskal
Á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 de extensão 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.
Vamos entender a árvore de abrangência mínima com um exemplo. Então, como sabemos, a árvore de abrangência mínima faz parte do gráfico, mas com menos custo. Portanto, esse cenário pode ser ilustrado com um exemplo. Vamos supor que temos um gráfico como este.
O gráfico acima pode ser organizado de maneiras diferentes para que o ciclo do gráfico seja removido, caso contrário não será um MST (árvore mínima de abrangência). Portanto, removeremos o ciclo do gráfico e contaremos o custo total do gráfico. Temos quatro nós, ou vértices (A, B, C e D).
Caso 1:
Depois de remover o ciclo do gráfico, o custo do gráfico acima do MST (árvore mínima de abrangência) é 56.
Caso -2:
Depois de remover o ciclo do gráfico, o custo do gráfico acima do MST (árvore mínima de abrangência) é 53.
Caso - 3:
Depois de remover o ciclo do gráfico, o custo do gráfico acima do MST (árvore de abrangência mínima) é 41.
Podemos ver que o último gráfico do custo total do Case-3 é muito menor em comparação com os outros dois gráficos. Portanto, este gráfico é o nosso MST final (árvore de abrangência mínima) para o gráfico original. Os algoritmos do prim ou Kruskal são o motivo de encontrar o custo do gráfico o mais baixo possível. Então esse é o nosso motivo neste artigo para explicar este MST.
Podemos desenhar uma árvore de extensão com a ajuda dos dois métodos a seguir:
- Algoritmo de Kruskal
- Algoritmo de Prim
Neste artigo, vamos discutir o algoritmo de Kruskal. O algoritmo de Prim será discutido no próximo artigo.
Algoritmo de Kruskal
O algoritmo de Kruskal é muito fácil de implementar em comparação com o algoritmo de Prim, porque não precisamos nos preocupar com os vértices de adjacência neste algoritmo. Neste algoritmo, o algoritmo de Kruskal começa em todos os vértices do gráfico. Escolhemos a vérticice mínima da borda de peso e começamos a criar a árvore de extensão mínima. Escolhemos outra vantagem com o peso mínimo e adicionamos à árvore de abrangência mínima. Este processo continua até que não adicionemos todos os nós do gráfico original. Uma vez que todos os nós no gráfico sejam adicionados à árvore mínima de abrangência, o algoritmo vai parar. Durante a criação da árvore de abrangência mínima de um gráfico, também precisamos cuidar desse gráfico, não criando ciclos porque os ciclos não devem estar na árvore mínima de abrangência.
Portanto, se algum nó criar o ciclo na árvore mínima, escolhemos o outro nó, mesmo que o peso desse nó seja maior que o nó anterior que cria o ciclo.
O algoritmo de Kruskal é diferente do algoritmo de Prim. O algoritmo de Prim, enquanto cria uma árvore de abrangência mínima, começa em qualquer nó ou vertice e depois adiciona outro nó ou vértice apenas dos nós de adjacência. Mas o algoritmo de Kruskal não se importa com o nó de adjacência e sempre seleciona esse nó que tem menos peso, mas esse nó não deve criar um ciclo na árvore mínima.
Algoritmo de Kruskal Passos:
As medidas seguintes são tomadas ao escrever o código C ++ para o algoritmo de Kruskal.
- Criamos uma matriz para armazenar grupos de nós ou vértices do gráfico.
- Criamos outra matriz para armazenar pesos de bordas do gráfico.
- Para a árvore Spanning, criamos uma nova matriz.
- Organizamos a matriz das bordas em ordem ascendente.
- Repitamos a etapa 6 até que a matriz de pesos de borda classificada não esteja vazia.
- Comparamos os dois grupos lado a lado. Nesse caso, se um nó de um grupo não corresponde ao outro nó, adicionamos essa borda à árvore de extensão e a adicionamos ao mesmo grupo.
- Itera através de todas as bordas da árvore de extensão para determinar seu peso total.
Agora, implementaremos as etapas do algoritmo acima usando um exemplo. Temos o gráfico abaixo e descobriremos a árvore de abrangência mínima para este gráfico.
Então, de acordo com o algoritmo, primeiro escolhemos a menor borda de peso, que é AB. Então, escolhemos essa vantagem e a mantemos na matriz de árvores. O peso da borda AB é 9.
Agora, escolhemos a próxima menor borda de peso, CD e mantemos essa borda na matriz de árvore de abrangência mínima. O peso da borda do CD é 12.
A próxima menor vantagem que recebemos foi BC, que mantivemos na matriz. A borda BC ponderada é 17.
Nosso algoritmo vai parar por aqui porque temos todos os vértices de um gráfico, e temos nossa árvore mínima. O peso total deste MST é 9 + 12 + 17 = 38.
Programa: O abaixo é um código C ++ para o algoritmo de Kruskal.
#incluir#incluir
#incluir
classe EdgeGraph
público:
int nodestart;
int nodeend;
int wght;
EdgeGraph ()
EdgeGraph (int node_1, int node_2, int weight): nodestart (node_1),
nodeend (node_2), wght (peso)
;
Bool CompareEdGecost (const EdgeGraph A, Const EdgeGraph B)
retornar a.wght < b.wght;
classe G
privado:
int num_of_nodes;
std :: vetor
std :: vetor
std :: vetor
público:
G ()
G (int num_of_nodes)
this-> num_of_nodes = num_of_nodes;
parentnode.redimensionar (num_of_nodes);
rankNode.redimensionar (num_of_nodes);
Void AddedgeGraph (EdgeGraph E);
int findParentNode (int node);
Void Kruskalmst_algo (STD :: Vector
Void DisplayEdgeGraphs (STD :: Vector
;
void G :: AddedgeGraph (EdgeGraph e)
EdgeGraphlist.push_back (e);
int g :: findParentNode (int node)
if (nó != parentNode [nó])
parentnode [nó] = findParentNode (parentNode [nó]);
return parelernode [nó];
Void G :: DisplayEdgeGraphs (STD :: Vector
int custe = 0;
std :: cout << "EdgeGraphs of MST : ";
para (Auto & e: MST)
std :: cout << "[" << e.nodeSTART << "-" << e.nodeEND
<< "](" << e.wght << ") ";
custo += e.wght;
std :: cout << "\n Kruskal MST Cost : " << cost << std :: endl;
// Esta é a principal função do algoritmo de Kruskal que pesquisa
// A árvore de abrangência mínima.
void g :: kruskalmst_algo (std :: vetor
para (int i = 0; i
rankNode [i] = 0;
classificar (EdgeGraphlist.BEGIN (), EdgeGraphlist.fim(),
Compareedgecost);
para (Auto & e: EdgeGraphlist)
int root_1 = findParentNode (e.nodestart);
int root_2 = findParentNode (e.nodeend);
if (root_1 != root_2)
resultado.push_back (e);
if (ranknode [root_1] < rankNode[root_2])
parentnode [root_1] = root_2;
rankNode [root_2] ++;
outro
parentnode [root_2] = root_1;
rankNode [root_1] ++;
int main ()
int num_of_nodes = 6; // (0, 1, 2, 3, 4, 5)
EdgeGraph E1 (0, 1, 4);
EdgeGraph E2 (0, 2, 1);
EdgeGraph E3 (0, 3, 5);
EdgeGraph E4 (1, 3, 2);
EdgeGraph E5 (1, 4, 3);
EdgeGraph E6 (1, 5, 3);
EdgeGraph E7 (2, 3, 2);
EdgeGraph E8 (2, 4, 8);
EdgeGraph E9 (3, 4, 1);
EdgeGraph E10 (4, 5, 3);
G g1 (num_of_nodes);
G1.AdicionadoGeGraph (E1);
G1.AdicionadoGeGraph (E2);
G1.AdicionadoGeGraph (E3);
G1.AdicionadoGeGraph (E4);
G1.AdicionadoGeGraph (E5);
G1.AdicionadoGeGraph (E6);
G1.AdicionadoGeGraph (E7);
G1.AdicionadoGeGraph (E8);
G1.AdicionadoGeGraph (E9);
G1.AdicionadoGeGraph (E10);
std :: vetor
G1.Kruskalmst_algo (MST);
G1.DisplayEdgeGraphs (MST);
retornar 0;
Saída:
Agegrafos de MST: [0-2] (1) [3-4] (1) [1-3] (2) [2-3] (2) [1-5] (3)Kruskal MST Custo: 9
Conclusão:
Estudamos a árvore mínima de Kruskal, que é a primeira preferência da maioria das pessoas quando elas precisam encontrar o gráfico MST de um gráfico. O algoritmo de Kruskal é simples de entender e implementar em um aplicativo do mundo real. Como o algoritmo de Prim, o algoritmo de Kruskal também é muito útil em aplicações da vida real. Então, devemos entender este algoritmo.