Структура - смежность
Cтраница 1
Структура смежности, отраженная в матрице смежности, может быть также представлена в виде линейного графа. Построим граф с вершинами по числу входных букв и соединим две различные вершины линией или ребром графа, если соответствующие им входные буквы являются смежными. [1]
Структуры смежности могут быть удобно реализованы массивом из V линейно связанных списков, где каждый список содержит последователей некоторой вершины. Поле данных содержит метку одного из последователей, и поле указателей указывает следующего последователя ( разд. Хранение списков смежности в виде связанного списка желательно для алгоритмов, в которых в графе добавляются или удаляются вершины. [2]
Структуры смежности могут быть удобно реализованы массивом из п ( число вершин в графе) линейно связанных списков. Каждый список содержит вершины, смежные с вершиной, для которой составляется список. Хранение же списков смежности на сцепленной памяти желательно в алгоритмах, в основе которых лежат операции добавления и удаления вершин из списков. Следует отметить, что во многих задачах на графах выбор представления является решающим для эффективности алгоритмов. [3]
Представление графа с помощью структуры смежности позволяет ускорить обследование графа. В просмотре глубины 1 граф предварительно исследуется таким образом, что всегда выбирается ребро, выходящее из вершины, у которой имеются еще не пройденные инцидентные ребра и которую мы достигли позже всех других вершин с таким свойством. [4]
Ориентированный или неориентированный граф может быть однозначно представлен структурой смежности своих вершин. Списки Adj [ x ] составляются для каждой вершины графа. [5]
Во втором просмотре дуги обследуются в порядке, который определяется структурой смежности Л, начиная с вершины, которая была начальной и в - первом просмотре. Вершины нумеруются числами от V до 1, каждая из них получает номер при последнем прохождении во время просмотра. Из процедуры приписывания номеров следует, что если v - w9 то N ( v) C N ( w), и если У-ШЬ v - ш2, то N ( WI) N ( w2) при условии, что дуга ( v w) проходится раньше дуги ( v, w2) во время второго просмотра. Теперь уже будем отождествлять вершины с номерами, приписанными вершинам во время второго просмотра. [6]
Если G - неориентированный граф, то каждое ребро представлено в структуре смежности дважды; если G - ориентированный граф, то каждая его дуга встречается один раз. Для данного графа структура смежности определяется не единственным - образом, и структур столько, сколько существует упорядочений ребер, инцидентных каждой вершине. [7]
Мы начинаем работу в предположении, что Gx и GY заданы в виде структур смежности Xadj и Yadj. [8]
 |
Поиск в глубину на графе. [9] |
На рис. 8.5 показано, как поиск в глубину исследует неориентированный граф G, представленный структурой смежности. Проходим ( с, а) и обнаруживаем, что вершина а уже посещалась ранее. Поэтому возвращаемся в с и каким-либо образом помечаем ребро ( с, а) ( на рис. 8.5 - пунктирной линией), чтобы отличить его от ребер типа ( Ь, с), которые ведут в новые вершины. [10]
Отметим, что при компьютерной реализации обходов по глубине и ширине целесообразно использовать задание дерева структурой смежности вершин. [11]
После завершения второго просмотра получаем n - дерево Р графа G, упорядоченное в соответствии со структурой смежности А. [12]
Рассмотрим приведенный на рис. 8.21 пример, где показаны два орграфа Gx и GY, а также их структуры смежности. [13]
Очевидно, дерево ( или лес), порожденное поиском в глубину, неединственно и классификация ребер зависит от произвольного порядка, в котором вершины и ребра исходного орграфа задаются в структуре смежности, а также от выбора начальной вершины. Тем не менее разбиение ребер, которое следует из поиска в глубину на орграфе, можно использовать для определения его сильно связных компонент. Заметим, что направленные вперед ребра можно игнорировать, так как они не влияют на сильную связность. [14]
Метод поиска в глубину на простом неориентированном графе представлен в алгоритме 6.1. Рекурсивная процедура Depth ( x, w) осуществляет поиск в глубину на графе Г ( X, U, Ф), содержащем х е X, и строит для графа дерево Т поиска, которое является ориентированным остовным деревом Го ( X, Т, Ф) ( если исходный граф не связен, то Г0 будет лесом); w e является отцом х е Хв строящемся дереве, где х - исследуемая вершина. Граф задан структурой смежности Adj [ x ], где Adj [ x ] означает множество вершин, смежных с х е X. Элементы Т - это ребра строящегося дерева поиска, а элементы В - это обратные ребра, которые не могут принадлежать Г0, так как они ведут назад в пройденные ранее вершины. Заметим, что обратное ребро должно идти от потомка к предку по дереву поиска. Чтобы отличить уже пройденные вершины от непройденных, вводится вектор Mark [ x ] меток вершин, которые постепенно нумеруются от 1 до Х по мере того, как попадаем в них. Сначала полагается Mark [ x ] О для всех х е X в знак того, что ни одна вершина не пройдена, и когда попадаем в вершину х первый раз, Mark [ x ] получает ненулевое значение. [15]
Страницы: 1 2