Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[149]

Find-Depth (v) Возвращает глубину (расстояние до корня) вершины v.

Graft(t, v) («прививка»). Вершина г должна быть корнем одного из деревьев, вершина v должна принадлежать к какому-то другому дереву; дерево с корнем г «прививается» к дереву, содержащему v, при этом v становится родителем г.

(а)Пусть мы реализовали эту структуру данных следующим образом. Деревья представляются как в лесе непересекающихся множеств (p[v] - родитель вершины v, если v - не корень, и p[v] = v, если v - корень), процедура Graft(t, v) состоит в присваивании p[r] <- v, процедура Make-Tree написана очевидным образом, и, наконец, для нахождения глубины (Find-Depth)) мы идем из v в корень и подсчитываем длину пути. Покажите, что при этом стоимость т операций Make-Tree, Graft и Find-Depth в худшем случае есть 0(то2).

Алгоритм можно ускорить, если воспользоваться объединением по рангам и сжатием путей. Заметим, что структура дерева, нужного для сжатия путей, не обязана соответствовать структуре исходного дерева - важно лишь, чтобы можно было восстанавливать информацию о глубине (ребро нового дерева должно хранить информацию о разнице глубин концов ребра в старом дереве).

(б)Реализуйте операцию Make-Tree.

(в)Реализуйте операцию Find-Depth. Ваш алгоритм должен использовать сжатие путей, а его время работы должно быть пропорционально длине пути поиска.

(г)Реализуйте операцию Graft (действуйте по аналогии с алгоритмами Union и Link; корень в строимом дереве не обязан быть корнем в старом смысле).

(д)Дайте точную оценку на стоимость последовательности т операций Make-Tree, Graft и Find-Depth, п из которых - операции Make-Tree (для худшего случая).

22-3 Алгоритм Тарьяна для нахождения наименьшего общего предка в режиме off-line.

Наименьший общий предок (least common ancestor, сокращённо LCA) вершин и и v корневого дерева Г есть, по определению, вершина наибольшей глубины среди вершин, являющихся предками как и, так и v. Задача о нахождении наименьших общих предка в режиме off-line (off-line least-common-ancestors problem) состоит в следующем. Дано корневое дерево Г и некоторое множество Р неупорядоченных пар его вершин. Требуется для каждой пары вершин (и, v) £ Р найти их наименьшего общего предка.

Ниже приведён алгоритм LCA, решающий эту задачу (наименьшие общие предки всех пар (и, v) £ Р будут напечатаны в результате вызова LCA(root[T]); вначале все вершины дерева - белые).


LCA(u)

1Make-Set(и)

2ancestor[Find-Set(и)] \gets и

3for (для) каждого $v$, являющегося реб\"~~а5нком $и$

4do LCA(v)

5Union(u,v)

6ancestor[Find-Set(и)] \gets и

7покрасить и в ч\"~~а5рный цвет

8for (для) каждой вершины v такой, что $(u,v)\in Р$

9do if вершина v ч\"~~а5рная

10then print (Наименьший общий предок $и$ и $v$

есть ancestor[Find-Set(v)]

(а)Покажите, что строка 10 исполняется в точности один раз для каждой пары (и, v) £ Р.

(б)Покажите, что в результате вызова LCA(root[T]) каждый из последующих вызовов ЬСА(и) происходит в тот момент, когда количество непересекающихся множеств равно глубине вершины и в дереве Т.

(в)Покажите, что в результате вызова LCА(корень[Т]) будут напечатаны наименьшие общие предки для всех пар (и, v) £ Р.

(г)Оцените время работы алгоритма LCA в предположении, что система непересекающихся множеств реализована с помощью леса с объединением по рангам и сжатием путей.

Замечания

Многие важные результаты о системах непересекающихся множеств в той или иной мере принадлежат Тарьяну. В частности, именно он установил оценку 0(ma(m, п)) [186, 188]. Более слабая оценка 0(m\g* п) была ранее получена Хопкрофтом и Ульманом [4, 103]. В работе [190] Тарьян и ван Леувен обсуждают различные варианты сжатия путей, в том числе алгоритмы, работающие «за один проход» (иногда они работают быстрее «двухпроходных»). Габов и Тарьян [76] показали, что в некоторых приложениях операции с непересекающимися множествами можно выполнить за время О (га).

В работе [187] Тарьян показал, что при некоторых дополнительных условиях стоимость операций с непересекающимися множествами не может быть ниже, чем 0(ma(m, га)), какую реализацию мы бы ни избрали. Фредман и Сакс [74] показали, что, кроме того, в худшем случае эти операции требуют обращения к Q(ma(m, п)) словам длиною в lg га битов.


Алгоритмы на графах

Введение

Графы встречаются в сотнях разных задач, и алгоритмы обработки графов очень важны. В этой части книги мы рассмотрим несколько основных алгоритмов обработки графов.

В главе 23 рассматриваются способы представления графа в программе, а также различные варианты обхода графа (поиск в ширину и в глубину). Приводятся два применения поиска в глубину: топологическая сортировка ориентированного графа без циклов и разложение ориентированного графа в сумму сильно связных компонент.

В главе 24 рассматривается задача о покрывающем дереве (наборе рёбер, связывающем все вершины графа) минимального веса. (Мы предполагаем, что каждое ребро графа имеет некоторый положительный вес.) Для этой задачи применимы жадные алгоритмы (см. главу 18).

В главах 25 и 26 рассматривается задача о кратчайших путях. Вновь каждому ребру приписано некоторое число, но теперь оно называется длиной ребра. Требуется найти кратчайшие пути из одной вершины во все остальные (глава 25) или кратчайшие пути из каждой вершины в каждую (глава 26).

Наконец, в главе 27 расматривается задаче о максимальном потоке вещества через сеть труб ограниченной пропускной способности. Каждое ребро рассматривается как труба некоторой пропускной способости. В некоторой вершине находится источник вещества, а в другой - потребитель. Спрашивается, какой поток вещества можно передавать от источника к потребителю, не превышая пропускной способности труб. Эта задача важна, поскольку к ней сводится многие интересные задачи.

Мы будем оценивать время обработки заданного графа G = (V, Е) в зависимости от числа его вершин (С) и рёбер ((-Е1)); мы будем для краткости писать V и Е вместо \ V\ и \Е\. В программах множество вершин граф G мы будем обозначать С[С], а множество рёбер - E[G].



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]