minimum spanning tree tutorial
У овом водичу за Ц ++ објашњено је шта је минимално распрострањено стабло (МСТ) заједно са Примовим и Крускаловим алгоритмима за проналажење МСТ-а у графикону и његове примене:
Распростируће се дрво може дефинисати као подскуп графа који се састоји од свих темена који покривају минимално могуће ивице и нема циклус. Повезивање стабла не може се прекинути.
Сваки повезани и неусмерени граф има бар једно стабло у распону. Неповезани граф нема распонско стабло, јер није могуће укључити све врхове.
=> Погледајте овде како бисте истражили целу листу водича за Ц ++.
Шта ћете научити:
Растезно дрво у Ц ++
Размотрите следећи повезани граф.
Као што је горе приказано, за дати повезани Граф који садржи 3 темена имамо три распона стабала. Генерално, ако је Н број чворова у графикону, тада комплетни повезани граф има максимум НН-2број распрострањених стабала. Дакле, у горњем графикону Н = 3, према томе, он има 3(3-2)= 3 распрострањена стабла.
У наставку су наведена нека својства растућег стабла:
- Повезани граф може имати више стабала која се протежу.
- Сва распрострањена стабла у графикону имају једнак број чворова и ивица.
- Ако уклонимо једну ивицу са растегнутог стабла, тада ће постати минимално повезан и учиниће да граф буде искључен.
- С друге стране, додавањем једне ивице дрвећу које растеже то ће учинити максимално ацикличан чиме се ствара петља.
- Распростируће се дрво нема петљу или циклус.
Шта је минимално растезно дрво (МСТ)
Минимално растегљиво дрво је оно које садржи најмању тежину међу свим осталим растегљивим стаблима повезаног пондерисаног графа. За граф може постојати више од једног минималног распона.
Постоје два најпопуларнија алгоритма која се користе за проналажење минималног распона у графу.
То укључује:
- Крускалов алгоритам
- Примов алгоритам
Размотримо оба ова алгоритма!
Крускал’с Алгоритхм
Крускалов алгоритам је алгоритам за проналажење МСТ у повезаном графу.
Крускалов алгоритам проналази подскуп графа Г такав да:
- Чини дрво са сваким врхом у себи.
- Збир тежина је најмањи међу свим распрострањеним стаблима која се могу формирати из овог графикона.
Редослед корака за Крускалов алгоритам дат је на следећи начин:
- Прво сортирајте све ивице од најмање тежине до највише.
- Узмите ивицу са најмањом тежином и додајте је на растегнуто дрво. Ако је циклус креиран, одбаците ивицу.
- Наставите да додајете ивице као у кораку 1 док се не узму у обзир сви врхови.
Псеудокод за Крускалов алгоритам
Доље је дат псеудокод за Крускалов алгоритам
Сада да видимо илустрацију Крускаловог алгоритма.
Сада бирамо ивицу са најмањом тежином која је 2-4.
Затим одаберите следећу најкраћу ивицу 2-3.
Тада бирамо следећу ивицу са најкраћом ивицом и то не ствара циклус, тј. 0-3
бесплатни видео довнлоадер са било које странице пуне верзије
Следећи корак је одабир најкраће ивице тако да не формира циклус. Ово је 0-1.
Као што видимо, покрили смо све темене и овде имамо растегнуто дрво са минималним трошковима.
Даље ћемо применити Крускалов алгоритам користећи Ц ++.
#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 Излаз:
Минимално дрво распона (МСТ) према Крускаловом алгоритму:
Руб: Тежина
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Имајте на уму да смо у програму користили исти пример графа као и на илустрацији Крускал-овог алгоритма изнад. У овој имплементацији користимо два вектора; један за чување графа, а други за чување минималног распона стабла. Рекурзивно проналазимо ивице са најмањом тежином и додајемо их МСТ вектору док нису покривени сви врхови.
Примов алгоритам
Примов алгоритам је још један алгоритам за проналажење минимума који обухваћа стабло графа. За разлику од Крускаловог алгоритма који започиње ивицама графа, Примов алгоритам започиње теменом. Почињемо са једним теменом и настављамо да додајемо ивице са најмањом тежином док сви врхови не буду покривени.
Редослед корака за Примов алгоритам је следећи:
- Изаберите случајни врх као почетни врх и иницијализујте минимално обухватно стабло.
- Пронађите ивице које се повезују са другим теменима. Пронађите ивицу са минималном тежином и додајте је на растегнуто дрво.
- Понављајте корак 2 док се не добије распрострањено стабло.
Псеудоцоде за Прим’с Алгоритхм
Сада да видимо илустрацију Прим-овог алгоритма.
За ово користимо исти пример графикона који смо користили у Илустрацији Крускаловог алгоритма.
Одаберемо чвор 2 као случајни врх.
Даље, бирамо ивицу са најмањом тежином од 2. Бирамо ивицу 2-4.
Даље, бирамо други врх који још увек није у распону стабла. Изаберемо ивицу 2-3.
Сада ћемо одабрати горњу ивицу са најмањом тежином. Имамо ивицу 3-0 која има најмању тежину.
Даље, бирамо ивицу са најмањом тежином из темена 0. Ово је ивица 0-1.
Из горње слике видимо да смо сада покрили све врхове на графикону и добили цело дрво са минималним трошковима.
Сада ћемо применити Примов алгоритам у Ц ++.
Имајте на уму да смо и у овом програму користили горњи пример графикона као улаз како бисмо могли упоредити излаз који даје програм заједно са илустрацијом.
Програм је дат у наставку:
#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; } Излаз:
Минимално дрво распона према Примовом алгоритму:
Руб: Тежина
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Примене распрострањеног дрвета
Неке од примена дрвећа са минималним распоном су следеће:
# 1) Постављање комуникационе мреже: Када желимо да успоставимо комуникациону мрежу помоћу комуникационих веза, тада се трошак постављања комуникационих веза између две тачке најбоље одређује помоћу МСТ-а.
# 2) Кластер анализа: Може се користити за решавање проблема К-кластерисања проналажењем минималног распрострањеног стабла и брисањем к-1 најскупљих ивица.
# 3) Постављање путних / железничких мрежа: Када постављамо разне путне или железничке мреже између или унутар градова, цена пројекта је веома важан фактор. Најбољу стазу са минималним трошковима можемо пронаћи користећи минимално растегнута стабла.
# 4) Планирање стамбених објеката: Објекти као што су струја, вода, канализација итд. Који се обезбеђују за бројне куће такође морају да имају оптималне трошкове, а то се ради помоћу МСТ-а.
# 5) Решавање проблема путујућег продавца: Можемо користити МСТ за решавање проблема трговца путника који захтева посету сваке тачке бар једном.
Закључак
Минимално стабло распона је подскуп графа г и овај подскуп има све вертикалне тачке графа, а укупни трошак ивица који повезују темена је минималан.
Разговарали смо о два алгоритма, тј. О Крускаловом и Примовом, како бисмо пронашли минимално распонско стабло на графикону. Примене растегнутог стабла су такође овде објашњене у овом упутству.
=> Овде погледајте најбоље туторијале за Ц ++.
Препоручено читање
- Водич за Јава рефлексију са примерима
- Структура података Б Трее и Б + Трее у Ц ++
- Водич за Питхон ДатеТиме са примерима
- Водич за Бугзилла: Практични приручник за алат за управљање недостацима
- Структура података бинарног стабла у језику Ц ++
- 20+ МонгоДБ лекција за почетнике: бесплатан курс МонгоДБ
- МонгоДБ Водич за осенчење са примером
- МонгоДБ Водич за креирање базе података
