Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 8

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

В приведенном примере к вершинам графа будут добавляться ребра в порядке (1, 3), (4, 6), (2, 5), (3, 6), (2, 3). В результате получается то же минимальное остовное дерево, что и в алгоритме Прима.

Трудоемкость алгоритма пропорциональна M*ln M при условии применения рационального алгоритма сортировки ребер по их стоимости. Если M существенно меньше N², то есть граф разреженный, то выгоднее применение алгоритма Крускала, а не Прима.

4.7. Поиск циклов на ориентированном графе

Многие практические задачи сводятся к поиску циклов, то есть путей, начинающихся и заканчивающихся в одной и той же вершине. Отметим два момента. Во-первых, очевидно есть смысл искать элементарные циклы, то есть пути, не содержащие циклов внутри себя. Во-вторых, каждый цикл из K вершин порождает еще K-1 цикл путем выбора другой начальной вершины. Например, если путь из вершин a – b - c образует цикл, то циклами будут и пути b – c - a, c – a – b. Простейший способ избежать такого повторения – нумеровать вершины графа и считать, что цикл начинает вершина с минимальным номером.

Циклы можно находить различными способами. Выберем, например, начальную вершину S и методом поиска в глубину будем искать пути S–T–R-…-S с дополнительными условиями, чтобы номера вершин T, R, … были большими, чем номер вершины S, а отличные от S вершины в пути не повторялись. Если из некоторой промежуточной вершины B не находится путь в вершину S, имеет смысл временно запретить эту вершину, чтобы не повторять бесполезных попыток. Перебирая начальные вершины, можно найти все циклы.

5. Поиск данных

5.1. Последовательный, индексно-последовательный, бинарный поиск

Типичной задачей многих приложений является поиск нужной информации в большом объеме данных. Для дальнейшего изложения введем ряд определений.

Таблицей будем называть совокупность однотипных элементов или записей. Запись делится на именуемые поля. Будем считать, что есть возможность прямого доступа к каждой записи таблицы.

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

Чаще всего встречаются следующие задачи поиска:

• найти любую запись с заданным значением ключа;

• найти первую запись с заданным значением ключа;

• найти все записи с заданным значением ключа;

• найти любую запись с заданным значением ключа;

• если поиск неудачен, вставить новую запись с заданным значением ключа;

• найти и удалить запись с заданным значением ключа.

Простейшим видом поиска является последовательный поиск. В зависимости от задачи поиск ведется от первой записи и до нахождения нужной или до конца.

Поиск несколько облегчается, если записи отсортированы по возрастанию или убыванию значений ключа, по которому производится поиск. Например, при сортировке по возрастанию можно прекращать поиск, как только значение ключа очередной записи окажется больше заданного значения. В среднем сортировка вдвое уменьшает трудоемкость последовательного поиска.

При всей своей простоте последовательный поиск крайне неэффективен. Он находит свое применение в тех случаях, когда объем данных невелик либо обработке подлежит большое число записей. Последовательный поиск может быть составной частью более сложных методов поиска.

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

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

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

Индекс может быть многоуровневым. Например, для поиска в индексе создается еще один главный индекс, с которого и начинается поиск.

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

Бинарный поиск основан на идее известного численного метода половинного деления или дихотомии. Записи в таблице располагаются по возрастанию (убыванию) значений ключа поиска. Первоначально нижняя граница поиска соответствует первой, а верхняя - последней записи таблицы. Анализируется средняя запись таблицы. В зависимости от величины ключа можно сделать вывод о том, в какой половине таблицы нужно продолжать поиск. Тем самым пространство поиска сокращается вдвое, и процесс продолжается. Легко видеть, что максимальная трудоемкость поиска пропорциональна величине log₂N, где N - размер таблицы.

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

Ниже приведен пример создания и использования индекса для отсортированного файла. Поиск в индексе – бинарный, а в файле - последовательный. Индексируется каждая пятая запись исходного файла.

Program Index;

{ Создание индекса для отсортированного файла и поиск }

Uses Crt;

Type

zap=record

Name: string

{ далее могут быть другие поля }

end;

ind=record

Name: string;

Nom: integer

end;

Var

I, M, N, Low, High, Mid: integer;

Key, Namer: string;

B: boolean;

Zapr: zap;

Indr: ind;

Fzap: file of zap;

Find: file of ind;

Ish: text;

Procedure Vvod;

Begin

Reset(Ish);

Rewrite(Fzap);

While not Eof(Ish) do

begin

ReadLn(Ish,Namer);

Zapr.Name:=Namer;

Write(Fzap,Zapr)

end;

Close(Ish);

Close(Fzap);

End;

Procedure SozdInd(var N: integer);

Begin

I:=5; M:=0; { номер записи в Fzap }

N:=0; { номер записи в Find}

Rewrite(Find);

Reset(Fzap);

While not Eof(Fzap) do

begin

I:=I-1;

Read(Fzap,Zapr);

if I=0 then

begin

Indr.Name:=Zapr.Name;

Indr.Nom:=M;

N:=N+1;

{ счетчик числа записей в индексном файле }

Write(Find, Indr);

I:=5

end;

M:=M+1

end;

Close(Find);

Close(Fzap)

End;

Procedure Poisk(Key: string; var M: integer);

{ Key-ключевое имя для поиска, N-число записей в индексном файле }

