minimum spanning tree tutorial
Този урок за C ++ обяснява какво е минимално обхващащо се дърво (MST) заедно с алгоритмите на Prim и Kruskal за намиране на MST в графика и неговите приложения:
Обхватното дърво може да бъде дефинирано като подмножество на графика, която се състои от всички върхове, покриващи минимално възможните ръбове и няма цикъл. Обхващащото дърво не може да бъде изключено.
Всяка свързана и неориентирана графика има поне едно обхващащо дърво. Прекъснатата графика няма обхващащо дърво, тъй като не е възможно да се включат всички върхове.
=> Вижте тук, за да разгледате пълния списък с уроци за C ++.
Какво ще научите:
Обхващащо дърво в C ++
Помислете за следната свързана графика.
Както е показано по-горе, за дадената свързана графика, съдържаща 3 върха, имаме три обхванати дървета. По принцип, ако N е броят на възлите в графика, тогава пълната свързана графика има максимум NN-2брой обхванати дървета. По този начин в горната графика N = 3, следователно има 3(3-2)= 3 обхващащи дървета.
Някои от свойствата на обхващащото дърво са изброени по-долу:
- Свързаната графика може да има повече от едно обхващащи дървета.
- Всички обхващащи дървета в графика имат еднакъв брой възли и ръбове.
- Ако премахнем единия ръб от обхващащото дърво, той ще стане минимално свързани и ще направи графиката прекъсната.
- От друга страна, добавянето на един ръб към обхващащото дърво ще го направи максимално ацикличен като по този начин създава цикъл.
- Обхващащото дърво няма цикъл или цикъл.
Какво е минимално обхващащо дърво (MST)
Минимално обхващащо дърво е това, което съдържа най-малко тегло сред всички други обхващащи дървета на свързана претеглена графика. За графика може да има повече от едно минимално обхващащо дърво.
Има два най-популярни алгоритма, които се използват за намиране на минималното обхващащо дърво в графика.
Те включват:
- Алгоритъмът на Крускал
- Алгоритъм на Prim
Нека обсъдим и двата алгоритма!
Алгоритъм на Крускал
Алгоритъмът на Крускал е алгоритъм за намиране на MST в свързана графика.
Алгоритъмът на Крускал намира подмножество на графика G, така че:
- Той образува дърво с всеки връх в него.
- Сборът от теглата е минимумът между всички обхващащи дървета, които могат да се формират от тази графика.
Последователността на стъпките за алгоритъма на Крускал е дадена, както следва:
- Първо сортирайте всички ръбове от най-ниското до най-високото тегло.
- Вземете ръба с най-ниското тегло и го добавете към дървото. Ако цикълът е създаден, изхвърлете ръба.
- Продължавайте да добавяте ръбове, както в стъпка 1, докато се разгледат всички върхове.
Псевдокод за алгоритъма на Крускал
По-долу е даден псевдокодът за алгоритъма на Крускал
Сега нека видим илюстрацията на алгоритъма на Крускал.
Сега избираме ръба с най-малко тегло, което е 2-4.
След това изберете следващия най-кратък ръб 2-3.
След това избираме следващия ръб с най-късия ръб и това не създава цикъл, т.е. 0-3
кои са най-добрите vr приложения за android
Следващата стъпка е да изберете най-късия ръб, така че да не образува цикъл. Това е 0-1.
Както виждаме, ние покрихме всички върхове и тук имаме обхващащо дърво с минимални разходи.
След това ще приложим алгоритъма на Kruskal’s, използвайки 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 Изход:
Минималното обхващащо дърво (MST) според алгоритъма на Крускал:
Ръб: Тегло
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Имайте предвид, че ние използвахме същата примерна графика в програмата, както в илюстрацията на алгоритъма на Крускал по-горе. В това изпълнение използваме два вектора; един за съхраняване на графика и друг за съхраняване на минималното обхващащо дърво. Рекурсивно намираме ръбовете с най-малко тегло и ги добавяме към MST вектора, докато всички върхове бъдат покрити.
Prim’s Algorithm
Алгоритъмът на Prim е още един алгоритъм за намиране на минимума, обхващащ дървото на графика. За разлика от алгоритъма на Kruskal, който започва с ръбове на графика, алгоритъмът на Prim започва с връх. Започваме с един връх и продължаваме да добавяме ръбове с най-малко тегло, докато всички върхове бъдат покрити.
Последователността на стъпките за Prim’s Algorithm е както следва:
- Изберете произволен връх като начален връх и инициализирайте минимално обхващащо дърво.
- Намерете ръбовете, които се свързват с други върхове. Намерете ръба с минимално тегло и го добавете към обхващащото дърво.
- Повторете стъпка 2, докато се получи обхващащото дърво.
Псевдокод за Prim’s Algorithm
Сега нека видим илюстрация за алгоритъма на Prim.
За това използваме същата примерна графика, която използвахме в илюстрацията на алгоритъма на Крускал.
Нека изберете възел 2 като произволен връх.
След това избираме ръба с най-малко тегло от 2. Избираме ръб 2-4.
След това избираме друг връх, който все още не е в обхващащото дърво. Избираме ръба 2-3.
Сега нека изберем ръб с най-малко тегло от горните върхове. Имаме край 3-0, който има най-малко тегло.
След това избираме ръб с най-малко тегло от връх 0. Това е ръбът 0-1.
От горната фигура виждаме, че сега сме обхванали всички върхове в графиката и сме получили цялостно обхващащо дърво с минимални разходи.
Сега нека приложим алгоритъма на Prim в C ++.
Имайте предвид, че и в тази програма използвахме горната примерна графика като вход, за да можем да сравним резултата, даден от програмата, заедно с илюстрацията.
Програмата е дадена по-долу:
#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; } Изход:
Минималното обхващащо дърво според алгоритъма на Prim:
Ръб: Тегло
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Приложения на Spanning Tree
Някои от приложенията на Minimum Spanning Trees са както следва:
# 1) Настройка на комуникационната мрежа: Когато искаме да създадем комуникационна мрежа, използваща комуникационни връзки, тогава разходите за създаване на комуникационни връзки между две точки се определят най-добре с помощта на MST.
# 2) Клъстер анализ: Може да се използва за решаване на проблема с K-клъстерирането чрез намиране на минимално обхващащо дърво и изтриване на k-1 най-скъпите ръбове.
# 3) Определяне на пътни / железопътни мрежи: Когато полагаме различни пътни или железопътни мрежи между или в градовете, цената на проекта е много важен фактор. Можем да намерим най-добрия път с минимални разходи, като използваме минимални обхващащи дървета.
# 4) Планиране на жилищни съоръжения: Съоръжения като електричество, вода, канализация и др., Които трябва да бъдат предоставени на редица къщи, също изискват оптимални разходи и това се прави с помощта на MST.
# 5) Решаване на проблема с пътуващия продавач: Можем да използваме MST, за да разрешим проблема с пътуващия продавач, който изисква да посетите всяка точка поне веднъж.
Заключение
Минималното обхващащо дърво е подмножеството на графика g и това подмножество има всички върхове на графиката и общата цена на ръбовете, свързващи върховете, е минимална.
Обсъдихме два алгоритма, т.е. Kruskal’s и Prim’s, за да намерим минималното обхващащо дърво от графиката. Приложенията на обхващащото дърво също са обяснени тук в този урок.
=> Вижте най-добрите уроци за обучение на C ++ тук.
Препоръчително четене
- Урок за отражение на Java с примери
- Структура на данните от B Tree и B + Tree в C ++
- Урок за Python DateTime с примери
- Урок за Bugzilla: Ръчен урок за инструмент за управление на дефекти
- Структура на данните на двоичното дърво в C ++
- 20+ MongoDB урок за начинаещи: Безплатен курс на MongoDB
- MongoDB Урок за оцветяване с пример
- MongoDB Създаване на урок за база данни
