Глава 18. Поиск на графе. 18.62.Разработайте реализацию АТД графа, представленного списками смежных вер­шин, которая содержит ребра (а не только их вершины назначения) в списках

18.62. Разработайте реализацию АТД графа, представленного списками смежных вер­шин, которая содержит ребра (а не только их вершины назначения) в списках, а за­тем реализуйте на графе поиск, основанный на стратегии, описанной в упражнении 18.61, который посещает каждое ребро и в то же время разрушает граф, воспользо­вавшись тем обстоятельством, что вы можете перемещать ребра всех вершин в бахрому за счет изменения одной связи.

• 18.63. Докажите, что рекурсивный поиск в глубину (программа 18.3) эквивалентен
обобщенному поиску на графе с использованием стека (программа 18.10) в том смыс­
ле, что обе программы посещают все вершины всех графов в одном и том же поряд­
ке тогда и только тогда, когда эти программы просматривают списки смежных вер­
шин в обратных порядках.

18.64. Предложите три различных порядка обхода при рандомизированном поиске на
графе

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

18.65. Может ли рандомизированный поиск наносить визиты вершинам графа

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

в порядке следования их индексов? Докажите правильность вашего ответа.

18.66. Воспользуйтесь библиотекой STL для построения обобщенной очереди ребер
графа, которая не принимает ребер с дублированными вершинами, используя для этой
цели стратегию игнорирования новых элементов.

о 18.67. Разработайте алгоритм рандомизированного поиска на графе, который выби­рает из накопителя то или иное ребро с равной вероятностью. Указание, См. программу 18.8.

о 18.68. Дайте описание стратегии обхода лабиринта, которая соответствует использо­ванию стека магазинного типа в обобщенном поиске на графе (см. раздел 18.1).

о 18.69. Снабдите обобщенный поиск на графе (см. программу 18.10) инструментальны­ми средствами, позволяющими вывести на печать значения высоты дерева и процен­тное отношение просмотренных ребер каждой просматриваемой вершины.

• 18.70. Проведите эксперименты с целью определить эмпирическим путем среднее зна­
чения количественных величин, описанных в упражнении 18.69, применительно к
обобщенному поиску на графе с использованием случайной очереди в графах различ­
ных размеров (см. упражнения 17.64—17.76).

• 18.71. Реализуйте производный класс, строящий динамические графические анима­
ции обобщенного поиска на графе, в которой с каждой вершиной ассоциируется ко­
ординаты (х, у) (см. упражнения 17.55—17.59). Протестируйте полученную программу
на случайных эвклидовых графах с близкими связями, используя столько точек, сколь­
ко сможете обработать за приемлемый промежуток времени. Ваша программа долж­
на строить изображения, подобные диаграммам, представленным на рис. 18.13, 18.24
и 18.29; свобода выбора различных цветов вместо степеней серого для обозначения
дерева, бахромы и непросмотренных вершин и ребер остается за вами.