Алгоритмы обхода связного графа

79. Перечислить вершины графа в порядке обхода а) в глубину; в) в ширину.

80. Граф задан матрицей смежности. Найти

∙ Какой-либо путь из вершины 2 в вершину 4;

∙ кратчайший путь из вершины 2 в вершину 4;

∙ кратчайшие пути из вершины 2 ко всем остальным вершинам.

81. На планете Глюк живет группа людей. Про некоторые пары людей известно, что они близкие родственники. Назовем А и В родственниками, если А и В близкие родственники, или найдется третий человек С, который по отдельности является родственником А и родственником В. Опишите алгоритм нахождения всех родственников человека Х.

82. На клетчатом листе бумаги размером 10 х 10 закрашены некоторые клетки. Разрешается ходить по не закрашенным клеткам, переходя на каждом шаге вверх, вниз, вправо или влево. Описать алгоритм, отвечающий на следующие вопросы:

А. Есть ли путь из левой нижней клетки в правую верхнюю;

Б. Какое минимальное число шагов нужно сделать, чтобы пройти этот путь;

В. По каким клеткам при этом надо идти

83. В двузначном числе за один ход разрешается заменить любую цифру суммой цифр по модулю 10. Заданы два двузначных числа a и b. Написать программу, которая определяет: можно ли построить цепочку ходов, которая переводит a в b; минимальную такую цепочку. В двузначном числе старшая цифра может быть и нулем.

84. На шахматной доске N х N, несколько клеток, которой вырезано, заданы две клетки. Построить минимальный путь коня из одной данной клетки в другую.

85. В таблице N x N, где N<13, клетки заполнены случайным образом цифрами от 0 до 9. Предложить алгоритм, позволяющий найти маршрут из клетки (1,1) в клетку (N,N) и удовлетворяющий следующим условиям:

∙ любые две последовательные клетки в маршруте имеют общую сторону;

∙ количество клеток маршрута минимально;

∙ из всех маршрутов, удовлетворяющих условиям 1) и 2), искомый маршрут тот, сумма цифр в клетках которого максимальна.

86. Имеются три пробирки. Вместимость каждой из них 100 миллилитров. Две пробирки из трех одинаково размечены. Деления нанесены произвольно и соответствуют целым количествам миллилитров. Изначально одна из пробирок с делениями наполнена 100 миллилитрами кваса, а остальные пустые. Описать алгоритм, который выясняет, можно ли поместить в пробирку без делений один миллилитр кваса и, если да, то находит минимальное число необходимых для этого переливаний. Каждое переливание из одной пробирки в другую можно проводить до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какого-либо деления.

87. Имеется расписание беспосадочных авиарейсов. Составить оптимальный алгоритм определяющий, можно ли из пункта А попасть в пункт В.

88. Имеется атлас автомобильных дорог с указанием расстояний между городами. Составить оптимальный алгоритм нахождения минимального пути между двумя городами.