Анимация препроцессинга и алгоритма

1.

Препроцессинг
Цвет для пунктирных стрелочек и второй вершины, hex: #8AD554
Цвет для сплошной стрелочки и третьей вершины, hex: #54A520
Цвет для первой вершины, hex: #FFCC00
Цвет для вершин по умолчанию hex: #B6D1D9
Алгоритм
Цвет для подъема при поиске наименьшего общего предка, hex:
#2A88E1
Цвет для неудачных прыжков, hex: #F83A3A
Цвет для удачных прыжков, hex: #54A520
Цвет для подъема вершины u, hex: #FFCC00
Цвет для вершин по умолчанию hex: #B6D1D9

2.

Препроцессинг
Поле для логов запуска
алгоритма
Кол-во детей у #1:
2
Кол-во детей у #2:
1
Кол-во детей у #3:
3
1
2
4
8
9
3
5
6
7

3.

Визуализация алгоритма – шаг 0. Выделение u, v
Поле для логов запуска
алгоритма
Кол-во детей у #1:
2
Кол-во детей у #2:
1
Кол-во детей у #3:
3
1
2
3
5
4
8
9
v
6
7
u

4.

Шаг 1 – свап u и v, если нужен для того, чтобы глубина u была не меньше глубины v
Поле для логов запуска
алгоритма
Кол-во детей у #1:
2
Кол-во детей у #2:
1
Кол-во детей у #3:
3
1
2
3
5
4
8
9
u
6
7
v

5.

Шаг 2 – Подъем u до достижения глубины вершины v, по степеням двойки, начиная со старшей.
При каждом присваивании новая вершина u красится в желтый цвет, буква u перемещается к ней, а старая
вершина красится в цвет остальных вершин. Старая и новая вершины и соединены стрелкой желтого цвета,
подписанной длиной прыжка (1, 2, 4 и тд)
1
2
4
2
8
9
3
u5
6
7
v

6.

Шаг 2 – Когда подъем закончился, вершину u красим в тот же цвет, что и v
1
2
4
8
9
3
u 5
6
7
v

7.

1
2
4
16
6
7
3
Шаг 3. Поиск общего предка. Начинается одновременный
параллельный подъем вершин u и v двоичными прыжками
(некоторые из них неудачные). Прыжки идут с шагом степеней
двойки, от большей к меньшей. Выше корня не поднимаемся.
5
Если прыжок на степень двойки из вершин u, v попадает в одну и
ту же вершину, прыжок считается неудачным. Иначе удачным.
А) Анимация неудачных прыжков: вершина, куда был прыжок,
16 подсвечивается красным цветом, а также рисуются стрелки от
9
вершин u и v до этой вершины красным цветом. Рядом со
стрелками пишется длина прыжка, в данном случае 16.
8
10
11
12
13
14
u
1
15
3
v

8.

1
3
2
4
6
4
Шаг 3. Поиск общего предка.
Б) Анимация удачных прыжков: вершины, куда были
прыжки, подсвечивается зеленым цветом, буквы u, v
передвигаются к ним, а также рисуются стрелки от старых
вершин u и v до новых зеленым цветом. Рядом со стрелками
пишется длина прыжка, в данном случае 4.
u
5
7
v
8
9
10
11
12
13
14
1
15
3
4

9.

Схема странички
Предполагаем, что вершины перечислены от 1 до n, а 1 это корень дерева. Введите данные графа ниже, указав для
каждой вершины количество её детей и укажите ниже
номера двух вершин u и v для поиска их наименьшего
общего предка.
Node #u =
Node #v =
Препроцессинг
Картинка из
конфига
Тут граф
1
Поле для логов
2
4
8
3
5
6
7
v
Кол-во детей у #1:
2
Кол-во детей у #2:
1
Кол-во детей у #3:
3