Моделирование. Списки и деревья. Графы

Оптимальный маршрут (стр. 113)
Березовое: 8:00
Полевое
Б
16:00
07:30
11:50
14:00
14:40
16:10

Что такое дерево?
Дерево – это структура данных, которая служит моделью многоуровневой структуры (иерархии).
Лес – это несколько деревьев.

Из чего состоит дерево?
A –
D, E, F, G –
корень
листья
B, C –
промежуточные
узлы
Путь — это последовательность узлов, где каждый следующий связан с предыдущим.
Высота дерева — это наибольшая длина пути от корня дерева к листу.

Родители и дети
B – родитель для D и E
D и E – сыновья для B
Предок – потомок: между ними есть путь.
A и B – предки для D и E
B, D и E – потомки для A
Родитель – сын: между ними есть ребро.

Кратчайший путь (перебор)
A
B
С
E
С
D
С
D
E
D
2
4
6
2
4
6
1
3
1
3
9
7
5
8
4
1
3
7
дерево возможных путей
Определите кратчайший путь между пунктами A и D.
Ответ: 7

Задача

Задача
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С.
A
B
С
D
С
С
D
1
4
3
1
4
3
2
3
3
6
3
6
9
3
D
6
5
E
2
8
С
Ответ: 8

Количество путей из А в Ж
1
1
1
1+1+1=3
1
1+1+1+1+3=7
1

Задача
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город В?

Задача
А → К через В
1) вычеркнем те дороги, которые минуют город В:
Решение:

Задача
А → К через В
Решение:
1
2
2
4
2
4
10
К= Д+Е+Ж = 2+4+4 = 10
Ответ: 10

Задача
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Д?

Задача
А → К через Д?
Решение: