Часть 5. Алгоритмы на графах. > 20.8.Разработайте класс WeightedEdge(взвешенное ребро), который реализует интер­ фейс EDGE(ребро) из программы 20.1 и содержит функцию-элемент

> 20.8. Разработайте класс WeightedEdge (взвешенное ребро), который реализует интер­
фейс EDGE (ребро) из программы 20.1 и содержит функцию-элемент show, которая
производит распечатку ребер и их весов в формате, используемом в рисунках этой
главы.

> 20.9. Реализуйте класс io для взвешенных графов, в котором имеются функции-эле­
менты show, scan и scanEZ (см. программу 17.4).

> 20.10. Постройте АТД графа, который использует целочисленные веса и в то же время
отслеживает минимальные и максимальные веса в графе и содержит функцию АТД,
которая всегда возвращает веса, представляющие собой вещественные числа в диапа­
зоне от 0 до 1.

> 20.11. Спроектируйте интерфейс, подобный используемому в программе 20.1, кото­
рый позволил бы клиентам и реализациям манипулировать типами данных Edge (но не
указателями на них).

о 20.12. Разработайте реализацию интерфейса, предложенного вами в упражнении 20.11, который использует представление графа в виде минимальной матрицы весов, в ко­торой функция итератора nxt использует информацию, неявно содержащуюся в ин­дексах строк и столбцов, для создания типа данных Edge, что обеспечивает возмож­ность возвращать его значения клиентской программе.

20.13. Реализуйте класс итератора с целью его использования в программе 20.5 (см. программу 20.4).

о 20.14. Разработайте реализацию интерфейса, построенного вами в упражнении 20.11, которая использует минимальное представление графа в виде списков смежных вер­шин, где узлы списка содержат вес и вершину назначения (но не вершину-источник), а функция итератора nxt использует неявную информацию для создания типа данных Edge, что обеспечивает возможность возвращать его значения клиентской программе.

20Л5. Внесите изменения в генератор разреженных случайных графов из программы

17.12, которые позволили бы присваивать ребрам случайные веса (из диапазона от 0
до 1).

> 20.16. Внесите изменения в генератор насыщенных случайных графов из программы

17.13, которые позволили бы присваивать ребрам случайные веса (из диапазона от 0
до 1).

20.17. Напишите программу, которая генерирует случайные взвешенные графы путем
соединения вершин, упорядоченных в виде решетки √ V на √ V, с соседними вер­
шинами (как изображенная на рис. 19.3, но для случая неориентированного графа),
при этом каждому ребру присваивается случайный вес (принимающий значение из
диапазона от 0 до 1).

20.18. Напишите программу генерации случайных полных графов, ребрам которых
присвоены веса, выбранные по распределению Гаусса.

• 20.19. Напишите программу, которая генерирует V случайных точек на плоскости во время построения взвешенного графа за счет соединения каждой пары точек, распо­ложенных друг от друга на расстоянии d и ближе, ребрами, весом которых является это расстояние (см. упражнение 17.74). Определите, какое должно быть установлено расстояние d, чтобы ожидаемое число ребер было равно Е.