![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Программа 20.9. Алгоритм Борувки построения дерева MTS
РИСУНОК 20.14. АЛГОРИТМ БОРУВКИ ПОСТРОЕНИЯ ДЕРЕВА MTS На диаграмме вверху показаны ориентированные ребра, проведенные из каждой вершины в ближайшие к ним соседние вершины. Ив этой диаграммы следует, что ребра 0-2, 1-7 и 3-5 являются самыми короткими ребрами, инцидентные обоим их вершинам, 6-7 есть кратчайшее ребро для вершины б, а 4-3 — кратчайшее ребро для вершины 4. Все эти ребра содержатся в дереве MTS и образуют лес поддеревьев MTS (диаграмма в центре), который вычисляется на первом этапе выполнения алгоритма Борувки. На втором этапе этот алгоритм завершает вычисление поддеревьев MTS (диаграмма внизу) добавлением ребра 0-7, которое является кратчайшим ребром, инцидентным каждой вершине тех поддеревьев, которые он соединяет между собой, и ребра 4- 7, которое является кратчайшим ребром, инцидентным каждой вершине нижнего поддерева. Часть 5. Алгоритмы на графах
vector< Edge *> a, b, mst; UF uf; public: MST (const Graph & G): G(G), uf(G.V()), mst(G.V<)+l) {a = edges< Graph, Edge> (G); int N, к «1; for (int E = a.size(); E! = 0; E = N) { int h, i, j;
|