{ M-номер найденной записи в исходном файле, M = -1 – запись не найдена }

Begin

Reset(Fzap);

Reset(Find);

Low:=0;

High:=N-1;

While Low<=High do { бинарный поиск индекса }

begin

Mid:=(Low+High) div 2;

Seek(Find, Mid);

Read(Find, Indr);

if Key=Indr.Name then

begin

Low:=Mid+1;

High:=Mid

end

else if Key<Indr.Name then High:=Mid-1

else Low:=Mid+1

end;

M:=High;

{ здесь Low>High}

{ M - максимальный номер записи в индексе, для которой Name<=Key }

{ если такой записи нет, то M = -1 }

if M >= 0 then

begin

Seek(Find, M);

Read(Find, Indr);

M:=Indr.Nom;

end

else M:=0;

Seek(Fzap, M);

Read(Fzap, Zapr);

While not Eof(Fzap) and (Zapr.Name<Key) do

begin

Read(Fzap, Zapr);

M:=M+1

end;

if Zapr.Name<>Key then M:=-1; { имя не найдено }

Close(Fzap);

Close(Find)

End;

Begin { начало основной программы }

ClrScr;

WriteLn;

Write('Введите имя исходного файла ');

Readln(Namer);

Assign(Ish,Namer);

Assign(Fzap,'a');

Assign(Find,'b');

Vvod;

SozdInd(N);

B:=True;

While B do

begin

Write('Введите фамилию (признак конца - к) ');

ReadLn(Namer);

if Namer<>'к' then

begin

Poisk(Namer, M);

Writeln('M=', M)

end

else B:=False

end;

Erase(Find);

Erase(Fzap)

End.

Бинарный поиск требует определенной аккуратности при работе с граничными значениями. Незначительные ошибки ведут к возможному зацикливанию либо неработоспособности программы.

4.2. Бинарные деревья поиска

Бинарным деревом поиска называется бинарное дерево из элементов, в котором ключ элемента в каждой вершине больше ключей всех элементов левого поддерева и меньше ключей элементов правого поддерева. Ниже приведен пример бинарного дерева поиска с числовыми значениями ключей.(.....)

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

Дерево поиска удобно для нахождения элемента с заданным ключом. Этот ключ сначала сравнивается с ключом корня. Если ключ корня больше, то переходим к левому сыну корня, иначе – к правому. Процесс продолжается в направлении от корня к листьям до нахождения элемента или получения отрицательного результата.

Деревья поиска применяют, например, в трансляторах для хранения и быстрого поиска ключевых слов или идентификаторов программы.

Наряду с поиском деревья поиска обеспечивают сортировку элементов. Действительно, обход дерева в порядке слева направо дает перечисление элементов по возрастанию ключей.

Включение нового элемента в дерево поиска выполняется следующим образом. Сначала производится поиск элемента с ключом, равным ключу нового элемента. После прихода в лист элемент войдет в новую вершину дерева, которая будет левым или правым сыном найденного листа в зависимости от значения ключа элемента.

Удаление элемента из дерева поиска предполагает такую перестройку дерева, чтобы оно не содержало указанного элемента, но оставалось деревом поиска. Возможны следующие три случая при удалении элемента из дерева поиска.

1. Удаляемый элемент находится в листе дерева. В этом случае удаляется соответствующая ссылка из отцовской вершины.

2. Удаляемый элемент находится в вершине с одним сыном. На место вершины с данным элементом помещается ее единственный сын со всеми своими потомками, то есть подтягивается все поддерево по имеющейся ветви.

3. Удаляемый элемент находится в вершине с обоими сыновьями. Сначала на место удаляемого элемента помещается один из двух элементов с соседними значениями ключа. Это может быть элемент с меньшим значением ключа из самой правой вершины левого поддерева либо с большим значением ключа из самой левой вершины правого поддерева. Для нахождения вершины с этим элементом достаточно спуститься из вершины с удаляемым элементом по левой ветви и далее идти по правым ветвям, пока это возможно, либо аналогичным образом найти этот элемент в правом поддереве. Найденная вершина имеет не более одного сына, поэтому дальнейшие действия сводятся к одному из первых двух случаев.

Например, удаление элемента с ключом 20 из дерева поиска, приведенного выше, даст следующий результат (.....)

Рассмотрим следующую задачу. С клавиатуры вводится последовательность слов. Требуется последовательно включать эти слова в дерево поиска, учитывая число вхождений каждого слова. Далее обеспечить удаление некоторых слов. При удалении уменьшать счетчик числа повторений слова и полностью удалять слово при обнулении этого счетчика. После каждой операции выдавать дерево поиска на экран, перечисляя вершины по алфавиту слов с указанием уровня вершин и счетчика повторений.

Program PoiskVkl;

{ поиск с включением на бинарном дереве }

Uses Crt;

Type

ref= ^word;

word=record

Key: string;

Count: integer;

Left, Right: ref

end;

Var

Root: ref;

Rab: string;

B: boolean;

Procedure Search(X: string; var P: ref);

Begin

if P=Nil then { слова нет - включить ! }

begin

New(P);

with P^ do

begin

Key:=X;

Count:=1; Left:=Nil; Right:=Nil

end

end

else

if X<P^.Key then Search(X, P^.Left)

else

if X>P^.Key then Search(X, P^.Right)

else { нашли слово }

P^.Count:=P^.Count+1

End;