Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 21. Кратчайшие пути. о 21.7.Разработайте генератор насыщенных (плотных) случайных сетей, основанный на программе 17.13, и генератор весов ребер по методике
о 21.7. Разработайте генератор насыщенных (плотных) случайных сетей, основанный на программе 17.13, и генератор весов ребер по методике, описанной в упражнении 21.6. Напишите клиентские программы, порождающие случайные сети для обоих распределений веса с так подобранным набором значений К и Е, чтобы можно было использовать их для выполнения эмпирических тестов на графах, получаемых из упомянутых моделей. 21.8. Реализуйте независимую от представления сети клиентскую функцию, которая строит сеть, получая из стандартного ввода ребра с весами (пары целых чисел из диапазона от 0 до V- 1 с весами между 0 и 1). • 21.9. Напишите программу, которая генерирует V случайных точек на плоскости, затем строит сеть с ребрами (в обоих направлениях), соединяющими все пары точек, расположенных на расстоянии, которое не превышает заданное d (см. упражнение 17.74), и устанавливает вес каждого ребра равным расстоянию между двумя точками, соединенными этим ребром. Определите, как установить d, чтобы ожидаемое число ребер было равно Е. о 21.10. Разработайте базовый класс и производные классы, реализующие АТД для графов, которые могут быть неориентироваными или ориентированными, взвешенными или невзвешенными и насыщенными или разреженными. > 21.11. Назначение следующей таблицы из опубликованной дорожной карты — дать длину кратчайших маршрутов, соединяющих города. Она содержит ошибку. Откорректируйте таблицу. Добавьте также таблицу в стиле рис. 21.4, которая показывает, как проследовать по кратчайшему маршруту.
|