Машинное представление графов
Самый приятный и полезный для человека способ представить граф – изобразить его на плоскости в виде точек и соединяющих их линий. Очевидно, что для ЭВМ он совершенно бесполезен… Поскольку выбор для этой цели определенной структуры данных очень сильно влияет на эффективность алгоритма, рассмотрим несколько способов машинного представления графов. Матрицы смежности– самый худший с алгоритмической точки зрения способ. Это матрицы nm в строках перечисляются вершины, в столбцах – ребра (см. таблицу и рис. 8.3).
Матрица смежности
Этот способ требует nm ячеек памяти, причем большинство из ячеек заняты нулями. Ответ на элементарный вопрос: «к каким вершинам ведут ребра из x?», требует перебора всех столбцов, т.е. m шагов. Матрица инциденцийимеет размер n´n. Если существует ребро (x–y), то в клетках с координатами (x, y) и (y, x) ставится 1.
Матрица инциденций графа G (рис. 8.3):
Независимо от числа ребер требуется объем памяти n´n, но за один шаг можно ответить на вопрос: «существует ли ребро из x в y?». Также граф можно представить в виде списка пар, соответствующих ребрам:
Список ребер графа G (рис. 8.3) Объем памяти равен 2m, но попробуйте ответить на вопрос: «к каким вершинам ведут ребра из вершины x?». Наиболее удобным машинным представлением графа являются списки инцидентности. Каждой вершине v V ставим в соответствие список вершин, соединенных ребрами с вершиной v. Для неориентированного графа каждое ребро (v–u) будет представлено дважды: в списке для v и в списке для u. Начало каждого списка будет храниться в одномерном массиве НАЧАЛО длины n. По вершине v находим НАЧАЛО[v] – в этой ячейке хранится указатель на начало списка вершин, соединенных с v. Каждый элемент такого списка – запись, состоящая из двух полей:
Если вершина 1 соединена с 2 и 3, то ее список выглядит как на рис. 8.4. Весь список для вершины v будем называть ЗАПИСЬ[v]. Цикл, перебирающий все элементы этого списка, будем записывать «for u ЗАПИСЬ[v]». Число ячеек памяти, необходимое для представления графа списками инцидентности, имеет порядок O(n+m). Создадим ЗАПИСЬ[1] для списков инцидентности (рис. 8.5) графа G (рис. 8.3).
Рис. 8.5. Список инцидентности к графу с рис. 8.3 Указатели на начало каждой цепи объединены в массив НАЧАЛО и инициализируются перед созданием цепи (рис. 8.6). Рис. 8.6. Первый шаг создания списков Записи для ребер, выходящих из узла (1), создаются динамически. Рассмотрим подробно этот механизм (рис. 8.7).
Очевидно, что запись, подключенная первой, оказывается в конце цепи, а последняя – в начале. Таким образом, дисциплина обслуживания соответствует стеку. Вообще, набор стандартных подпрограмм для работы с динамическими списками включает в себя процедуру вталкивания в стек push, функцию выталкивания из стека pop и функцию выталкивания из очереди poptail. Опишем их во фрагменте 1. ФРАГМЕНТ 1
Ясно, что формирование всех цепей списков инцидентности нужно делать в цикле. Сделаем это во фрагменте 2. ФРАГМЕНТ 2
Популярное: Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (779)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |