1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 13
Текст из файла (страница 13)
Интересной альтернативой является представление строк и(или) столбцов матрицы смежностей в виде двоичных векторов. Такое ГЛ. К РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ представление может способствовать значительной эффективности алгоритмов на графах. Еще одно возможное представление графа — с помощью списков. Списком смежностей для узла и называется список всех узлов гв, смежных с и. Граф можно представить с помощью [[У[[ списков смежностей, по одному для каждого узла. Пример 2.2, На рис. 2.6,а изображен ориентированный граф, содержащий четыре узла, а на рис. 2.6,б — его матрица смежностей.
На рис. 2,6,в показаны четыре списка смежностей, по одному для каждого узла. Например, из узла 1 в узлы 2 и 4 идут ребра, так что список смежностей для 1 содержит компоненты 2 и 4, связанные в смысле рис. 2.1. Табличное представление списков смежностей приведено на рис. 2.6,г. Каждая из первых четырех ячеек в массиве СЛЕДУЮЩИЙ содержит указатель на первый узел списка смежностей, а именно СЛЕДУЮЩИЙ[!) указывает на первый узел списка смежностей для узла !.
Заметим, что СЛЕДУЮЩИЙ[3[=0, поскольку в списке смежностей для узла 3 нет узлов. Остальные составляющие массива СЛЕДУЮЩИЙ представляют ребра графа. Массив КОНЕЦ содержит узлы из списков смежностей. Таким образом, список смежностей узла 1 начинается в ячейке 5, ибо СЛЕДУЮЩИЙ[1)=5, КОНЕЦ[5)=2; это показывает, что есть ребро (1, 2). Равенства СЛЕДУЮЩИЙ[51=6 и КОНЕЦ[6[=4 означают, что есть ребро (1, 4), а СЛЕДУЮЩИЙ[6)=0 — что больше нет ребер, начинающихся в 1.
П Заметим, что представление графа в виде списков смежностей требует памяти порядка [[У[[+[[Е[[. Представлением с помощью списков смежностей часто пользуются, когда [[Е[[(<[[У[['.. Если граф неориентирован, то каждое ребро (и, в) представляется дважды: один раз в списке смежностей для и и одйн раз в списке смежностей для в, В этом случае можно добавить новый массив, называемый СВЯЗЬ, чтобы коррелировать оба экземпляра неориентированного ребра.
Таким образом, если 1 — ячейка, соответствующая узлу в в списке смежностей для о, то СВЯЗЬИ вЂ” ячейка, соответствующая узлу и в списке смежностей для в. Если мы хотим с удобством удалять ребра из неориентированного графа, то списки смежностей можно связать дважды (как описано в равд. 2,1).
Это обычно бывает нужно потому, что даже если удалять всегда ребро (и, в), стоящее первым в списке смежностей узла и, все равно может оказаться, что ребро, идущее в обратном направлении, стоит в середине списка смежностей узла и. Чтобы быстро удалить ребро (и, в) из списка смежностей для ю, надо уметь быстро находить ячейку, содержащую предыдущее ребро в этом списке смежностей.
ЕС ДЕРЕВЬЯ 2.4. ДЕРЕВЬЯ Теперь введем очень важный вид ориентированных графов— деревья — н рассмотрим структуры данных, пригодные для их представления. Определение. Ориентированный граф без циклов называется ориентированным ациклическим графом. (Ориентированное) дерево (иногда его называют корневым деревом) — это ориентированный ациклический граф, удовлетворяющий следующим условиям: 1) имеется в точности один узел, называемый корнем, в который не входит ни одно ребро, 2) в каждый узел, кроме корня, входит ровно одно ребро, 3) из корня к каждому узлу идет путь (который, как легко пока- зать, единствен).
Ориентированный граф, состоящий из нескольких деревьев, называется лесом. Леса и деревья — столь часто встречающиеся частные случаи ориентированных ациклических графов, что для описания их свойств отбит ввести специальную терминологию. Определение. Пусть Е=((7, Е) — граф, являющийся лесом. Если (и, св) принадлежит Е, то о называется отцом узла и4, а и — сыном узла о. Если есть путь из о в св, то о называется предком узла в, а щ— потомком узла о. Более того, если о~се, то и называется подлинным ~редком узла и, а 4в — подлинным потомком узла о.
Узел без подлинных потомков называется листом. Узел о и его потомки вместе образуют поддерево леса г, и узел о называется корнем этого поддерева. левмйсыя врлвыйсмя а 4Г Рис. 4.7. 44воичнос дерево н его представление. ГЛ. К РАЗРАВОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ Глубина узла и в дереве — это длина пути из корня в о. Высота узла о в дереве — это длина самого длинного пути из о в какой-нибудь лист. Высотой дерева называется высота его корня.
Уровень зла о в дереве равен разности высоты дерева и глубины узла о. апример, на рис. 2.7,а узел 3 имеет глубину 2, высоту О и уровень 1. Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядочено. При изображении упорядоченного дерева мы будем считать, что множество сыновей каждого узла упорядочено слева направо. Двоичным (бинарным) деревом называется такое упорядоченное дерево, что 1) каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын, 2) каждый узел имеет не более одного левого сына и не более одного правого сына.
Поддерево Т„ корнем которого является левый сын узла о (если такое существует), называется левым поддеревом узла о. Аналогично поддерево Т„, корнем которого является правый сын узла о (если такое существует), называется правым поддеревом узла о.
Все узлы в Т, расположены левее всех узлов в Т„. Двоичное дерево обычно представляют в виде двух массивов ЛЕВЫЙСЫН и ПРАВЫЙСЫН. Пусть узлы двоичного дерева занумерованы целыми числами от 1 до п. В этом случае ЛЕВЫЙСЫН[1[=1 тогда и только тогда, когда узел с номером 1 является левым сыном узла с номером!. Если у узла 1 нет левого сына, то ЛЕВЫЙСЫН[1[=О. ПРАВЫЙСЫН[1] определяется аналогично. Пример 2.3. Двоичное дерево и его представление изображены на рис.
2.7. С) Определение. Двоичное дерево называется полным, если для некоторого целого числа й каждый узел глубины меньшей й имеет как левого, так н правого сына и каждый узел глубины й является листом. Полное двоичное дерево высоты й имеет ровно 2"+' — 1 узлов. Полное двоичное дерево высоты й часто представляют одним массивом. В позиции 1 этого массива находится корень. Левый сын узла в позиции! расположен в позиции 21, а его правый сын — в позиции 21+1. Отец узла, находящегося в позиции 2 1, расположен в позиции ~В2~. Многие алгоритмы, использующие деревья, часто прохсдлп2 дерево (посещают каждый его узел) в некотором порядке.
Известно несколько систематических способов сделать это. Мы рассмотрим три широко распространенных способа: прохождение дерева в прямом порядке, обратном и внутреннем. т.д деРеВья Ф д в Рне. 2.8, Прохомденне дерева: а — в поеном порядке; б — обратном; е — внут. раннем, Определение. Пусть Т вЂ” дерево с корнем г и сыновьями ип... ..., Вю й)0. При А=О зто дерево состоит нз единственного узла г. Прохождение дерева Т в прямом порядке определяется следующей рекурсией: 1) посетить корень г, 2) посетить в прямом порядке поддеревья о корнями от, ..., оа в указанной последовательности. Прохождение дерева Т в оброгпном порядка определяется следующей рекурсией: 1) посетить в обратном порядке поддеревья с корнями от, ...
..., Ва в указанной последовательности, 2) посетить корень г, Прохождение двоичного дерева ао внутреннем порядка определяется следующей рекурсией: 1) посетить во внутреннем порядке левое поддерево корня (если оно существует), 2) посетить корень, 3) посетить во внутреннем порядке правое поддерево корня (если оно существует). Пример 2.4. На рис. 2.8 изображено двоичное дерево, узлы которого пронумерованы в соответствии с прохождением его в прямом порядке (риа, 2.8,а), обратном (рив. 2.8,б) и внутреннем (рис. 2.8,в).
П Если при некотором прохождении дерева его узлам были присвоены какие-то номера, то на узлы удобно сеылаться по этим номерам. Так, и будет обозначать узел, которому был присвоен номер о. ГЛ. А РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ Если все узлы занумерованы в порядке посещения, то рассмотренные нумерации Обладают рядом интересных свойств. При нумерации в прямом порядке все узлы поддерева с корнем г имеют номера, не меньшие Г.
Точнее, если О, — множество потомков узла Г, то о будет номером некоторого узла из АА„ тогда и только тогда, когда Г~п(Г+й0„й. Поставив в соответствие каждому узлу и его номер в прямом порядке и количество его потомков, легко определить, является ли некоторый узел ш потомком для п. После того как номера присвоены (в соответствии с прямым порядком) и вычислено количество потомков каждого узла, на вопрос, является ли ш потомком для о, можно ответить за фиксированное время, не зависящее от размера дерева, Номера, соответствующие обратному порядку, обладают аналогичным свойством.
Номера узлов двоичного дерева, соответствующие внутреннему порядку, обладают тем свойством, что номера узлов в левом поддереве для и меньше и, а в правом поддереве больше ш Таким образом, чтобы найти узел с номером ш, надо сравнить ш с корнем Г. Если и= Г, то искомый узел найден. Если ш Г, то надо повторить этот процесс для левого полдерева; если Гл)Г, то повторить процесо для правого поддерева. В конце концов узел с номером ш будет найден. Такие свойства прохождений нам понадобятся в следующих главах. Дадим теперь еще одно, последнее определение, касающееся деревьев.
Определение. Неориентированным деревом называется неориентированный ациклический связный (любые два узла соединены путем) граф. Корневое неориентированное дерево — это неориентированное дерево, в котором один узел выделен в качестве корня. Ориентированное дерево можно превратить в корневое неориентированное, просто сделав все его ребра неориентированными.
Мы будем употреблять одну и ту же терминологию и пользоваться одними и теми же обозначениями для корневых неориентированных и для ориентированных деревьев. Основное математическое различие здесь состоит в том, что все пути в ориентированном дереве идут от предков к потомкам, тогда как в корневом неориентированном дереве пути могут идти в обоих направлениях. 2.$. РЕКУРСИЯ Процедуру, которая прямо или косвенно обращается к себе, называют рекурсивной. Применение рекурсии часто позволяет давать более прозрачные и сжатые описания алгоритмов, чем это было бы возможно без рекурсии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
