![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. > 19.98.Приведите пример леса DFS и обратной топологической сортировки, которые получаются в результате выполнения стандартного поиска в глубину с неявным
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3 (см. программу 19.7). • 19.99. Пусть задан некоторый DAG, существует ли топологическая сортировка, ко > 19.100. Покажите в стиле рис. 19.26 процесс топологической сортировки графа DAG 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3 с помощью алгоритма, использующего очередь истоков (программа 19.8). > 19.101. Приведите пример топологической сортировки, которая получается, когда в примере, представленном на рис. 19.25, в качестве структуры данных используется стек, а не очередь. • 19.102. Пусть задан некоторый граф DAG, существует ли топологическая сортиров 19.103. Измените алгоритм топологической сортировки на базе очереди истоков с таким расчетом, чтобы можно было пользоваться обобщенной очередью. Воспользуйтесь модифицированным алгоритмом с очередью LIFO (Last In First Out - последним прибыл, первым обслужен), со стеком и рандомизированной очередью. > 19.104. Воспользуйтесь программой 19.8 для построения реализации класса, осуществляющего проверку наличия циклов в заданном графе DAG (см. упражнение 19.75). о 19.105. Преобразуйте алгоритм топологической сортировки с использованием очереди истоков в алгоритм, использующий очередь стоков для выполнения обратной топологической сортировки. 19.106. Напишите программу, которая обобщает все возможные топологические упо 19.107. Напишите программу, которая преобразует любой орграф с V вершинами и •• 19.108. Напишите программу, которая осуществляет построение любого DAG с V вершинами и Е ребрами с равной вероятностью (см. упражнение 17.70). 19.109. Сформулируйте необходимые и достаточные условия для того, чтобы для конкретного графа DAG существовало только одно возможное топологически отсортированное упорядочение его вершин.
|