minimum spanning tree tutorial
Este Tutorial C ++ explica o que é uma árvore de abrangência mínima (MST) junto com os algoritmos de Prim e Kruskal para encontrar MST em um gráfico e suas aplicações:
Uma Spanning tree pode ser definida como um subconjunto de um gráfico, que consiste em todos os vértices cobrindo as arestas mínimas possíveis e não tem um ciclo. Spanning tree não pode ser desconectado.
Cada grafo conectado e não direcionado tem pelo menos uma árvore de abrangência. Um gráfico desconectado não possui uma árvore estendida, pois não é possível incluir todos os vértices.
=> Veja aqui para explorar a lista completa de tutoriais C ++.
O que você aprenderá:
Spanning Tree em C ++
Considere o seguinte gráfico conectado.
Como mostrado acima, para o determinado Grafo conectado contendo 3 vértices, temos três árvores geradoras. Em geral, se N é o número de nós em um grafo, então um grafo conectado completo tem no máximo NN-2número de árvores abrangentes. Assim, no gráfico acima N = 3, portanto, tem 3(3-2)= 3 árvores abrangentes.
Algumas das propriedades da árvore de abrangência estão listadas abaixo:
- Um grafo conectado pode ter mais de uma árvore de abrangência.
- Todas as árvores abrangentes em um grafo têm o mesmo número de nós e arestas.
- Se removermos uma borda da árvore de abrangência, ela se tornará minimamente conectado e fará com que o gráfico seja desconectado.
- Por outro lado, adicionar uma aresta à árvore de abrangência tornará maximamente acíclico criando assim um loop.
- Uma Spanning Tree não possui um loop ou um ciclo.
O que é uma árvore de abrangência mínima (MST)
Uma árvore de abrangência mínima é aquela que contém o menor peso entre todas as outras árvores de abrangência de um gráfico ponderado conectado. Pode haver mais de uma árvore de abrangência mínima para um gráfico.
Existem dois algoritmos mais populares usados para encontrar a árvore de abrangência mínima em um gráfico.
Eles incluem:
- Algoritmo de Kruskal
- Algoritmo de Prim
Vamos discutir esses dois algoritmos!
Algoritmo de Kruskal
O algoritmo de Kruskal é um algoritmo para encontrar o MST em um gráfico conectado.
O algoritmo de Kruskal encontra um subconjunto de um gráfico G tal que:
- Ele forma uma árvore com cada vértice.
- A soma dos pesos é o mínimo entre todas as árvores abrangentes que podem ser formadas a partir deste gráfico.
A sequência de etapas para o algoritmo de Kruskal é dada da seguinte forma:
- Primeiro, classifique todas as arestas do menor peso para o maior.
- Pegue a aresta com o menor peso e adicione-a à árvore geradora. Se o ciclo for criado, descarte a aresta.
- Continue adicionando arestas como no passo 1 até que todos os vértices sejam considerados.
Pseudocódigo para Algoritmo de Kruskal
Abaixo está o pseudo-código para o Algoritmo de Kruskal
Agora vamos ver a ilustração do algoritmo de Kruskal.
Agora escolhemos a aresta com menor peso, que é 2-4.
Em seguida, escolha a próxima aresta mais curta 2-3.
Então, escolhemos a próxima aresta com a aresta mais curta e isso não cria um ciclo, ou seja, 0-3
framework orientado a dados em exemplo de webdriver selênio
O próximo passo é escolher a aresta mais curta para que não forme um ciclo. Este é 0-1.
Como podemos ver, cobrimos todos os vértices e temos uma árvore geradora com custo mínimo aqui.
A seguir, implementaremos o Algoritmo de Kruskal usando C ++.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int[V]; for (int i = 0; i Resultado:
A árvore de abrangência mínima (MST) de acordo com o algoritmo de Kruskal:
Borda: Peso
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Observe que usamos o mesmo gráfico de exemplo no programa que usamos na ilustração do algoritmo de Kruskal acima. Nesta implementação, fazemos uso de dois vetores; um para armazenar o gráfico e outro para armazenar a árvore de abrangência mínima. Encontramos recursivamente as arestas com menor peso e as adicionamos ao vetor MST até que todos os vértices sejam cobertos.
Algoritmo de Prim
O algoritmo de Prim é outro algoritmo para encontrar o mínimo que abrange a árvore de um gráfico. Em contraste com o algoritmo de Kruskal que começa com as bordas do gráfico, o algoritmo de Prim começa com um vértice. Começamos com um vértice e continuamos adicionando arestas com o mínimo de peso até que todos os vértices sejam cobertos.
A sequência de etapas para o Algoritmo de Prim é a seguinte:
- Escolha um vértice aleatório como vértice inicial e inicialize uma árvore geradora mínima.
- Encontre as arestas que se conectam a outros vértices. Encontre a aresta com peso mínimo e adicione-a à árvore geradora.
- Repita a etapa 2 até que a árvore de abrangência seja obtida.
Pseudocódigo para Algoritmo de Prim
Agora vamos ver uma ilustração para o algoritmo de Prim.
Para isso, estamos usando o mesmo gráfico de exemplo que usamos na Ilustração do algoritmo de Kruskal.
Vamos selecionar o nó 2 como vértice aleatório.
Em seguida, selecionamos a aresta com o menor peso de 2. Escolhemos a aresta 2-4.
Em seguida, escolhemos outro vértice que ainda não está na árvore de abrangência. Escolhemos a vantagem 2-3.
Agora vamos selecionar uma aresta com menos peso dos vértices acima. Temos a vantagem de 3-0 que tem menos peso.
A seguir, escolhemos uma aresta com o menor peso do vértice 0. Esta é a aresta 0-1.
Pela figura acima, vemos que agora cobrimos todos os vértices do gráfico e obtivemos uma árvore geradora completa com custo mínimo.
Agora vamos implementar o algoritmo do Prim em C ++.
Observe que também neste programa, usamos o gráfico de exemplo acima como entrada para que possamos comparar a saída fornecida pelo programa com a ilustração.
O programa é fornecido abaixo:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G[V][V] = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex[V]; // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex[0] = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G[x][y]; cout << endl; mst_vertex[y] = true; num_edge++; } return 0; }
Resultado:
A árvore de abrangência mínima de acordo com o algoritmo de Prim:
Borda: Peso
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Aplicações de Spanning Tree
Algumas das aplicações de árvores de alcance mínimo são as seguintes:
# 1) Configuração da rede de comunicações: Quando queremos configurar uma rede de comunicação usando links de comunicação, o custo de configurar links de comunicação entre dois pontos é melhor determinado usando um MST.
# 2) Análise de cluster: Ele pode ser usado para resolver o problema de agrupamento K encontrando uma árvore de abrangência mínima e excluindo as k-1 arestas mais caras.
# 3) Layout de redes rodoviárias / ferroviárias: Quando instalamos várias redes rodoviárias ou ferroviárias entre ou dentro das cidades, o custo do projeto é um fator muito importante. Podemos encontrar o melhor caminho com custo mínimo usando árvores de abrangência mínima.
# 4) Planejamento de instalações habitacionais: Instalações como eletricidade, água, esgoto, etc. a serem fornecidas a várias casas também precisam ter um custo ideal e isso é feito por meio de um MST.
# 5) Resolvendo o problema do caixeiro viajante: Podemos usar um MST para resolver o problema do caixeiro-viajante que exige uma visita a cada ponto pelo menos uma vez.
Conclusão
A árvore geradora mínima é o subconjunto do grafo ge este subconjunto possui todos os vértices do grafo e o custo total das arestas conectando os vértices é mínimo.
Discutimos dois algoritmos, ou seja, Kruskal e Prim, para encontrar a árvore de abrangência mínima do gráfico. Os aplicativos da Spanning Tree também foram explicados aqui neste tutorial.
=> Confira os melhores tutoriais de treinamento em C ++ aqui.
Leitura recomendada
- Tutorial de reflexão Java com exemplos
- Estrutura de dados da árvore B e da árvore B + em C ++
- Tutorial Python DateTime com exemplos
- Tutorial do Bugzilla: Tutorial prático da ferramenta de gerenciamento de defeitos
- Estrutura de dados de árvore binária em C ++
- 20+ Tutorial do MongoDB para iniciantes: curso gratuito do MongoDB
- Tutorial de fragmentação do MongoDB com exemplo
- MongoDB Create Database Tutorial