Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1,85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
|
В
ЫВОДЫ Графы – это одна из самых важных структур данных, используемых в информатике для моделирования различных систем. Основным отношением между элементами графа – его узлами – является отношение смежности, оп- ределяющее свойство связности графа. Два узла графа являются смежными, если имеется соединяющее их ребро. Ребро, имеющее направленность, назы- вается дугой, а граф, все ребра которого являются дугами, называется оргра- фом. 19 / 23 204 Деревья являются частным случаем графа. Так, остовное дерево полу- чается из графа удалением максимального числа ребер с сохранением свой- ства связности. Также, как и в случае деревьев, существуют различные алго- ритмы обхода узлов графа. Наиболее известными из них являются алгоритмы обхода графа в глубину и в ширину. Специальными видами обхода графа являются циклы Эйлера и Гамильтона. Ребра графа могут быть снабжены дополнительными характеристика- ми – весами. Для взвешенного графа можно поставить целый ряд интересных задач, в частности задачи поиска минимального пути между двумя вершина- ми, поиска кратчайшего замкнутого пути, построения остовного дерева наи- меньшей стоимости. Для более изучения алгоритмов работы с графами мож- но рекомендовать монографии [26, 35, 45]. У ПРАЖНЕНИЯ 1. Пусть G = (V, Е) — связный неориентированный граф. Разработайте ал- горитм для вычисления за время О(V + Е) пути в G, который проходит по каждому ребру из Е по одному разу в каждом направлении. 2. Ориентированный граф G = (V, E) обладает свойством односвязности (singly connected), если имеется не более одного пути для каждой пары вершин этого графа. Разработайте эффективный алгоритм для определе- ния, является ли ориентированный граф односвязным. 3. Используя класс Timing (глава 1), сравните скорость поиска в графе с использованием алгоритмов обхода в ширину и в глубину. 4. Модифицируйте алгоритм построения эйлерова цикла так, чтобы не требовалась предварительная проверка четности степеней. Существова- ние вершины нечетной степени должно обнаруживаться по ходу работы алгоритма. 5. Докажите, что при любом N ≥ 2, где N – число вершин, в графе сущест- вует гамильтонов цикл. 20 / 23 |
