Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
, если вершина 
уже включена в остов,
, если 
– ближайшая к уже включенная в остов вершина.
За один просмотр массива 
(
ЭШ) можно выделить очередное ребро минимального остова –
это минимальное по весу ребро типа 
, где 
.
Пусть это ребро 
и его вес равен 
.
=>
Если 
, то ребро действительно содержится в графе и его нужно добавить в остов (вместе с вершиной 
).
После этого необходимо перестроить массив (за 1 проход): для каждой пока не включенной в остов вершины проверить, не будет ли ребро 
легче, чем .
Если 
, то это означает, что исходный граф несвязный, и было выделено одно из поддеревьев остова. Построение следующего поддерева можно начинать с любой вершины , для которой .
Для несвязного графа возможен и другой вариант: временно включить в остов фиктивное ребро с ; продолжить построение, пока остов не будет содержать 
ребро, затем исключить все ребра с весом 
(фиктивные).
Алгоритм Прима для графа с матрицей весов C:
for (B[1] = 0, i = 2; i <= n; i++) B[i] = 1;
for (i = 1; i < n; i++) { // цикл включения ребер
cm = MAX; vm = 0;
for (j = 1; j <= n; j++) { // поиск мин. ребра
if (B[j]!=0 && (vm==0 || cm>C[j][B[j]]))
{ vm = j; cm = C[j][B[j]]; }
}
добавить_ребро_к_остову(vm, B[vm]);
for (B[vm] = 0, j = 1; j <= n; j++) {
if(B[j]!=0 && C[j][B[j]]>C[j][vm]) B[j]=vm;
}
}
удалить_фиктивные_ребра();
Трудоемкость данного алгоритма составляет 
.
Алгоритм Крускала
Данный алгоритм выгодно использовать, если исходный граф содержит относительно немного ребер, которые лучше задавать массивом троек 
.
Все ребра сортируются по весу и последовательно проверяются, начиная от самого легкого: если очередное ребро не образует цикла в уже построенной части остова, то оно добавляется в остов, иначе отбрасывается.
Процесс продолжается, пока не будет получено ребро (для связного графа), либо пока не будут просмотрены все ребра (для несвязного).
Сортировка требует 
ЭШ, поэтому если 
, то для выделения мин. ребер выгоднее построить бинарную кучу.
Для проверки, приводит ли добавление ребра 
к образованию цикла, формируются (и последовательно объединяются) множества связных вершин: вершины 
и 
принадлежат одному множеству, если 
путь из в , состоящий из уже выделенных ребер остова.
 |
: ребро 
образует цикл в 
– недопустимое,
: ребро соединяет точки из разных множеств. может быть добавлено к остову, при этом и 
объединятся в одно множество.
Быстрое объединение множеств
Множества вершин удобно представлять в виде деревьев принадлежности вершин со ссылкой от «сына» к «отцу» и хранить ссылки в целочисленном массиве 
:
- начальные значения 
(отдельные корни деревьев),
- далее – только для корней, иначе 
– это «отец» .
По ссылкам можно пройти от вершины до корня, а корень однозначно определяет множество вершин.
=>
При проверке ребра необходимо:
- найти корни множеств, содержащих вершины и ,
- если корень() = корень(), то обе вершины принадлежат одному множеству, т. е. ребро образует цикл,
- если корень() 
корень(), то ребро добавляется в остов, а 2 множества объединяются путем формирования в ссылки с одного корня на другой.
Пример построения деревьев принадлежности (порядок выбора ребер (1,2), (6,7), (4,5), (3,6), (1,4), (2,4), (2,6)):
 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | 3 | 1 | 4 | 3 | 6 |
| 1 | 1 | 1 | 1 | 4 | 3 | 6 |
Чтобы деревья при объединении не вырождались в линейный список, нужно меньшее дерево делать поддеревом большего.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)