Минимальное связующее дерево
Граф, не имеющий направлений, называется неориентированным графом. Каждый граф должен иметь путь от одного узла к другому узлу. Остовное дерево также является неориентированным связным графом, в котором присутствуют все узлы графа с минимальным количеством ребер. Если остовное дерево не имеет всех узлов графа, то мы не можем сказать, что это остовное дерево. Суммарные веса остовного дерева будут меньше исходного веса графа, так как мы соединили его через ребра минимального веса. Покрывающее дерево также не имеет цикла. Любой граф имеет более одного остовного дерева, но только одно из них будет уникальным. Мы называем это минимальным остовным деревом, поскольку пытаемся создать полный граф со всеми узлами, сохраняя при этом низкий вес.
Мы можем нарисовать остовное дерево с помощью следующих двух методов:
- Kruskal’s algorithm
- Prim’s algorithm
В этой статье мы собираемся обсудить алгоритм Прима. Алгоритм Крускала будет рассмотрен в следующей статье.
Prims algorithm
Алгоритм Прима используется для нахождения минимального остовного дерева графа. Алгоритм примитива начинается с любого узла, а затем добавляет любой соседний узел с минимальным весом, и этот процесс продолжается до тех пор, пока не будут посещены все узлы в графах. При создании минимального остовного дерева графа мы также не должны создавать циклы, потому что циклов не должно быть в минимальном остовном дереве.
Шаги алгоритма Prims
Алгоритм прима использует жадный подход для минимального остовного дерева. Мы должны выбрать любую вершину графа, а затем выбрать следующую вершину смежности, чей вес меньше, и мы продолжаем этот процесс до тех пор, пока не соединим все узлы графа.
Шаг 1: Выберите любую исходную вершину в графе.
Шаг 2: Найдите ребро минимального веса, которое примыкает к источнику, а затем соедините его с остовным деревом.
Шаг 3: Повторяйте шаг 2, пока все узлы не будут добавлены в минимальное остовное дерево.
Пример:
Ниже приведен пример поиска минимального остовного дерева с использованием алгоритма Прима.
- Выбираем любой случайный узел из графа G и добавляем его в MST (минимальное остовное дерево). Мы выбираем здесь узел 0.
- Теперь мы выбираем то ребро, которое является смежным с исходным узлом (0), но с наименьшим весом, а затем добавляем этот узел с наименьшим весом в минимальное остовное дерево.
- Теперь мы выбираем то ребро, которое является смежным с исходным узлом (0 или 1), но с наименьшим весом, а затем добавляем этот узел с наименьшим весом в минимальное остовное дерево.
- Теперь мы выбираем то ребро, которое является смежным с исходным узлом (0, 1 или 3), но с наименьшим весом, а затем добавляем этот узел с наименьшим весом в минимальное остовное дерево.
- Теперь мы выбираем то ребро, которое является смежным с исходным узлом (0, 1, 3 или 4), но с наименьшим весом, а затем добавляем этот узел с наименьшим весом в минимальное остовное дерево.
- Теперь мы выбираем то ребро, которое является смежным с исходным узлом (0, 1, 3, 4 или 6), но с наименьшим весом, а затем добавляем этот узел с наименьшим весом в минимальное остовное дерево.
- Теперь мы выбираем то ребро, которое является смежным с исходным узлом (0, 1, 3, 4, 6 или 2), но с наименьшим весом, а затем добавляем этот узел с наименьшим весом в минимальное остовное дерево.
Выше наш окончательный MST (минимальное остовное дерево), а общая стоимость равна 6.
Программа C++ Prim MST (минимальное связующее дерево)
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
typedef std :: pair<int,int> SII;
typedef std :: vector<SII> SSII;
int PrimsMST (int sourceNode, std :: vector<SSII> & graph){
// This queue will store details of each node
// along with their weight value.
std :: priority_queue<SII, std :: vector<SII>, std :: greater<SII>> k;
k.push(std :: make_pair(0, sourceNode));
bool nodesAdded[graph.size()];
memset(nodesAdded, false, sizeof(bool)*graph.size());
int mst_tree_cost = 0;
while (!k.empty()) {
// We are selecting here the node which has minimum cost
SII itemNode;
itemNode = k.top();
k.pop();
int Node = itemNode.second;
int Cost = itemNode.first;
// Here we are checking if any node has not been added to the MST,
// then adding that node.
if (!nodesAdded[Node]) {
mst_tree_cost += Cost;
nodesAdded[Node] = true;
// Iterate over the negibour nodes which were recently taken
// out of the priority queue.
// and added to the MST which is not yet added
for (auto & pair_node_cost : graph[Node]) {
int adjency_node = pair_node_cost.second;
if (nodesAdded[adjency_node] == false) {
k.push(pair_node_cost);
}
}
}
}
return mst_tree_cost;
}
int main(){
// The details of the graph with cost and adjency node.
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 fromNode_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 Nodes (0 to 6)
std :: vector<SSII> primsgraph;
primsgraph.resize(num_of_nodes);
primsgraph[0] = fromNode_0_in_graph_1;
primsgraph[1] = fromNode_1_in_graph_1;
primsgraph[2] = fromNode_2_in_graph_1;
primsgraph[3] = fromNode_3_in_graph_1;
primsgraph[4] = fromNode_4_in_graph_1;
primsgraph[5] = fromNode_5_in_graph_1;
primsgraph[6] = fromNode_6_in_graph_1;
// As we already know, we have to choose the source vertex,
// so we start from the vertex 0 node.
std :: cout << «Total cost of minimum spanning tree after Prim’s algorithm : «
«» << PrimsMST(0, primsgraph) << std :: endl;
return 0;
}
Выход:
Total cost of minimum spanning tree after Prim‘s algorithm : 6
Process finished with exit code 0
Временная сложность алгоритма MST Prim
- Общее время, необходимое для обработки и выбора определенного узла очереди с приоритетом, который еще не добавлен в MST, составляет logV. Но поскольку это работает для каждой вершины, общая временная сложность составляет V (logV).
- Граф неориентированный, и общее количество ребер будет 2E. Поскольку мы должны поместить узлы в приоритетную очередь, это займет журнал общего времени (V). Однако, поскольку у нас есть в общей сложности 2E ребра, наша общая операция отправки будет 2E (log (V)).
- Общая сложность после операции 1 и 2 составляет O( (E + V ) log (V )).
Заключение
Мы изучили минимальное остовное дерево Prim, которое большинство людей предпочитает в первую очередь, когда им нужно найти граф MST из графа. Алгоритм Prim прост для понимания и реализации в реальном приложении. Алгоритм Prim очень полезен в реальных приложениях, например, при соединении железнодорожных путей с целыми городами. Так что это всего лишь один пример, но его применение огромно, поэтому мы должны понять этот алгоритм.
