![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. конкретной задачи, то алгоритмы объединения-поиска, которые мы рассматривали в главе 1, самые быстрые
Обозначения U - взвешенное быстрое объединение посредством сжатия пути делением пополам (программа 1.4) I - начальная конструкция представления графа D - рекурсивный поиск в глубину В - поиск в ширину (программа 18.9) * - выход, когда установлен факт полной связности графа
Во-первых, из таблицы ясно, что не следует использовать представление графа в виде матрицы смежности в случае разреженных графов больших размеров (и нельзя его использовать применительно к очень большим графам), причем не только в силу того, что затраты на инициализацию матрицу неприемлемы, но и по причине того, что алгоритм
|