1] Определение глубины дерева [0
Работа добавлена на сайт samzan.net:
Содержание
|
[0.1] Определение глубины дерева [0.2] Обход дерева на заданную глубину [0.3] включение нового значения в дерево [0.4] Поиск первого подходящего в дереве на основе полного обхода [0.5] Поиск в дереве максимального (минимального) значения [0.6] Оптимизация поиска в дереве [0.7] Нумерация вершин [0.8] Поиск и включение в двоичное дерево [0.9] Нумерация вершин в двоичном дереве [0.10] Контрольные вопросы [0.11] Задания для практической работы
[1] [1.1] Преобразование двоичного дерева в лозу. [1.2] Преобразование лозы в сбалансированное двоичное дерево. [1.3] Контрольные вопросы [1.4] Задания для практической работы
[2] [2.1] Основные понятия [2.2] Алгоритмы представления графа [2.2.1] Представление графа в виде массива [2.2.2] Представление графа в виде матрицы смежности [2.2.3] Представление графа в виде связанного списка [2.2.4] Представление графа в виде списка дуг [2.2.5] Преобразования структур графа [2.3] Обходы в графах [2.4] Определение путей и контуров Эйлера [2.5] Поиск кратчайших путей [2.6] Определение остовных деревьев [2.7] Контрольные вопросы [2.8] Задания для практической работы
[3] [3.1] Контрольные вопросы [3.2] Задания для практической работы
[4] [4.1] Сортировка выбором [4.2] Сортировка вставками [4.3] Пузырьковая сортировка [4.4] Быстрая сортировка [4.5] сортировка слиянием [4.6] Пирамидальная сортировка [4.7] Контрольные вопросы [4.8] Задания для практической работы
[5] [5.1] Введение [5.2] Последовательный поиск [5.3] Двоичный поиск [5.4] Работа со словарем. Иоиск и вставка. Хеширование. [5.5] Поиск подстроки в строке [5.5.1] Алгоритм прямого поиска подстроки в строке [5.5.2] БМ-поиск (Боуера–Мура) [5.5.3] КМП-поиск (Кнута–Мориса и–Пратта) [5.6] Контрольные вопросы [5.7] Задания для практической работы |
Основные операции при работе с деревьями
К основным операциям работы с деревьями относятся:
а) поиск элемента в дереве. Операция заключается в прохождении узлов дерева в одном из рассмотренных выше порядке. При прохождении дерева поиска достаточно пройти только то поддерево, которое возможно содержит искомый элемент;
б) включение элемента в дерево. Операция заключается в добавлении листа (исключая сбалансированное дерево – включение элемента в сбалансированное дерево приводит, как правило, к его перестройке) в какое-то поддерево, если такого элемента нет в исходном дереве. При включении нового элемента в дерево поиска лист добавляется в то поддерево, в котором не нарушается отношение порядка;
в) удаление элемента из дерева. Операция заключается в изменении связей между дочерними и родительскими, по отношению к удаляемому, элементами (исключая сбалансированное дерево – удаление элемента из сбалансированного дерева приводит, как правило, к его перестройке); здесь необходимо рассматривать три случая: удаление листа (см. рис.1.а), удаление элемента с одним потомком (см. рис.1.б), удаление элемента с двумя потомками (см. рис.1.в).
Рис. 1. Случаи удаления листа дерева
При удалении элемента степени 2 из дерева поиска изменять связи необходимо так, чтобы не нарушалось установленное в дереве отношение порядка. Лучшим вариантом в этом случае будет перемещение на место удаляемого элемента либо самого правого листа из левого поддерева удаляемого элемента, либо самого левого листа из правого поддерева удаляемого элемента;
г) сравнение деревьев (проверка деревьев на равенство). Операция заключается в прохождении обоих деревьев в одном порядке до тех пор, пока либо не будут пройдены оба дерева, либо одно из них, либо соответствующие элементы окажутся не равными, либо в одном из деревьев не будет обнаружено отсутствие соответствующего элемента. Только в случае равенства деревьев оба дерева будут пройдены одновременно;
д) копирование дерева. Операция заключается в прохождении исходного дерева и построении нового дерева с элементами, информационные поля которых равны информационным полям соответствующих элементов исходного дерева.
Далее рассмотрим операции поиска и включения элемента в дерево. Остальные операции можно выполнить на основе работы алгоритмов поиска и включения элемента в дерево.
Определение глубины дерева
При определении минимальной (максимальной) длины ветви дерева каждая вершина должна получить значения минимальных длин ветвей от потомков, выбрать из них наименьшую и передать предку результат, увеличив его на 1 - " добавить себя" .
struct tree{
int val;
tree *p[4];
};
//---- Определение ветви минимальной длины
int MinLnt(tree *q){
if (q==NULL) return 0;
int min= MinLnt(q->p[0]);
for (int i=1; i< 4; i++){
int x=MinLnt(q->p[i]);
if (x < min) min=x;}
return min+1;}
Обход дерева на заданную глубину
Для отслеживания процесса " погружения" достаточно дополнительной переменной, которая уменьшает свое значение на 1 при очередном рекурсивном вызове.
//------Включение вершины в дерево на заданную глубину
int Insert(tree *ph, int v, int d) { // d - текущая глубина включения
if (d == 0) return 0; // Ниже не просматривать
for ( int i=0; i< 4; i++)
if (ph->p[i] == NULL){
tree *pn=new tree;
pn->val=v;
for (int j=0; j< 4; j++) pn ->p[j]=NULL;
ph->p[i]=pn;
return 1; }
else
if (Insert(ph->p[i], v , d-1)) return 1; // Вершина включена
return 0; }
включение нового значения в дерево
Для включения простейшим способом нового значения в дерево в ближайшее в корню место достаточно соединить две указанные функции вместе.
void main(){ tree PH={ 1,{NULL,NULL,NULL,NULL} };
for (int i=0; i< 100; i++) Insert( & PH, rand( 20 ), MinLnt( & PH));
}
Поиск первого подходящего в дереве на основе полного обхода
При обнаружении в дереве первого значения, удовлетворяющего условию, необходимо прервать не только текущий шаг рекурсии, но и все предыдущие. Поэтому цикл рекурсивного вызова прерывается сразу же, как только потомок возвратит найденное в поддереве значение. Текущая вершина должна " ретранслировать" полученное от потомка значение к собственному предку (" вверх по инстанции" ).
//---- Поиск в дереве строки, длиной больше заданной
struct stree{
char *str;
stree *p[4];};
char *big_str(stree *q){
if (q==NULL) return NULL;
if (strlen(q->str)> 5) return q->str; // Найдена в текущей вершине
for (int i=0; i< 4; i++){
char *child=big_str(q->p[i]); // Получение строки от потомка
if (child!=NULL) return child; // Вернуть ее " от себя лично"
}
return NULL;} // Нет ни у себя, ни у потомков
Поиск в дереве максимального (минимального) значения
Производится полный обход дерева, в каждой вершине стандартный контекст выбора минимального из текущего значения в вершине и значений, полученных от потомков при рекурсивном вызове функции.
//---- Поиск максимального в дереве
int GetMax(tree *q){
if (q==NULL) return -1;
int max=q->val;
for (int i=0; i< 4; i++){
int x=GetMax(q->p[i]);
if (x > max) max=x;}
return max;}
Оптимизация поиска в дереве
Основное свойство дерева соответствует пословице " дальше в лес - больше дров" . Точнее, количество просматриваемых вершин от уровня к уровню растет в геометрической прогрессии. Если известен некоторый критерий частоты использования различных элементов данных (например, более короткие строки используются чаще, чем длинные), то в соответствии с ним можно частично упорядочить данные по этому критерию с точки зрения их " близости" к корню : в нашем примере в любом поддереве самая короткая строка находится в его корневой вершине. Алгоритм поиска может ограничить глубину просмотра такого дерева.
//--- Дерево оптимизацией : короткие ключи ближе к началу
struct dtree{
char *key; // Ключевое слово
void *data; // Искомая информация
dtree *p[4]; }; // Потомки
void *find(dtree *q, char *keystr) // Поиск по ключу
{ void *s;
if (q==NULL) return NULL;
if (strcmp(q->key,keystr)==0) return q->data; // Ключ найден
if (strlen(keystr)<strlen(q->key))
return NULL; // Короткие строки - ближе к корню
for (int i=0; i< 4; i++)
if ((s=find(q->p[i],keystr))!=NULL) return s;
return NULL; }
Функция включения в такое дерево ради сохранения свойств должна в каждой проходимой ею вершине рекурсивно " вытеснять" более длинную строку в поддерево и заменять ее на текущую (новую), более короткую.
Нумерация вершин
Способы обхода дерева.В деревьях обход вершин возможен только с использованием рекурсии, поэтому и их логическая нумерация производится согласно последовательности их рекурсивного обхода. Рекурсивная функция в этом случае получает ссылку или указатель на счетчик вершин, который она увеличивает на 1 при обходе текущей вершины. В зависимости от того, кто нумеруется вперед предок или потомки, и в зависимости от направления просмотра потомков имеют место различные способы обхода и нумерации.
//---- Обход дерева с нумерацией вершин сверху вниз, слева направо (прямой обход)
void ScanNum (tree *q, int &n ) {
if (q==NULL) return;
printf("n=%d val=%d\n",n++,q->val);
for (int i=0; i< 4; i++) ScanNum(q->p[i],n);
}
Обход с нумерацией в обычном дереве используется для извлечения вершины по логическому номеру. При достижении вершины с заданным номером обход прекращается (аналогично алгоритму поиска первого подходящего).
//---- Извлечение по логическому номеру с полным обходом дерева
int GetNum (tree *q, int &n, int num ) {
if (q==NULL) return -1;
if ( n++ ==num) return q->val; // Номер текущей совпал с требуемым
for (int i=0; i< 4; i++) { // Обход потомков,
int vv=GetNum (q->p[i],n,num ); // пока не превышен номер
if (n > num) return vv;
}
return -1; }
Если каждая вершина дерева будет содержать дополнительный параметр количество вершин в связанном с ней поддереве, то извлечение по логическому номеру можно выполнить с помощью циклического алгоритма, либо линейной рекурсии, благодаря тому, что можно сразу же определить в каком поддереве находится интересующая нас вершина. Счетчики вершин можно корректировать в самом процессе добавления /удаления вершин.
//--- Извлечение по логическому номеру (счетчик вершин в поддереве)
struct ctree{
int nodes; // Счетчик вершин в поддереве
int val;
ctree *p[4]; };
int GetNum(ctree *q, int num, int n0){
if (q==NULL) return 1; // n0 начальный номер в текущем поддереве
if (n0++==num) return q->val; // начальный номер совпал с требуемым
for (int i=0; i< 4; i++){
if (q->p[i]==NULL) continue;
int nc= q->p[i]->nodes; // число вершин у потомка
if (n0+ nc > num) // выбран потомок
return GetNum(q->p[i],num,n0); // с диапазоном номеров
else // корректировать начальный номер
n0+=nc; // для следующего потомка
}}
В двоичном дереве каждая вершина имеет не более двух потомков, обозначенных как левый ( left) и правый ( right). Кроме того, на данные, хранимые в вершинах дерева, вводится следующее правило упорядочения: значения вершин левого поддерева всегда меньше, а значения вершин правого поддерева - больше значения в текущей вершине.
struct btree {
int val;
btree *left,*right; };
Поиск и включение в двоичное дерево
Свойства двоичного дерева позволяют применить в нем алгоритм поиска, аналогичный двоичному поиску в массиве. Каждое сравнение искомого значения и значения в вершине позволяет выбрать для следующего шага правое или левое поддерево. Алгоритмы включения и исключения вершин дерева не должны нарушать указанное свойство: при включении вершины дерева поиск места ее размещения производится путем аналогичных сравнений. Эти алгоритмы являются линейно рекурсивными или циклическими.
//----- Обход двоичного дерева
void Scan(btree *p, int level){
if (p==NULL) return;
Scan(p->left,level+1);
printf("l=%d val=%d\n",level,p->val);
Scan(p->right,level+1); }
//----- Поиск в двоичном дереве---------------
// Возвращается указатель на найденную вершину
btree *Search(btree *p, int v){
if (p==NULL) return NULL; // Ветка пустая
if (p->val == v) return p; // Вершина найдена
if (p->val > v) // Сравнение с текущим
return Search(p->left,v); // Левое поддерево
else
return Search(p->right,v); } // Правое поддерево
//----- Включение значения в двоичное дерево--------------
// Используется ссылка на указатель на текущую вершину
void Insert(btree *&pp, int v){
if (pp == NULL) { // Найдена свободная ветка
pp = new btree; // Создать вершину дерева
pp ->val = v;
pp->left = pp->right = NULL;
return;
}
if (pp->val > v) // Перейти в левое или
Insert(pp->left,v); // правое поддерево
else
Insert(pp->right,v);
}
Обратите внимание, что указатель pp ссылается на то место в дереве, где находится указатель на текущую вершину, а потому под него можно производить запись (присваивание) при создании новой вершины. При замене рекурсии циклом пришлось бы довольствоваться явным двойным указателем btree **pp .
Нумерация вершин в двоичном дереве
В двоичном дереве естественная нумерация вершин соответствует обходу в порядке возрастания их значений, то есть левое поддерево текущая вершина правое поддерево.
//---- Обход двоичного дерева с нумерацией вершин
void ScanNum ( btree *q, int &n ) {
if (q==NULL) return;
ScanNum(q->left,n);
printf("n=%d val=%d\n",n,q->val); n++;
ScanNum(q->right,n);}
Контрольные вопросы
- Что представляет собой двоичное дерево?
- Чем отличается двоичное дерево от двусвязного списка?
- В чем заключается особенность дерева как структуры данных?
- Процедуры какого характера наиболее эффективны при работе с деревьями?
- В чем заключается вставка узла в дерево?
- В чем заключается удаление узла из дерева?
- Каковы особенности удаления элемента из древовидной структуры данных?
- В чем заключается поиск в дереве?
- Что такое «прохождение дерева»?
- Какие возможны варианты прохождения дерева?
- Что такое высота дерева?
- Как сохранить сбалансированность дерева при вставке и удалении узлов?
Задания для практической работы
Создать класс операций по работе с деревом. Программа должна содержать функцию обхода дерева с выводом его содержимого, функцию добавления вершины дерева (ввод), а также указанную в варианте функцию.
- Вершина дерева содержит указатель на строку. Строки в дереве не упорядочены. Функция включает вершину в дерево с новой строкой в ближайшее свободное к корню дерева место. ( В результате дерево будет сбалансированным). Для исключения полного обхода в каждую вершину дерева поместить длину его минимальной ветви и корректировать его в процессе включения во всех проходимых вершинах.
- Вершина двоичного дерева содержит массив целых и два указателя на правое и левое поддерево. Массив целых в каждом элементе упорядочен, дерево в целом также упорядочено. Функция включает в дерево целую переменную с сохранением упорядоченности.
- Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддерево. Строки в дереве упорядочены по возрастанию. Написать функций включения строки и получения указателя на строку по заданному номеру, который она имеет в упорядоченной последовательности обхода дерева.
- Элемент дерева содержит либо данные (строка ограниченной длины), либо указатели на правое и левое поддеревья. Строки в дереве упорядочены. Написать функцию включения новой строки. (Обратить внимание на то, что элемент с указателями не содержит данных, и при включении новой вершины вершину с данными следует заменить на вершину с указателями).
- Вершина дерева содержит целое число и массив указателей на поддеревья. Целые в дереве не упорядочены. Функция включает вершину в дерево с новой целой переменной в ближайшее свободное к корню дерева место. (То есть дерево должно иметь ветви, отличающиеся не более чем на 1).
- Вершина дерева содержит два целых числа и три указателя на поддеревья. Данные в дереве упорядочены. Написать функцию включения нового значения в дерево с сохранением упорядоченности.
- Вершина дерева содержит указатель на строку и N указателей на потомков. Функция помещает строки в дерево так, что строки с меньшей длиной располагаются ближе к корню. Если новая строка " проходит" через вершину, в которой находится более длинная строка, то новая занимает место старой, а алгоритм включения продолжается для старой строки. Функция включения выбирает потомка минимальным количеством вершин в поддереве.
- Вершина дерева содержит либо 4 целых значения, либо 2 указателя на потомков, причем концевые вершины содержат данные, а промежуточные - указатели на потомков. Естественная нумерация значений производится при обходе концевых вершин слева направо. Разработать функции получения и включения значения в дерево по логическому номеру.
- Вершина дерева содержит N целых значений и два указателя на потомков. Запись значений производится таким образом, что меньшие значения оказываются ближе к корню дерева (то есть все значения в поддеревьях больше самого большого значения у предка). Разработать функции включения и поиска данных в таком дереве. Если новое значение " проходит" через вершину, в которой находится большее, то оно замещает большее значение, а для последнего алгоритм включения. Функция включения выбирает потомка максимальным значением в поддереве.
- Выражение, содержащее целые константы, арифметические операции и скобки, может быть представлено в виде двоичного дерева. Концевая вершина дерева должна содержать значение константы. Промежуточная - код операции и указатели на правый и левый операнды - вершины дерева. Функция получает строку, содержащую выражение, и строит по ней дерево. Другая функция производит вычисления по полученному дереву.
- Вершина дерева содержит указатель на строку и динамический массив указателей на потомков. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция при включении строки создает вершину, наиболее близкую к корню.
- Вершина дерева содержит динамический массив целых значений и два указателя на потомков. Значения в дереве не упорядочены. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция включает новое значение в свободное место в массиве ближайшей к корню вершины.
- Вершина дерева содержит массив целых и два указателя на правое и левое поддерево. Значения в дереве не упорядочены. Естественная нумерация значений производится путем обхода дерева по принципу " левое поддерево - вершина - правое поддерево" . Разработать функции включения и получения значения элемента по заданному логическому номеру.
- Написать функцию, которая добавляет к бинарному дереву T новую вершину с элементом E (если ее не было в T).
- Написать функцию , которая заменяет в дереве T значения всех отрицательных элементов вершин на их абсолютные величины (информационное поле вершины дерева T имеет тип Real).
- Написать функцию , которая удаляет все вершины с одинаковыми элементами из непустого дерева T (разрешается использовать вспомогательную множественную структуру данных).
- Написать функцию , которая удаляет из непустого бинарного дерева T вершины, содержащие максимальный и минимальный элемент (информационное поле вершины дерева имеет тип Real).
- Написать функцию , которая удаляет из непустого дерева поиска T вершины, содержащие максимальный и минимальный элемент (информационное поле вершины дерева имеет тип Real).
- Написать функцию , которая удаляет из непустого дерева все вершины с положительными элементами (информационное поле вершины дерева имеет тип Real).
- Написать функцию , которая удаляет из непустого дерева поиска все вершины с отрицательными элементами (информационное поле вершины дерева имеет тип Real).
- Написать функцию, которая определяет, входит ли вершина, содержащая информационное поле E, в заданное бинарное дерево дважды.
- Написать функцию, которая проверяет, входит ли вершина, содержащая информационное поле E, в правое или левое поддерево заданного дерева поиска.
- Написать функцию, которая проверяет совпадают ли элемент из самого левого листа непустого поиска дерева с элементом из самого правого листа того же дерева.
- Установить, можно ли попасть из одной вершины бинарного дерева в другую, если двигаться по ветвям к листьям.
- Установить, можно ли попасть из одной вершины дерева поиска в другую, если двигаться по ветвям к листьям.
- Используя линейную скобочную запись дерева поиска, описать логическую функцию, проверяющую на равенство деревья поиска T1 и T2.
- Написать с помощью линейной скобочной записи бинарного дерева функцию, проверяющую, входит ли вершина с элементом E в правое (левое) поддерево заданного бинарного дерева.
- Два бинарных дерева называются изоморфными, если можно отобразить одно из них в другое, изменив порядок сыновей его узлов. Распознать изоморфизм двух данных бинарных деревьев.
- Описать функцию , которая определяет количество вхождений вершины с заданным элементом E в бинарное дерево.
- Описать функцию , которая вычисляет сумму элементов всех вершин заданного непустого дерева поиска (информационное поле вершины дерева имеет тип Real).
- Описать функцию, которая определяет максимальную глубину непустого дерева, т.е. количество ветвей в самом длинном из путей от корня дерева до листьев.
- Определить глубину (высоту) непустого дерева поиска, используя функцию определения пути от данной вершины до корня.
- Используя линейную скобочную запись дерева, описать функцию, которая определяет максимальную глубину непустого бинарного дерева.
- Описать функцию, которая подсчитывает количество вершин на k-ом уровне непустого дерева поиска (корень - вершина 0-го уровня).
- Написать функцию, которая определяет количество вхождений элемента E в информационные поля вершин левого поддерева заданного бинарного дерева.
- Написать функцию, которая вычисляет среднее арифметическое всех элементов заданного непустого дерева (информационное поле вершины дерева имеет тип Real).
- Написать функцию, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до 1ближайшей вершины с заданным элементом E.
- Определить суммарный путь данного дерева поиска, используя функцию определения пути от данной вершины до корня.
- Используя линейную скобочную запись дерева, написать функцию, которая находит содержимое информационного поля самого левого (правого) листа непустого дерева поиска.
- Используя линейную скобочную запись дерева, написать функцию, которая определяет количество вхождений вершины с элементом E в левое поддерево заданного бинарного дерева.
- Используя линейную скобочную запись дерева, написать функцию, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до вершины с заданным элементом E.
- Написать функцию, которая выбирает из непустого дерева поиска все разные английские буквы (информационное поле вершины дерева имеет тип Char).
- Написать функцию, которая определяет максимальный элемент из всех листьев непустого бинарного дерева (информационное поле вершины дерева имеет тип Integer).
- Написать процедуру, которая выводит на экран содержимое информационных полей всех внутренних вершин бинарного дерева.
- Выписать все вершины дерева поиска, находящиеся на заданном уровне k (k=0,1,2,...), используя функцию определения пути от данной вершины до корня.
- Используя линейную скобочную запись дерева, описать процедуру, которая определяет элементы всех внутренних вершин дерева поиска.
- Используя линейную скобочную запись дерева, описать процедуру, которая выводит на экран содержимое информационных полей всех листьев заданного дерева поиска.
- Написать функцию , которая записывает в файл F элементы вершин заданного дерева поиска в порядке возрастания.
- Множество целых чисел поместить в дерево поиска и на основе этого представления упорядочить данное множество.
Сбалансированные двоичные деревья
После каждой операции изменения дерева можно проводить балансировку дерева, которая позволяет минимизировать его высоту. При этом поиск по двоичному дереву будет требовать минимального времени. Балансировка позволяет также ускорить операции вставки и удаления узлов, которые тоже требуют проведения поиска.
К сожалению, пока нет способа проведения быстрой балансировки дерева до его минимальной высоты. Тем не менее, балансировка является очень эффективным методом. Мы не можем провести балансировку дерева до его минимальной высоты, но, задав критерий "разбалансированности" дерева перед проведением очередной балансировки, можно приблизиться к этой минимальной высоте. В этом случае, хотя мы и не получаем дерева с минимально возможной высотой в каждый момент времени, тем не менее, находимся близко к минимуму.
Алгоритм балансировки состоит из двух частей:
Дерево преобразуется в лозу.
Лоза перестраивается в сбалансированное дерево.
Лоза (vine) — это левоассоциативное двоичное дерево. Она имеет следующий вид:
Рис.1. Левоассоциативное двоичное дерево – лоза.
Главная лоза (рис.2) (main vine) — это левоассоциативное поддерево двоичного дерева.
Рис.2. Левоассоциативное поддерево двоичного дерева.
На рисунке вершины главной лозы окрашены в белый цвет.
Преобразование двоичного дерева в лозу.
Мы проходим по дереву указателем p, начиная в корне дерева. Вспомогательный указатель q указывает на родителя p (поскольку мы строим левоассоциативное дерево, то p всегда является левым ребенком q). На каждом шаге возникает одна из двух возможных ситуаций:
- Если у p нет правого ребенка, то эта часть дерева уже перестроена. p и q просто спускаются по дереву (приравниваются своим левым сыновьям).
- Если у p есть правый ребенок (обозначим его r), тогда выполняется левый поворот относительно p:
Рис. 3. Выполнение левого поворот
На рисунке a, b и c обозначают поддеревья, которые могут быть пусты. После поворота устанавливаем указатель p на r.
Преобразование лозы в сбалансированное двоичное дерево.
Этот этап алгоритма более содержательный и поэтому менее очевидный. Поэтому сначала будет разобран простой пример, а потом будет дано его обобщение.
Пусть есть лоза, которая состоит из 2n-1 вершин для какого-либо натурального n. Для примера возьмем n=4, тогда лоза будет содержать 15 вершин. Преобразуем данную лозу в сбалансированное дерево за три операции перестроения.
На первой операции пройдем по лозе сверху вниз, начиная в корне, и раскрасим каждую вершину соответственно в серый или черный цвет (условимся, что корень будет серого цвета). Затем возьмем каждую серую вершину, кроме самой нижней, сделаем ее правым ребенком черной вершины, являющейся ее левым ребенком. Т.е. выполним малый правый поворот относительно каждой серой вершины, кроме самой нижней (на рисунке 4 приведен пример малого правого поворота относительно вершины X).
Рис.4. Малый правый поворот относительно вершины X
Таким образом, вместо лозы, состоящей из 15 вершин, мы получим дерево, состоящее из 7 черных вершин и 8 серых вершин (Рис.5).
Рис.5. Первое перестроение.
Для второго перестроения (рис.6) сначала перекрасим серые вершины в белые. Далее перекрасим каждую вторую черную вершину в серый цвет, начиная в корне. Теперь, как и раньше, выполним малый правый поворот относительно каждой серой вершины, кроме самой нижней.
Рис.6. Второе перестроение.
Третье перестроение аналогично первым двум. Вершины 12 и 4 перекрашиваются в серый цвет, затем выполняется малый правый поворот относительно вершины 12. В результате получается сбалансированное дерево.
Рис.7. Третье перестроение.
Теперь необходимо разобраться со случаем, когда длина лозы не может быть представлена в виде 2n-1 для какого-либо натурального n. В этом случае необходимо привести длину главной лозы к требуемому значению.
Пусть лоза состоит из m вершин. Тогда существует такое n, что (2n-1) < m < (2n+1-1). Необходимо укоротить главную лозу на m – (2n-1) вершин. После этого можно перестроить получившееся дерево аналогично способу, описанному выше. В результаты получится сбалансированное дерево с m – (2n-1) листьями.
Для примера разберем случай, когда лоза состоит из 9 вершин. Отсюда следует, что n=3, т.к. (23-1)=7<9<15=(24-1). Следовательно, необходимо укоротить главную лозу на 9-(23-1)=2. После этого перестраиваем дерево аналогично примеру, приведенному выше. В результате у нас должно получиться сбалансированное дерево.
Рис.8. Сбалансированное дерево с m - (2n-1) листьями
Контрольные вопросы
Что означает термин «сбалансированное» дерево?
Для чего выполняется балансировка?
Опишите фазы балансировки.
Как происходит преобразование исходного дерева в лозу?
Как происходит преобразование лозы в сбалансированное дерево?
В каких случаях необходимо укорачивать лозу?
Как определить размер укорачивания?
Задания для практической работы
Требуется разработать программу по представленному алгоритму и на основе ранее полученных знаний по основным операциям работы с деревьями. Программа должна быть универсальной, для любого количества вершин.
Графы
Основные понятия
В процессе обработки данных на компьютере часто приходится моделировать объекты сложной структуры, содержащие в качестве составных частей (элементов) объекты более простой структуры. Примерами таких структур являются— массивы, множества, списки и деревья. Иногда сложный объект состоит из некоторого множества элементов одного и того же типа, между которыми существуют определенные связи (отношения). В технике такие объекты часто называют сетями.
Для моделирования сетей в математике служат объекты, называемые графами. Графом G называется пара множеств (V, E), где V— конечное множество элементов, называемых вершинами графа, а E— конечное множество упорядоченных пар е = (w, v), называемых дугами, где w, v— вершины.
Говорят, что дуга е выходит из вершины w и входит в вершину v. Вершины w и v называют инцидентными дуге е, а дугу е — инцидентной вершинам w и v.
В этом определении множество вершин V соответствует множеству узлов моделируемой сети, а множество дуг— связям между узлами. Определение, данное выше, отражает лишь структуру сети, но не характеристики ее отдельных узлов и связей. Если такие характеристики все же существенны, то рассматривают нагруженные графы, в которых с каждой вершиной или дугой (может быть, и с тем, и с другим) связана величина или несколько величин, называемых нагрузкой на граф. Формально говоря, нагрузку графа определяют функции:
f:V->W1 и g: E -> W2,
где W1 и W2 представляют собой множества значений нагрузки вершин и дуг графа соответственно. Иногда при анализе графа неважно, какая из вершин w и v в дуге е = (w, v) первая, а какая вторая, т. е. пара (w, v) не упорядочена. В этом случае дугу е называют ребром, а весь граф называют неориентированным в отличие от ориентированного графа, задаваемого исходным определением. Разумеется, в этом случае бессмысленно говорить о том, из какой вершины ребро выходит и в какую вершину входит. Формально говоря, неориентированным графом называют такой граф, у которого наряду с любой дугой e1 = (u, v) имеется и противоположная дуга е2 — (v, u). Эта пара дуг и образует ребро е = <u, v> неориентированного графа.
Алгоритмы представления графа
При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирования. Выбор представления графа определяется прежде всего тем, какие алгоритмы обработки графов используются, а также соображениями экономии памяти при обработке очень больших графов или в условиях жестких ограничений на расход памяти.
Говоря о представлении графа, имеют в виду прежде всего вопрос о представлении в памяти его структуры, т. е. считается, что по представлению графа нужно уметь определять, какие вершины с какими другими вершинами в графе связаны. На практике кроме структуры графа нужно каким-то образом представлять и нагрузку на его вершины и дуги. От того, какие элементы графа нагружены и какого типа эта нагрузка, тоже зависит представление графа.
Ниже приводится несколько способов представления графов, причем для каждого способа указано, для каких алгоритмов он подходит, а также дана приблизительная оценка занимаемой памяти. Везде далее считается, что число вершин графа N = card(V) и число дуг (или ребер) графа M = card(E) — величины постоянные. Можно считать, что вершины графа имеют номера от 0 до N-1, а каждая дуга характеризуется парой номеров вершин, инцидентных этой дуге.
В листингах будем представлять только структуру графов, причем для каждого способа представления опишем только конструктор соответствующего класса и операции добавления новой дуги и проверки наличия дуги с заданными концами. Поскольку большинство операций, представленных ниже в листингах, одинаковы для всех представлений графов, имеет смысл описать абстрактный класс Graph, в котором и определить все эти операции в виде пустых виртуальных функций. Тогда конкретные представления графов будут описаны в виде классов, производных от базового класса Graph.
Представление графа в виде массива
Первое из описываемых представлений графа основано на следующих соображениях. Структуру графа можно описать, сопоставив каждой вершине множество дуг, выходящих из нее, причем каждая дуга, выходящая из вершины u, идентифицируется своим концом— номером вершины, в которую эта дуга входит. Таким образом, граф представляется массивом, в котором каждому номеру вершины и в диапазоне от 0 до N сопоставлено множество целых чисел — номеров вершин, в которые входят дуги, исходящие из выбранной вершины u. Описанное представление графа будем называть S-графом (от set— множество). Будем считать, что множество целых чисел в диапазоне от 0 до N представлено объектом класса Set. Тогда S-граф может быть описан следующим классом:
файл graph.h
class Graph
{
public:
// Функция addArc позволяет добавить к графу новую дугу,
// ведущую из вершины с номером from в вершину с номером to.
virtual void addArc (int from, int to) = 0;
// Функция has Arc проверяет, имеется ли в графе дуга, ведущая
//из вершины с номером from в вершину с номером to.
virtual bool hasArc(int from, int to) const = 0;
// Функция vertexCount выдает число вершин графа
virtual int vertexCount() const = 0;
};
файл setgraph.h
#include "graph.h"
#include "set.h" // Определение класса для работы с множествами
class SetGraph : public Graph {
Set **graph; // Массив множеств дуг
int vertexNumber; // Число вершин
public:
// Конструктор графа с n вершинами создает массив из пустых множеств
SetGraph(int n) : vertexNumber(n), graph(new Set*[n])
{ for (int i = 0; i < n; i++) { graph[i] = new Set(0,n); }
}
// Деструктор уничтожает массив множеств
~SetGraph();
// Функция подсчета числа вершин просто выдает
// ранее сохраненное значение
int vertexCount () const { return vertexNumber; }
// Основные методы работы с графом
void addArc(int from, int to);
bool hasArc(int from, int to) const;
};
Все виртуальные функции легко реализуются с помощью соответствующих операций над множествами. Так, принадлежность дуги (и, v) графу может быть легко реализована следующим образом:
bool SetGraph::hasArc(int u, int v) const {
if (u < 0 || u >= vertexNumber || v < 0 || v >= vertexNumber)
return false; // Неправильно задана дуга
return graph[u]->has(v); }
Аналогично, добавление дуги к графу реализуется так:
void SetGraph::addArc(int u, int v) {
if (u < 0 || u >= vertexNumber || v < 0 || v >= vertexNumber)
return; // Неправильно задана дуга
*graph[u] |= v; }
В данной реализации при попытке задать номера вершин, которых заведомо нет в графе, функции просто ничего не делают. Возможно, более правильной моделью поведения было бы возбуждение исключительной ситуации.
В данном представлении также легко и эффективно реализуется метод, позволяющий удалить дугу с заданными номерами инцидентных ей вершин. Несколько сложнее решается задача перебора дуг, инцидентных данной вершине. Например, для того чтобы определить количество дуг, выходящих из вершины с заданным номером, нужно иметь возможность определять количество элементов в множестве. Если считать, что класс set содержит метод card для подсчета числа элементов множества (мощности множества), то число выходящих из заданной вершины u дуг легко получить с помощью выражения graph[u] .card(), однако число входящих в заданную вершину дуг может быть получено только путем перебора всех вершин графа.
Представление графа в виде матрицы смежности
Еще один распространенный способ представления графа — это представление в виде матрицы смежности размером N * N (рис.1). B этой матрице в элементе с индексами (i,j) записывается информация о дугах, ведущих из вершины с номером i в вершину с номером j. В важном частном случае простого графа, т. е. графа, в котором каждая упорядоченная пара вершин соединена не более чем одной дугой, и отсутствуют дуги вида (u, u), элементы матрицы могут принимать значения 0 или 1 в зависимости от того, существует ли соответствующая дуга. Ясно, что такое представление самым тесным образом связано с представлением, описанным выше в определении класса setGraph.
Представление в виде матрицы смежности будем называть М-графом. Удобно связывать с матрицей смежности информацию о нагрузке на дуги. В этом случае элементом матрицы будет либо значение нагрузки на соответствующую дугу, либо некоторое стандартное значение, говорящее об отсутствии дуги.
Рис.1. граф и его представление в виде матрицы смежности
Если, например, граф моделирует транспортную сеть, в которой нагрузка на дугу представляет расстояние между пунктами, соединенными этой дугой, то признаком отсутствия дуги удобно сделать значение 0 или, напротив, максимально возможное целое, смотря по тому, что окажется более удобным в используемом алгоритме. В общем виде, если тип нагрузки представлен значениями класса W, то представление графа будет содержать двумерный массив значений класса W. Мы для простоты не будем интересоваться нагрузкой на дуги графа, таким образом, элементами матрицы, представляющей М-граф, могут быть просто логические значения.
файл MatrixGraph.h
#include "graph.h"
class MatrixGraph : public Graph {
bool **graph;
int vertexNumber;
public:
// Конструктор с параметром - количеством вершин графа.
MatrixGraph(int n);
// Количество вершин постоянно и содержится в поле vertexNumber
int vertexCount() const { return vertexNumber; }
// Остальные виртуальные функции, реализацию которых требуется
// предоставить при определении конкретного представления графа
void addArc(int from, int to);
bool hasArc(int from, int to) const;
};
файл MatrixGraph.cpp
#include "MatrixGraph.h"
// Реализация конструктора - заказ и инициализация памяти
// под двумерный массив логических значений
MatrixGraph::MatrixGraph(int n)
{
graph = new bool*[vertexNumber = n];
for (int i = 0; i < n; i++)
{
bool * row = graph[i] = new bool[n];
for (int j = 0; j < n; j++) {
row[j] = false; }
}
}
bool MatrixGraph::rhasArc(int from, int to) const
{
if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber)
return false; // неправильно заданы номера вершин
return graph[from][to];
}
void MatrixGraph::addArc(int from, int to)
{
if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber)
return; // невозможно добавить дугу
graph[from][to] =true; )
Поскольку представление M-графа очень близко к представлению S-графа, то и операции над M-графом выполняются практически с той же степенью эффективности, что и для S-графа. Удобными и эффективно реализуемыми операциями над M-графом являются операции проверки наличия дуги, значения ее нагрузки (в случае нагруженного графа), добавления и удаления дуг, изменения нагрузки.
Менее эффективными операциями будут операция подсчета или перебора дуг, инцидентных заданной вершине. Между тем во многих алгоритмах именно эта операция является самой часто используемой. Структура графа может меняться крайне редко, а вот исследоваться эта структура будет достаточно часто, причем инцидентность вершин и дуг чаще всего является главным предметом таких исследований. В этом случае представление графа в виде матрицы смежности будет неудобным.
Еще одно соображение. Если число вершин графа велико, то матрица смежности будет занимать достаточно много места. В то же время в графе количество дуг чаще всего существенно меньше NxN— размера матрицы, так что большинство элементов матрицы смежности будут пустыми.
Представление графа в виде связанного списка
Списки вообще удобны тем, что могут содержать переменное количество элементов, при этом общий размер занимаемой ими памяти соответствует количеству элементов списка. Каждый элемент списка будет содержать информацию об одной дуге, причем номер вершины, из которой эта дуга исходит, определяется самим местоположением списка, так что его можно в самом элементе списка не хранить. Информация о дуге будет содержать номер вершины, в которую эта дуга входит, а в случае нагруженного графа также и значение нагрузки на дугу (рис.2).
Рис.2. Граф и его представление в виде связанных списков.
Соответствующее представление будем называть L-графом (от list— список). В листинге приведено возможное описание класса и реализация операций для ненагруженного L-графа. Кроме описания класса для L-графа в листинге показано определение простого однонаправленного списка объектов с операциями добавления элемента в список и проверки наличия элемента в списке.
файл ListGraph.h
#include "graph.h" // Описание родительского класса
// Описание шаблона классов для представления
// простых однонаправленных списков
template <class T>
class List {
// Внутренний класс для представления элементов списка
struct Listltem {
Т item; // Собственно элемент списка
Listltem *next; // Ссылка на следующий элемент списка
// Конструктор элементов введен для удобства реализации операций
Listltem(const T fiitem, Listltem *next = NULL)
{
Listltem::item = item;
Listltem::next = next; }
};
// Список представлен ссылками на первый и последний элементы...
Listltem *first, *last;
// ...а также счетчиком числа элементов
int count;
public:
// Конструктор пустого списка - единственный в нашем описании
List() { first = last = NULL; count = 0; )
// Операции добавления элемента...
void add(const T &);
// ...и проверки наличия элемента в списке
bool has(const T &) const;
};
// Собственно описание класса для представления L-графа
class ListGraph : public Graph {
// Массив списков целых, каждое из которых задает
// номер вершины, в которую входит дуга. Индексы в массиве
// задают номера вершин, из которых эти дуги исходят.
List<int> *graph;
// Количество вершин в графе.
int vertexNumber;
public:
// Конструктор порождает N списков и инициализрует массив этих
// списков, запоминая количество вершин, заданное аргументом
ListGraph(int n) { graph = new List<int>[vertexNumber = n]; }
// Операция подсчета вершин просто выдает запомненное ранее значение
int vertexCount() const { return vertexNumber; 1
// Две следующие функции реализуют операции над дугами
void addArc(int from, int to);
bool hasArc(int from, int to) const;
};
файл ListGraph.cpp
#include "ListGraph.h"
// Реализация операций над списком.
// Добавление нового элемента в список
template <class T>
void List<T>::add(const T & item) {
ListItem *newItem - new ListItem(item);
// Новый элемент включается в конец списка
if (last) last->next = newItem; else first = newItem;
last = newItem;
count++; }
// Проверка наличия элемента в списке
template <class T>
bool List<T>::has(const T & item) const {
// Список просматривается с начала в поисках нужного элемента
for (ListItem *current = first; current; current = current->next) {
if (current->item == item) return true;
}
// Элемент не найден
return false;
}
// Реализация операций над графом.
// Операция добавления дуги.
void ListGraph::addArc(int from, int to) {
if (from < 0 || from >= vertexNumber || to < 0 ||to >= vertexNumber)
return; // невозможно добавить дугу
// Добавление новой дуги в конец списка
graph[from].add(to); }
// Операция проверки наличия дуги.
bool ListGraph::hasArc(int from, int to) const {
if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber)
return false; // неправильно заданы номера вершин
//В списке с номером from ищем элемент to.
return graph[from].has(to);
}
Удаление дуги при таком представлении не удается реализовать столь же просто, как это было сделано для S-графа и M-графа. Для этого придется просмотреть соответствующий список, найти в нем нужную дугу и удалить ее из списка.
Представление графа в виде совокупности списков дуг становится неудобным в тех случаях, когда наиболее часто используются операции проверки наличия или модификации конкретной дуги, т. е. как раз те операции, которые наиболее эффективно реализуются для S-графов и M-графов. Зато эффективно реализуется перебор всех дуг, исходящих из заданной вершины, операция, которая сравнительно долго выполняется для S-графов и М-графов. Правда, для того чтобы найти дуги, входящие в заданную вершину, приходится вообще просмотреть все списки, т. е. пройти полностью всю структуру графа.
Представление графа в виде списка дуг
Иногда используются и другие представления графов, например, для случая очень разреженных графов, когда при большом количестве N вершин графа число дуг существенно меньше NXN, например, порядка N. Одним из таких представлений является представление в виде списка дуг, когда все дуги графа собраны в единый список, в каждом элементе которого записана информация об обоих концах дуги, а также, возможно, о нагрузке на дугу (рис.3).
Рис.3. Граф и его представление в виде списка дуг.
В листинге приведено представление графа в виде списка дуг. Такое представление будем называть A-графом от слова Arc— дуга. Список дуг представлен списком элементов, каждый из которых содержит два целых числа— номера концов дуги. В данной реализации список не представлен в виде отдельного описания класса. Вместо этого описание элемента такого списка— дуги— внесено прямо в описание класса для представления A-графа, а реализации операций над списком просто являются частью реализации операций над дугами графа.
Операция добавления дуги в этом представлении — это просто операция добавления одного элемента в конец списка, и реализуется она сравнительно эффективно. Напротив, при выполнении операции поиска дуги может потребоваться просмотреть весь список. Разумеется, настолько же неэффективной будет и операция удаления дуги.
файл ArcGraph.h
#include "graph.h" // Определение родительского класса
// Описание класса для представления A-графа
class ArcGraph : public Graph {
// Дуга представлена элементом списка, содержащим номера
// концов дуги и указатель на следующий элемент списка
struct Arc {
int begin, end;
Arc *next;
// Конструктор дуги.
Arc{int b, int e, Arc *n = NULL) {
begin = b; end = e; next = n; )
};
// Список дуг представлен, как обычно,
// указателями на первый и последний элементы списка
Arc *first, *last;
// arcCount - счетчик числа дуг-элементов списка
int arcCount;
// vertexNumber - количество вершин графа, используемое
//в данном представлении только для контроля номеров вершин
int vertexNumber;
public:
// Конструктор графа инициализирует пустой список
// и запоминает количество вершин графа.
ArcGraph(int n) {
first = last = NULL; arcCount = 0; vertexNumber = n;
}
// Функция подсчета количества вершин выдает запомненное значение
int vertexCoun() const { return vertexNumber; }
// Операции над дугами:
void addArc(int from, int to);
bool hasArc(int from, int to) const;
};
файл ArcGraph.cpp
«include "ArcGraph.h"
//Реализация операции добавления дуги
void ArcGraph::addArc(int from, int to) {
// Сначала проверяем правильность задания номеров вершин.
if (from < 0 || to < 0 || from >= vertexNumber || to >=vertexNumber)
return;
Arc *newArc = new Arc(from, to);
// Новая дуга добавляется в конец списка
if (last) last->next = newArc; else first = newArc;
last = newArc;
arcCount++;
}
// Реализация операции проверки наличия дуги.
bool ArcGraph::hasArc(int from, int to) const {
// Необходимо просмотреть список дуг в поисках нужной.
for (Arc *current = first; current; current = current->next) {
if (current->begin == from && current->end == to)
return true;
}
return false;
}
Конечно, выбирать представление графа для решения конкретной задачи нужно исходя из того, какие операции с графами будут выполняться чаще всего. Если в процессе работы граф часто меняет структуру связей, то, наверное, лучшим способом представления будет матрица смежности. Если наиболее частой операцией будет поиск путей в графе, проходящих по направлению дуг, то более удобным и выгодным способом будет способ представления графа в виде списков смежности.
Однако иногда бывает, что выбрать какой-то один способ представления графа трудно, например, потому, что в разные периоды времени работы программы требуется выполнять различные операции. В этом случае было бы удобно переходить от одного представления графа к другому. К счастью, такие преобразования занимают не очень много времени. Конечно, для преобразования придется, по крайней мере, один раз просмотреть весь граф, но время, затраченное на построение нового представления, всегда будет прямо пропорционально размеру графа. Это означает, что если время работы некоторого алгоритма на графе имеет порядок сложности не меньше размера графа, то скорость его работы практически не зависит от способа представления графа, поскольку всегда можно перед началом работы выполнить нужное преобразование без существенной потери эффективности основного алгоритма.
Преобразования структур графа
приведем функции преобразования, которые могли бы использоваться для изменения представления графа. Так определенные функции должны, как правило, иметь доступ к структурам как исходного, так и результирующего графов, так что в соответствующих описаниях классов эти функции должны быть объявлены "друзьями" соответствующих классов. В листинге 1.13 описаны четыре функции для следующего преобразования структур: M-граф -> S-граф -> L-граф -А-граф -> M-граф.
Таким образом, с помощью этих функций можно из каждого описанного представления графа получить любое другое представление.
файл convert.срр
#include "SetGraph.h"
#include "MatrixGraph.h"
#include "ListGraph.h"
#include "ArcGraph.h"
// Функция преобразования представления из M-графа в S-граф
SetGraph * convert(const MatrixGraph & srcGraph) {
int n = srcGraph.vertexCoun();
SetGraph *destGraph = new SetGraph(n);
for (int i = 0; i < n; i++) {
// Представление строки исходного графа:
bool * srcRow = srcGraph.graph[i];
// Соответствующее множество результирующего графа:
Set & destRow = *destGraph->graph[i];
for (int j = 0; j < n; j++) {
// Новая дуга записывается с помощью операции
// добавления элемента к множеству
if (srcRow[j]) destRow |= j; } } return destGraph;
}
// Функция преобразования представления из S-графа в L-граф
ListGraph * convert(const SetGraph & srcGraph) {
int n = srcGraph.vertexCount();
ListGraph *destGraph = new ListGraph(n);
for (int i = 0; i < n; i++) {
// Представление строки исходного графа:
Set & srcRow = *srcGraph.graph[i];
// Соответствующий список дуг в результирующем графе:
List<int> & destRow = destGraph->graph[i];
for (int j = 0; j < n; j++) {
// Обе операции - проверка принадлежности множеству и добавления
// элемента в список выполняются за фиксированное время.
if (srcRow.has(j)) destRow.add(i);
}}
return destGraph;
}
// Функция преобразования представления из L-графа в А-граф.
// В этой функции используются только открытые операции А-графа,
// поэтому она может и не "дружить" с описанием класса ArcGraph
ArcGraph * convert(const ListGraph & srcGraph) {
int n = srcGraph.vertexCount0;
ArcGraph *destGraph = new ArcGraph(n);
for (int i = 0; i < n; i++) {
List<int>::ListItem *current = srcGraph.graph[i].first;
while (current) {
// Добавление дуги в список дуг с помощью операции addArc.
destGraph->addArc(i, current->item);
current = current->next; } } return destGraph;
}
// Функция преобразования представления из А-графа в M-граф.
MatrixGraph * convert(const ArcGraph & srcGraph) {
int n = srcGraph.vertexCount();
MatrixGraph *destGraph = new MatrixGraph(n);
// в цикле перебираются все дуги
for (ArcGraph::Arc * current = srcGraph.first; current; current = current->next) {
destGraph->graph[current->begin][current->end] = true;
}
return destGraph;
}
Обходы в графах
Как и в случае обхода деревьев, для графов существуют два основных класса обходов: обходы в глубину и обходы в ширину.
Обходы в глубину пытаются каждый раз после прохождения некоторой вершины А выбрать в качестве следующей такую вершину В, в которую из вершины А ведет дуга. Таким образом, алгоритмы этого класса пытаются всегда двигаться вглубь графа, находя все новые не пройденные ранее вершины. Если таких непройденных вершин нет, то алгоритм возвращается к предыдущей, ранее пройденной вершине, и пытается найти очередную дугу, ведущую из нее в какую-либо другую еще не пройденную вершину. Если и таких вершин нет, то снова происходит откат назад, и так до тех пор, пока либо все вершины не будут пройдены, либо алгоритм вернется назад в вершину, выбранную в качестве исходной.
Обходы в ширину пытаются, начав с некоторой вершины, в качестве очередных рассматривать только вершины, непосредственно связанные с исходной. Только после того, как все такие вершины будут рассмотрены, алгоритм будет пытаться рассматривать следующий слой вершин, непосредственно связанных с только что пройденными. Таким образом, алгоритм обхода в ширину последовательно рассматривает все более удаленные от исходной вершины до тех пор, пока либо все вершины не будут пройдены, либо не останется больше вершин, достижимых из исходной.
Рассмотрим в качестве примера граф, изображенный на рис. 3. Этот граф содержит 9 вершин и 12 дуг. Он состоит из двух компонент связности, так что заведомо не удастся обойти его весь, выбрав некоторую вершину в качестве исходной и проходя только по направлениям дуг. Тем не менее если сначала выбрать в качестве исходной вершины вершину 1, то все остальные вершины одной компоненты связности из нее будут достижимы, так что по крайней мере эта компонента связности будет пройдена до того, как потребуется вновь выбирать начальную вершину. Тем же свойством обладают и все остальные вершины графа, кроме вершины 7. Если выбрать ее в качестве начальной вершины для обхода, то будет пройдена только она сама, а потом потребуется вновь выбирать некоторую вершину в качестве начальной для обхода остальных.
Если в качестве алгоритма обхода взять алгоритм обхода в глубину, причем договориться, что из всех возможных альтернатив он всегда выбирает проход к вершине с наименьшим номером, то получится следующий порядок обхода вершин графа:
0; 1; 4; 6; 3; 7; 2; 8; 5
Порядок обхода в ширину в данном случае отличается от порядка обхода в глубину незначительно:
0; 1; 4; 6; 7; 3; 2; 8; 5
это получается потому, что граф, выбранный для примера, очень небольшой. Обычно в случае больших графов порядки обхода отличаются весьма существенно.
На рис. 3 также изображена логическая структура графа. Для того чтобы яснее представить себе работу алгоритмов обхода, необходимо хорошо представлять также и физическую структуру памяти соответствующего объекта.
В представлении графа рис. 3 в виде L-графа имеются 9 списков дуг (для каждой вершины существует список исходящих из нее дуг). На этом рисунке изображен массив списков дуг (около каждого элемента массива показан номер соответствующей вершины графа). Дуги представлены прямоугольниками, содержащими номер той вершины, в которую дуга входит.
В качестве первого примера рассмотрим внешний итератор вершин графа при обходе в глубину. Для того чтобы перейти от текущей вершины графа к следующей, итератор должен, во-первых, запоминать, какие из вершин уже пройдены или не пройдены, а во-вторых, для быстрого возврата к предыдущей вершине помнить последовательность дуг на пути из выбранной начальной вершины в текущую. Эту последовательность дуг будет удобно представляться в виде стека, элементами которого будут содержать информацию, необходимую для возврата по дугам.
Пусть алгоритм выбрал в качестве начальной вершину с номером 0. Тогда обход графа начнется в ситуации, приведенной в первой строке табл.1.
Таблица 1. Последовательность состояний при обходе графа в глубину
|
Шаг |
Список пройденных вершин |
Текущая вершина |
Стек дуг на пути к текущей вершине |
|
1 |
— |
0 |
— |
|
2 |
0 |
1 |
0-1 |
|
3 |
0,1 |
4 |
0-1, 1-4 |
|
4 |
0, 1,4 |
6 |
0-1, 1-4, 4-6 |
|
5 |
0, 1,4,6 |
3 |
0-1, 1-4, 4-6, 6-3 |
|
6 |
0, 1,4, 6,3 |
7 |
0-1, 1-4, 4-7 |
|
7 |
0, 1,4, 6, 3,7 |
— |
— |
|
8 |
0,1,4, 6, 3,7 |
2 |
— |
|
9 |
0, 1,4, 6, 3, 7,2 |
8 |
2-8 |
|
10 |
0, 1,4, 6, 3, 7, 2,8 |
5 |
2-8, 8-5 |
|
11 |
0, 1,4, 6, 3, 7,2, 8,5 |
— |
— |
Итератор обходит текущую вершину и выбирает следующую вершину из числа тех, в которые ведут дуги из текущей вершины. После первого шага ситуация будет такой, как показано в строке 2 табл. 1. Пройденная на этом шаге дуга 0-1 помещается в стек. Следующие три шага выполняются аналогично, а последовательное изменение ситуации показано в табл. 1 в строках 3-5.
В тот момент, когда текущей стала вершина 3, оказывается, что единственная дуга, ведущая из нее, ведет в уже пройденную вершину 0, поэтому следует, используя стек, вернуться на шаг назад в вершину 6 и попытаться найти следующую вершину по одной из дуг, ведущих из этой вершины. Поскольку новых дуг, ведущих из вершины 6, тоже больше нет, то делаем еще шаг назад к вершине 4. Теперь уже находится дуга, ведущая из этой вершины в еще не пройденную вершину 7, так что после прохода по соответствующей дуге образуется новая ситуация, показанная в табл. 1 в строке 6.
После прохождения вершины 7 оказывается, что больше нет дуг, ведущих в еще не пройденные вершины ни из вершины 7, ни из всех предыдущих вершин на пути в эту вершину. В строке 7 таблицы показана ситуация, возникшая после проверки всех этих дуг. Теперь можно снова выбрать произвольно одну из непройденных вершин, скажем, вершину 2, и далее алгоритм последовательно переберет вершины 2, 8 и 5 так, как показано в строках 8—11. Теперь все вершины графа оказываются пройденными.
Для обходов в ширину приведем два способа обхода— с помощью внешнего и внутреннего итераторов, которые, схематично описанного ниже.
Выберем произвольную вершину графа и начнем обход с этой вершины. В процессе работы алгоритма будем делить все вершины графа на три класса:
- пройденные вершины ("черные");
- вершины, которые будут пройдены на следующем шаге алгоритма ("серые");
- и все остальные непройденные вершины ("белые").
В начальный момент работы выбранная исходная вершина помещается в множество "серых" вершин, а все остальные вершины будут пока "белыми". Один шаг работы алгоритма состоит в том, что берутся все "серые" вершины, проходятся (и помещаются во множество "черных" вершин), затем находятся все "белые" вершины, в которые ведут дуги из только что пройденных вершин, и все найденные вершины перекрашиваются в серый цвет, т. е. помещаются в множество "серых" вершин.
Если "серых" вершин больше нет, то это означает, что пройдены уже все вершины, достижимые из исходной. Если при этом в графе еще остались непройденные "белые" вершины, можно снова выбрать одну из них в качестве исходной и повторить работу алгоритма.
На практике множество "серых" вершин можно организовать в виде очереди, тогда вершины из очереди можно брать по одной из головы очереди, а новые вершины, в которые ведут из нее дуги, сразу же помещать в конец очереди.
Определение путей и контуров Эйлера
Путь Эйлера проходит по каждому ребру в графе только один раз. Контур Эйлера проходит каждое ребро в графе тоже один раз, а также начинается и заканчивается в одной и той же вершине (рис. 4). Многие уже знакомы с концепцией следующей простой головоломки — нарисовать какое-то очертание без отрыва ручки от бумаги.
Если серьезно, то поиск путей и контуров Эйлера имеет более практичное применение. Их можно использовать для проложения маршрута по каким-либо реальным сетям таким образом, что каждое ребро будет проходиться в точности один раз. Существуют некоторые свойства, которыми должен обладать граф, чтобы в нем имелся путь или контур Эйлера.
Рис. 4. Граф, который имеет путь Эйлера, и сам этот путь.
Для существования контура Эйлера каждая вершина в графе должна иметь некоторую степень. Если любая вершина имеет нечетную степень, то сформировать контур Эйлера невозможно. В каждую вершину должны входить и из нее выходить только еще не пройденные ребра. Этого никогда не случится с вершиной, имеющей нечетную степень, потому что в нее можно войти, а выйти нельзя, поскольку все выходящие ребра уже пройдены.
Чтобы получить путь Эйлера, в графе должно быть точно две вершины с нечетной степенью. Путь должен начинаться и заканчиваться в вершине с нечетной степенью, потому что только эти вершины можно посетить дополнительное (для входа) количество раз.
Теперь очевидно, что для графа требуются ограничения. Граф не должен быть связанным. Однако этот граф должен содержать только один связанный подграф. Если граф содержит больше одного связанного подграфа, то он не может иметь путей или контуров Эйлера, так как некоторые ребра никогда не будут пройдены.
Любой граф, который удовлетворяет указанным условиям, должен иметь путь Эйлера или контур Эйлера. Такой граф называется эйлеровским.
Определение пути или контура Эйлера можно провести с использованием методики, похожей на глубинный поиск. Следующий алгоритм используется для поиска контура Эйлера, но его можно немного изменить, чтобы он позволял также находить путь Эйлера в любом графе, который удовлетворяет приведенным выше условиям.
На рисунках 5—8 показан пример выполнения такого алгоритма. Работа алгоритма заключается в локализации циклов в графе с использованием похожей на глубинный поиск методики. Эти циклы затем можно скомбинировать для образования одного цикла, который проходит по всем ребрам в графе, — цикла Эйлера. Алгоритм можно описать как последовательность следующих действий:
1. Инициализировать список циклов.
2. Выполнять глубинный поиск, пока все ребра не будут удалены из графа. Добавить текущий номер вершины в текущий путь. Пройти ребро, образованное в процессе поиска, и удалить его. Если ребер для просмотра больше нет, то добавить текущий путь в список циклов, а затем продолжить поиск непройденных вершин, начиная с первой вершины.
3. Объединить пути и циклы вместе для формирования контура Эйлера.
Рис. 5. Исходный граф.
Рассмотрим подробнее этот алгоритм. Глубинный поиск начинается с вершины v0 и на последующих итерациях посещаются вершины v1 и v3. После v3 достигается v0, и полученный цикл считается найденным. Затем цикл v0, v1, v4, v3 и v0 сохраняется.
Рис 6. Ребра графа, по которым проходит
путь 0->1->4->3-> 0 удаляются.
Затем глубинный поиск продолжается с первой вершины, которая имела выходящее из нее ребро. В нашем случае это вершина v,. При глубинном поиске может быть найден цикл v1, v2, v5, v4, v4, v7, v6, v3, v1 который добавляется в список циклов. Рис. 7 демонстрирует граф без второго найденного цикла.
Следующий этап глубинного поиска начинается с вершины v5; при этом обнаруживается цикл v5, v8 v7, v5. Начиная с этого момента, мы больше не найдем непросмотренных ребер. Таким образом, получилось три цикла.
Рис. 7. Граф с удаленными ребрами
по пути 1->2->5->4->7->6->3->1.
Этот же алгоритм с небольшими поправками можно использовать также для поиска пути Эйлера. Разница состоит в результате первого этапа поиска. Любой граф, удовлетворяющий условиям для контура Эйлера, после первого этапа поиска создает цикл. Чтобы найти путь Эйлера, первый поиск надо провести, начиная с одной из двух вершин с нечетными степенями. Результатом такого поиска будет путь от первой вершины с нечетной степенью ко второй. Все последующие этапы поиска дают циклы, которые можно вставить в первый путь таким же образом, как и в случае с контуром Эйлера.
Рис. 8. Найденный контур Эйлера.
Эффективная реализация этого алгоритма может оказаться немного громоздкой. Потенциальную проблему представляют неориентированные графы из-за обычного способа их представления. Хотя в графе ребро является единственным объектом, оно представляется как два ориентированных ребра, одно из которых идет от u к v, а другое — от v к u.
Прохождение матрицы смежности или списка смежных вершин для проверки ребер в соответствии с этим алгоритмом требует много времени. Желательно всегда передвигаться по списку ребер только вперед. Когда ребро просматривается, его можно либо удалить, либо поместить за указатель ребра этой вершины, и тогда оно больше никогда не будет просматриваться.
Это, безусловно, справедливо для ориентированных ребер; после того как ребро передается, оно больше никогда не исследуется. Неориентированные графы немного усложняют этот алгоритм, поскольку мы должны учитывать тот факт, что каждое ребро представлено в виде двух направленных ребер. Это значит, что изучить неориентированное ребро можно дважды, продвигаясь вперед и назад по каждому ребру и получая неправильные результаты.
Поиск кратчайших путей
Путем в графе называют чередующуюся последовательность вершин и дуг v1, e1, v2, e2,... vn-1 en-1, vn, в которой каждый элемент vi— вершина графа, а каждый элемент еi — дуга графа, ведущая из предыдущей вершины vi в следующую вершину vi+1|. Говорят, что такой путь соединяет вершину v1 с вершиной vn. Чаще всего рассматриваются простые пути, т. е. такие, в которых нет повторяющихся вершин, кроме, быть может, совпадения первой и последней вершины. В случае такого совпадения путь называется замкнутым или циклом.
Среди характеристик пути чаще всего рассматривается его длина— количество дуг в этом пути. Иногда с каждой дугой связывается некоторое число, которое можно интерпретировать как длину этой дуги. Граф в этом случае называется нагруженным, а длиной пути в нагруженном графе будет называться сумма длин входящих в этот путь дуг.
Самая простая задача поиска кратчайшего пути в графе состоит в следующем. Пусть заданы две вершины — начальная и конечная. Известно, что имеется по крайней мере один путь, по которому можно пройти, чтобы попасть из начальной вершины в конечную. Требуется указать один из таких путей.
Более интересная задача состоит в том, чтобы найти кратчайший путь между двумя вершинами при условии, что каждая дуга имеет определенную длину, так что мерой такого расстояния будет не количество дуг на кратчайшем пути, а суммарная длина пути.
Алгоритм Э. Дейкстры.
Опишем алгоритм нахождения такого пути при условии, что длины всех дуг неотрицательны. Этот алгоритм был предложен и опубликован Э. Дейкстрой (Е. W. Dijkstra), поэтому и носит его имя.
Алгоритм поиска кратчайшего пути в этом случае несколько напоминает алгоритм обхода графа в ширину и состоит в следующем. Будем рассматривать два множества: множество вершин, для которых уже известен кратчайший путь до них из начальной вершины (passed), и множество еще не исследованных вершин (notPassed).
В начале работы первое множество будет пустым, а второе будет содержать все вершины графа. На каждом шаге работы алгоритма из второго множества в первое переводится одна вершина — та, расстояние до которой от исходной вершины минимально. Эту вершину будем называть пограничной (border).
Для определения пограничной вершины во время работы алгоритма постоянно корректируется массив расстояний dist, в котором для каждой вершины хранится расстояние до нее от исходной вершины, если оно известно. В начале работы алгоритма расстояние известно только для одной вершины — начальной. Конечно, это расстояние равно нулю, так что эта вершина и будет выбрана первой в качестве пограничной. В дальнейшем массив будет корректироваться за счет просмотра вершин-кандидатов, в которые ведут дуги из очередной пограничной вершины в еще не просмотренные вершины.
Сам путь из начальной вершины в конечную будет сохраняться с помощью массива меток backs. Алгоритм заканчивает работу, как только в качестве пограничной будет выбрана конечная вершина или, если окажется, что очередная пограничная вершина вообще не связана с начальной (находится на бесконечно большом расстоянии от нее). Это расстояние задается в программе константой infinity.
Реализация этого алгоритма приведена в листинге в виде метода getDijkstraPath класса ListGraph. В качестве аргументов методу передаются номера начальной и конечной вершин на кратчайшем пути, а также переменная, которая будет содержать вектор номеров промежуточных вершин на пути из начальной вершины в конечную. Результатом работы метода будет суммарная длина кратчайшего пути.
Чтобы задать нагрузку на дуги, не изменяя представления графа, введем специальный абстрактный тип данных Graphweight, представляющий объекты, задающие нагрузку на дуги графа. Главным методом соответствующего класса будет функция arcLength, которая по заданным номерам вершин определяет длину дуги, соединяющей эти вершины. Значение функции будем считать неопределенным, если заданные вершины не соединены никакой дугой или вообще не задают номеров вершин графа. Чтобы задать конкретную нагрузку на граф, необходимо определить реализацию абстрактного типа данных GraphWeight.
Листинг : Алгоритм определения кратчайшего пути Э. Дейкстры с учетом длин дуг
double ListGraph: :getDijkstraPath (int beg, int end,
const GraphWeight & weights, vector<int> & path) const
{
path.clear();
// Множество непросмотренных вершин:
Set notPassed(0, vertexCount()-1);
notPassed.addScale(0, vertexCount()-1);
// Массив обратных меток
int *backs = new int[vertexCount()];
// Массив минимальных расстояний. В начале работы все расстояния
// бесконечно большие, кроме расстояния до исходной вершины
double *dist = new double[vertexCount()];
for (int i = 0; i < vertexCount(); i++)
dist[i] = INFINITY;
dist[beg] = 0;
// Цикл поиска и обработки пограничной вершины
while(!notPassed.empty())
{
// Поиск пограничной вершины: просматриваем массив dist
// в поисках вершины с минимальным расстоянием от beg
int border = -1;
double minDist = INFINITY;
Iterator<int> *check = notPassed.iterator();
while(check->hasMoreElements()) {
int next = **check;
if (dist[next] < minDist) { minDist = dist[border = next];
}
++*check;
}
delete check;
// Если пограничная вершина не найдена, то пути нет
if (border == -1) return INFINITY;
// Если пограничная вершина совпала с конечной,
// то переходим к формированию результата
if (border == end) break;
// Обработка вершин, смежных с пограничной
notPassed -= border;
Iterator<int> *nextToBorder = graph[border].iterator();
while (nextToBorder->hasMoreElements())
{
int v = **nextToBorder;
if (notPassed.has(v) && dist[v] >
dist[border] + weights.arcLength(border, v)) {
backs[v] = border;
dist[v] = dist[border] + weights.arcLength(border, v);
}
++*nextToBorder;
}
delete nextToBorder;
}
// Формирование результирующего вектора
int current = end;
while(current != beg) {
path.insert(path.begin(), current);
current = backs[current];
}
path.insert(path.begin(), beg);
return dist[end];
}
Алгоритм Флойда — Уоршалла
Идея алгоритмом Флойда — Уоршалла, состоит в следующем. Будем рассматривать последовательность матриц смежности. В этой матрице элемент с индексами (i,j) равен +∞, если в графе нет ребра, ведущего из вершины i в вершину j. В противном случае элемент содержит длину ребра (расстояние) от вершины i к вершине j. Имея эту начальную матрицу в качестве матрицы G0, будем получать далее последовательность матриц G1, G2,Gn, используя формулу
Gk(i,j) = min(Gk-1(i,j), Gk-1(i,k-1) + Gk-1(k -1, j)) .
В этой формуле считается, что если вершины i и j не соединены дугой, то соответствующий элемент матрицы Gk(i,j) содержит бесконечно большое значение +∞, операции с которым подчиняются естественным правилам: для любого значения а (конечного или бесконечного) а + ∞ = ∞, min(a, ∞) = а.
Кроме матрицы длин кратчайших путей G надо получить еще и матрицу направлений D для того, чтобы можно было определить сами найденные кратчайшие пути. Ее можно получать сходным способом. В этой матрице элемент Dk(i,j) равен номеру начальной промежуточной вершины на кратчайшем пути из вершины i в вершину j, проходящему через промежуточные вершины из множества {0, 1,... k-1}. Ясно, что начальная матрица направлений D0 совпадает с исходной матрицей смежности графа, в которой элемент с индексами (i,j) содержит значение j, если имеется ребро, ведущее из вершины i в вершину j, и содержит -1, если такого ребра нет. В дальнейшем, при вычислении матрицы кратчайших путей, как только обнаруживается, что элемент Gk(i,j) следует заменить суммой Gk-1(i,k-1) + Gk-1(k -1, j), элемент Dk(i,j) меняется на Dk-1(i,k-1). Таким образом, в конце концов в матрице Dn будут содержаться направления по всем кратчайшим путям между всеми парами вершин в исходном графе.
Итак, имеем алгоритм, реализованный в виде функции getMinPaths. Этот метод получает в качестве аргументов исходный граф G, нагрузку на его дуги, представленную объектом класса Graphweight, и две переменные, в которые в процессе работы алгоритма и будут записаны значения элементов матрицы кратчайших путей и матрицы направлений.
Листинг : Алгоритм нахождения матрицы кратчайших путей и матрицы направлений методом Флойда — Уоршалла
void getMinPaths(const MatrixGraph & G, // Исходный граф
const GraphWeight & w, // Нагрузка на дуги
double ** & P, // Переменные для матрицы путей
int ** & D // ...и для матрицы направлений
) {
int n = G.vertexCount(); // Число вершин графа
// Инициализация матриц.
// В матрицу длин путей записываются длины дуг исходного графа:
Р = new double*[n];
for (int i = 0; i < n; i++) {
double * row = P[i] = new double[n];
for (int j = 0; j < n; j++) { row[j] = w.arcLength(i, j);
}
}
//В матрицу направлений записывается информация о направлениях
// дуг исходного графа (-1, если направление не определено):
D = new int*[n]; for (int i = 0; i < n; i++) {
int * row = D[i] = new int[n];
for (int j = 0; j < n; j++) {
row[j] = (G.hasArc(i, j) ? j : -1);
}
}
// Вычисление кратчайших путей и направлений
//по алгоритму Флойда — Уоршалла
for (int k = 1; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != k-1 && P[i][k-1] < INFINITY && P[k-l][j] < INFINITY P[i] [j] > P[i] [k-1] + P[k-1] [j]) {
P[i][j] = P[i][k-1] + P[k-1][j];
D[i][j] = D[i][k-1];
}}}}}
Определение остовных деревьев
Остовиым деревом (скелетом) неориентированного графа называется его подграф, не имеющий циклов и содержащий все вершины исходного графа. Так, например, для нагруженного графа, изображенного на рис. 9, а, скелетами являются все его подграфы, изображенные на рис. 9, б.
Рис. 9. Нагруженный неориентированный граф и его остовные поддеревья
Строго говоря, то, что изображено на рис. 9, б, не является деревом, поэтому следовало бы говорить не об остовном дереве, а, скорее, об остовном лесе. Тем не менее в дальнейшем мы не будем уточнять, идет ли речь об одном или нескольких деревьях, представляющих остов графа.
Варианты скелетов исходного графа, изображенные на рис. 9, б, имеют различный суммарный вес ребер графа. В первом варианте сумма весов ребер скелета равна 15, во втором варианте— 27, и в третьем варианте— 19. В разных ситуациях бывает необходимо найти остовное дерево с максимальным или минимальным общим весом ребер. Так первое поддерево имеет минимальный суммарный вес из всех возможных поддеревьев. Второе поддерево— максимальный. Поставим задачу найти минимальное остовное дерево (т. е. остовное дерево минимального суммарного веса ребер) для заданного неориентированного графа. Разумеется, поиск максимального остовного дерева будет производиться по точно такому же алгоритму.
Первый из предлагаемых алгоритмов принадлежит классу так называемых жадных алгоритмов. Этот алгоритм пытается найти решение поставленной задачи в лоб, стараясь найти минимальное остовное дерево последовательным отбором ребер с минимальным весом, следя за тем, чтобы получающийся граф не имел циклов. Разумеется, для этого необходимо сначала отсортировать все ребра графа по возрастанию их весов. Лучше всего, если граф с самого начала представлен списком ребер, в этом случае сортировка будет наиболее естественной. Но даже и в других случаях сортировка ребер графа по весу занимает не слишком много времени— в худшем случае M x log2M, где М— количество ребер графа.
Подходящим способом сортировки ребер будет организация списка ребер в виде пирамиды — в этом случае сортировку можно совместить во времени с основной работой алгоритма. После того как ребра будут выстроены в упорядоченный список или в пирамиду, жадный алгоритм выбирает ребра по очереди, начиная с ребер с наименьшим весом, и пытается включить каждое очередное ребро в строящееся дерево. Очередное ребро не удается включить в дерево, если оно замыкает какой-либо цикл в графе. Проверить этот факт можно, если удастся выяснить, принадлежат ли оба конца очередного ребра уже построенной части остовного дерева. Отсюда следует следующий алгоритм, называемый также алгоритмом Крускала (J. В. Kruskal).
После сортировки ребер по весу строящееся остовное дерево организуется в виде отдельных фрагментов этого дерева, в которые в каждый момент времени включены все вершины графа. В начале работы каждая вершина графа представляет собой отдельную компоненту, а соединяющих их ребер пока вообще нет. Каждое вновь включаемое ребро соединяет две отдельные компоненты в одну, таким образом, полное остовное дерево будет построено после N-1 включения ребра. Разумеется, очередное ребро можно включить в дерево, только если его концы принадлежат разным компонентам, в противном случае в компоненте образуется цикл. Таким образом, если очередное ребро соединяет вершины, принадлежащие одной связной компоненте, то такое ребро не включается в строящееся остовное дерево и игнорируется
Рис. 10. а. Алгоритм Крускала построения минимального остовного дерева графа
Рис. 10. б. Алгоритм Крускала построения минимального остовного дерева графа
Для хранения информации о компонентах строящегося дерева предлагается структура данных в виде массива, каждый i-й элемент которого содержит ссылку на одну из вершин компоненты, содержащей i-ю вершину. Фактически такой массив является одним из способов представления дерева компонент (точнее, леса из нескольких деревьев), в котором ссылки из узлов дерева проводятся от потомков к предкам.
На рис. 10.б представлена последовательность этапов при построении компонент остовного дерева согласно жадному алгоритму. В качестве исходного графа выбран граф рис. 10.а. Первоначально остовное дерево состоит из отдельных вершин исходного графа, жадный алгоритм постепенно добавляет к нему ребра, начиная с ребер с наименьшим весом. На рис. 10.б показаны 8 последовательных этапов построения остовного дерева согласно жадному алгоритму. На каждом этапе в остовное дерево включается новое ребро. Ребра, замыкающие цикл в уже построенной части, игнорируются алгоритмом.
В листинге показана реализация алгоритма Крускала построения минимального остовного дерева. Метод minSkeieton графа получает в качестве аргумента выходной поток для печати в него информации о ребрах графа, включаемых в остовное дерево. Второй аргумент— это объект, задающий нагрузку на ребра графа. Информация о структуре минимального остовного дерева выводится в выходной поток в виде последовательности пар целых чисел — номеров вершин, задающих ребра графа, а общий полученный вес этого остовного дерева выдается в качестве результата работы функции.
На первом этапе работы алгоритма строится пирамида из ребер графа. В каждый узел пирамиды заносится информация о номерах соединяемых этим ребром вершин и о весе ребра. Информация о ребрах графа берется из матрицы смежности графа и объекта класса GraphWeight, задающего нагрузку на ребра.
На втором этапе начинается построение остовного дерева, информация о котором хранится в массиве. Каждый раз, как только очередное ребро попадает в остовное дерево, информация о нем выводится в выходной поток.
Листинг: Реализация алгоритма Крускала построения минимального остовного дерева
Файл listgraph.h
// Класс ListGraph задает структуру L-графа
class ListGraph {
// Массив списков дуг
List<int> *graph;
// Количество вершин графа
int vertexNumber;
public :
// Конструктор создает массив пустых списков
ListGraph(int n) : vertexNumber(n), graph(new List<int>[n]) {}
// Деструктор уничтожает списки дуг
~ListGraph() { delete [] graph; }
// Функция подсчета числа вершин просто выдает
// ранее сохраненное значение
int vertexCount() const {return vertexNumber; }
// Основные методы работы с графом
void addArc(int from, int to);
bool hasArc(int from, int to) const;
// Алгоритм Крускала нахождения минимального остовного дерева
double minSkeleton(std:rostream & out, const GraphWeight & gw);
};
Файл Arc.h
// Структура ребра для алгоритма Крускала: сравнение ребер
// происходит по их весам
struct Arc {
int from, to;
double weight;
Arc(int from = 0, int to = 0, double weight = 0)
: from(from), to(to), weight(weight) {}
Arc(const Arc & arc)
: from(arc.from), to (arc.to), weight(arc.weight) {}
Arc & operator = {const Arc & arc) {
from - arc.from; to - arc.to; weight = arc.weight;
}
bool operator < (const Arc & arc) { return weight < arc.weight; }
bool operator <= (const Arc & arc) { return weight <= arc.weight; }
bool operator > (const Arc & arc) { return weight > arc.weight; }
bool operator >= (const Arc & arc) { return weight >= arc.weight; }
bool operator == (const Arc & arc) { return weight == arc.weight; }
bool operator != (const Arc & arc) { return weight != arc.weight; }
std::ostream & operator « (std::ostream & out, const Arc & arc);
Файл listgraph.cpp
// Собственно алгоритм Крускала
double ListGraph::minSkeleton(
// Выходной поток для вывода результирующей информации:
std::ostream & out,
// Нагрузка на ребра графа:
const GraphWeight & gw) {
// Суммарный вес найденного минимального остовного дерева:
double weight = 0;
// Пирамида, содержащая информацию о ребрах графа:
ArrayHeap<Arc> arcs(vertexNumber * vertexNumber / 2);
// Структура узла в лесе, представляющем частично построенное
// минимальное остовное дерево
struct SkeletonNode {
int node; // номер узла исходного графа
int next; // ссылка на родительский узел
// Конструкторы:
SkeletonNode(int n = 0) : node(n), next(-l) {}
SkeletonNode(const SkeletonNode & node) : node(node.node), next(node.next) {}
};
// Начальное заполнение пирамиды ребер:
// просматриваются все ребра графа,
//и информация о них заносится в пирамиду,
for (int i = 0; i < vertexNumber; i++) {
Iterator<int> *neighbors = graph[i].iterator();
while (neighbors->hasMoreElements()) {
int j = **neighbors;
}
// Граф неориентированный, поэтому для исключения дублирования
// информации рассматриваются только дуги, ведущие из вершины
// с меньшим номером в вершину с большим номером. Петли
// (если они есть) сразу же исключаются,
if (i < j) {
// Добавление ребра в пирамиду:
arcs += Arc(i, j, gw.arcLength(i, j));
}
++*neighbors;
}
delete neighbors;
// Начальное заполнение леса: каждая вершина графа представляет
// собой отдельное дерево, состоящее из единственной вершины.
SkeletonNode skeleton[vertexNumber];
for (int i = 0; i < vertexNumber; i++) {
skeleton[i] = SkeletonNode(i);
}
// Основной цикл по ребрам, включенным в пирамиду
while (!arcs.empty()) {
// Очередное ребро берется с вершины пирамида и исключается из нее
Arc nextArc = *arcs;
arcs, remove ();
// u и v - концы выбранного ребра
int u = nextArc. from, v = nextArc.to;
// Следующие два цикла находят корни деревьев,
// содержащих эти вершины:
while(skeleton[u].next ! = -1) u = skeleton[u].next;
while(skeleton[v].next != -1) v = skeleton[v].next;
if (u != v) {
// Ребро включается в остовное дерево,...
out « nextArc « "; ";
weight += nextArc.weight;
// ... а два дерева соединяются в одно.
skeleton[u]-next = v;
}
return weight;
}
При попытке вычислить минимальное остовное дерево для графа, приведенное на рис. 9, с помощью вызова метода:
cout « testGraph.minSkeleton(cout, arcsWeight);
В стандартный выходной поток будет выведена следующая информация:
(2,5); (0,3); (5,8); (0,6); (0,1); (1,4); (4,7); 15
Что и свидетельствует о том, что минимальное остовное дерево построено правильно, поскольку содержит ребра (2, 5), (0, 3), (5, 8), (0, б), (0, 1), (1, 4), (4, 7) и суммарный вес всех ребер составляет минимально возможную величину 15.
Еще один алгоритм построения минимального остовного дерева напоминает алгоритм Дейкстры для поиска наименьшего пути между двумя вершинами в графе и носит название алгоритма Прима (R. С. Prim).
В этом алгоритме построение остовного дерева начинается с одной вершины, к которой затем добавляются ребра таким образом, чтобы каждое новое ребро одним своим концом опиралось в уже построенную часть дерева, а другой конец лежал бы в множестве еще не присоединенных к дереву вершин. Из всех таких ребер на каждом шаге выбирается ребро с наименьшим весом. Для того чтобы выбор ребра был бы наиболее эффективен, так же, как и в алгоритме Дейкстры, в алгоритме Прима используется промежуточная структура данных — массив, элементы которого содержат информацию о расстоянии от каждой из вершин до уже построенной части остовного дерева. Таким образом, с помощью однократного просмотра такого массива всегда можно выбрать ребро минимальной длины.
Будем считать, что вершины, не соединенные ребрами с уже построенной частью остовного дерева, находятся от этой части на бесконечно большом расстоянии. После того как очередная вершина будет выбрана и присоединена к остовному дереву, все инцидентные ей ребра просматриваются, чтобы скорректировать информацию о расстояниях. Эта часть алгоритма также очень похожа на соответствующую коррекцию массива расстоянии из алгоритма Дейкстры. Если оказывается, что очередная выбранная вершина находится на бесконечно большом расстоянии от уже построенной части дерева, то это означает, что завершено построение дерева для одной компоненты связности графа и, значит, одного остовного дерева для графа построить невозможно (в этом последнем случае стоит говорить об остовном лесе).
Если для графа, изображенного на рис. 9, начать поиск минимального остовного дерева с вершины 0, то к дереву будут последовательно присоединяться ребра 0—3 (длиной 1), 0—1 (2), 0—6 (2), 1—4 (3), 4—7 (4), вершина 2 (+∞), 2—5(1), 2—8 (2).
На рис. 11 показана последовательность построения минимального остовного дерева для графа, изображенного на рис. 9.
Реализация алгоритма Прима показана в листинге в виде определения метода minSkeletonPrim, который так же, как и метод minSkeleton, в качестве аргумента получает выходной поток для печати информации о найденных ребрах минимального остовного дерева, а в качестве результата выдает суммарный вес полученного остовного дерева.
Листинг : Алгоритм Прима нахождения минимального остовного дерева
double ListGraph::minSkeletonPrim(
// Выходной поток для вывода результирующей информации:
std::ostream & out,
// Нагрузка на ребра графа:
const GraphWeight & gw) {
// Множество непройденных вершин (сначала - все вершины)
Set notPassed(0, vertexNumber-1);
notPassed.addScale(0, vertexNumber-1);
// Массив расстояний от вершин до уже построенной части
double *dist - new double[vertexNumber];
// Массив направлений от новых вершин к уже построенной части
double *ends = new double[vertexNumber];
// Инициализация массивов расстояний и направлений
for (int i = 0; i < vertexNumber; i++) {
dist[i] = INFINITY;
ends[i] = -1;
}
// Суммарный вес построенной части дерева
double sumWeight =0;
// Основной цикл поиска новых вершин
while (!notPassed.empty()) {
// Поиск ближайшей вершины
double minDist = INFINITY;
Iterator<int> *iVertices = notPassed.iterator();
int minVertex = **iVertices;
while (iVertices->hasMoreElements()) {
int nextVertex = **iVertices;
if (dist[nextVertex] < minDist) {
minDist = dist[nextVertex];
minVertex = nextVertex;
} ++*iVertices; }
delete iVertices;
if (dist[minVertex] < INFINITY) {
// Присоединяем очередное ребро
out << "(" << ends[minVertex] << "," << minVertex <<”);”;
sumWeight += minDist;
}
notPassed -= minVertex;
// Новая вершина присоединена;
// корректируем информацию о расстояниях
Iterator<int> *neighbors = graph[minVertex].iterator();
while (neighbors->hasMoreElements()) {
int next = **neighbors;
if (notPassed.has(next)&& gw.arcLength(minVertex, next) < dist[next]) {
dist[next] = gw.arcLength(minVertex, next);
ends[next] = minVertex;
} ++*neighbors;
} delete neighbors;
} return sumWeight;
}
Рис. 11. Этапы построения остовного дерева согласно алгоритму Прима
Если применить метод minSkeietonPrim к графу, изображенному на рис. 9
cout « testGraph.minSkeleton(cout, arcsWeight);
то, разумеется, результат будет примерно тем же самым, что и при применении метода minskeieton, реализующего жадный алгоритм:
(0,3); (0,1); (0,6); (1,4); (4,7); (2,5); (2,8); 15
Алгоритмы имеют разную производительность на различных графах. Скорость работы алгоритма Крускала зависит, прежде всего, от количества ребер в графе и слабо зависит от количества вершин. Напротив, скорость работы алгоритма Прима определяется количеством вершин и слабо зависит от числа ребер. Следовательно, алгоритм Крускала следует применять в случае неплотных или разреженных графов, у которых количество ребер мало по сравнению с количеством ребер у полного графа. Если известно, что ребер в графе достаточно много, то для поиска минимального остовного дерева лучше применять алгоритм Прима.
Контрольные вопросы
- Основные понятия теории графов
- Перечислите алгоритмы представления графа
- Особенности представления графа в виде массива
- Особенности представления графа в виде матрицы смежности
- Особенности представления графа в виде связанного списка
- Особенности представления графа в виде списка дуг
- Особенности преобразования структур графа
- Реализация обходов в графах
- Определение путей и контуров Эйлера
- Поиск кратчайших путей методом Дейкстры
- Поиск кратчайших путей методом Флойда-Уоршала
- Определение остовных деревьев методом Крускала
- Определение остовных деревьев методом Прима
Задания для практической работы
Выберите граф и выполните следующие операции:
- представить граф в виде массива;
- представить граф в виде матрицы смежности;
- представить граф в виде связанного списка;
- представить граф в виде списка дуг;
- предусмотреть возможность преобразования структур графа;
- реализовать обход графа в глубину и ширину;
- определить если имеются путь и контур Эйлера;
- реализовать поиск кратчайшего пути методом Дейкстры и методом Флойда-Уоршала. Провести сравнительные характкристики;
- определить минимальноем остовное дерево методом Крускала и методом Прима. Провести сравнительные характкристики.
1. 2.
3. 4.
5. 6.
7. 8.
9. 10.
11. 12.
13. 14.
16.
15.
Жадные алгоритмы
Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская что конечное решение также окажется оптимальным.
Общего критерия оценки применимости жадного алгоритма для решения конкретной задачи не существует, однако, для задач, решаемых жадными алгоритмами характерны две особенности:
во-первых, к ним применим Принцип жадного выбора ;
во-вторых, они обладают свойством Оптимальности для подзадач.
Принцип жадного выбора
Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных выборов даёт глобально оптимальное решение. В типичном случае доказательство оптимальности следует такой схеме: Сначала доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадный выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.
Свойство оптимальности для подзадач
Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в задаче о выборе заявок можно заметить, что если A — оптимальный набор заявок, содержащий заявку номер 1, то — оптимальный набор заявок для меньшего множества заявок , состоящего из тех заявок, для которых .
Пример: Размен монет
Задача. Монетная система некоторого государства состоит из монет достоинством a1 = 1 < a2 < ... < an. Требуется выдать сумму S наименьшим возможным количеством монет.
Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства an: . Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.
Для данной задачи жадный алгоритм не всегда даёт оптимальное решение. Например, сумму в 10 копеек монетами в 1, 5 и 6 коп. жадный алгоритм разменивает так: 6 коп. — 1 шт., 1 коп. — 4 шт., в то время как правильное решение — 2 монеты по 5 копеек. Тем не менее, на всех реальных монетных системах жадный алгоритм даёт правильный ответ.
Алгоритм Хаффмана (англ. Huffman) — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. Коды Хаффмана широко используются при сжатия информации (в типичной ситуации выигрыш может составить от 20% до 90% в зависимости от тина файла). Алгоритм Хаффмана находит оптимальные коды символов (исходя из частоты использования этих символов в сжимаемом тексте) с помощью жадного выбора.
Пусть в файле длины 100 000 известны частоты символов.
Мы хотим построить двоичный код, в котором каждый символ представляется в виде конечной последовательности битов, называемой кодовым словом.
|
а |
b |
с |
d |
е |
f |
|
|
Количество (в тысячах) |
45 |
13 |
12 |
16 |
9 |
5 |
|
Равномерный код |
000 |
001 |
010 |
011 |
100 |
101 |
|
Неравномерный код |
0 |
101 |
100 |
111 |
1101 |
1100 |
При использовании равномерного кода, в котором все кодовые слова имеют одинаковую длину, на каждый символ (из шести имеющихся) надо потратить как минимум три бита, например, а — 000, b — 001,.. .,f — 101. На весь файл уйдет 300 000 битов .
Рис.1. Представление равномерного кода в виде дерева.
Неравномерный код будет экономнее, если часто встречающиеся символы закодировать короткими последовательностями битов, а редко встречающиеся длинными.
Рис.2. Представление неравномерного кода в виде дерева.
. Один такой код показан на рис.2: буква а изображается однобитовой последовательностью 0, а буква f четырёхбитовой последовательностью 1 100. При такой кодировке на весь файл уйдёт (45- 1 + 13-3+ 12-3+ 16-3 + 9-1 +5-1) * 1000 = 221000 битов, что даёт около 25% экономии.
Этот метод кодирования состоит из двух основных этапов:
- Построение оптимального кодового дерева.
- Построение отображения код-символ на основе построенного дерева.
Общая схема построения дерева Хаффмана (рис.3):
- Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).
- Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа — чем чаще используется, тем больше весит).
- Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.
- Добавим сформированный узел к списку.
- Если в списке больше одного узла, то повторить 2-5.
Рис.3. Этапы построения дерева Хаффмана
Контрольные вопросы
- В чем принцип работы жадного алгоритма?
- Какие типы задач можно решать с помощью жадного алгоритма?
- Что понимается под методом Хаффмана?
- Где применяется метод Хаффмана?
- Как строится дерево Хаффмана?
- Как вычислить размер исходного текста и сжатого?
Задания для практической работы
Задание состоит из нескольких этапов:
- Получить у преподавателя индивидуальный текст для сжатия.
- Создать программный модуль, который
- из исходного текста получает список кодируемых символов;
- Рассчитать размер несжатого файла;
- С учетом полученных вероятностей, построить дерево Хаффмана;
- Рассчитать размер сжатого файла.
- Провести сравнительный анализ сжатия при разных характеристика исходного файла.
Алгоритмы сортировок
Сортировка выбором
Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве. Далее, находится второй наименьший элемент и меняется местами с элементом, стоящим вторым в исходном массиве. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.
Изложенный метод называется сортировкой выбором, поскольку он работает по принципу выбора наименьшего элемента из числа неотсортированных. На рис. 1 представлен пример работы этого метода.
|
A |
S |
O |
R |
T |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
S |
O |
R |
T |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
A |
O |
R |
T |
I |
N |
G |
E |
X |
S |
M |
P |
L |
E |
|
A |
A |
E |
R |
T |
I |
N |
G |
O |
X |
S |
M |
P |
L |
E |
|
A |
A |
E |
R |
T |
I |
N |
G |
O |
X |
S |
M |
P |
L |
E |
|
A |
A |
E |
E |
T |
I |
N |
G |
O |
X |
S |
M |
P |
L |
R |
|
A |
A |
E |
E |
G |
I |
N |
T |
O |
X |
S |
M |
P |
L |
R |
|
A |
A |
E |
E |
G |
I |
N |
T |
O |
X |
S |
M |
P |
L |
R |
|
A |
A |
E |
E |
G |
I |
L |
T |
O |
X |
S |
M |
P |
N |
R |
|
A |
A |
E |
E |
G |
I |
L |
M |
O |
X |
S |
T |
P |
N |
R |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
X |
S |
T |
P |
O |
R |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
O |
S |
T |
P |
X |
R |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
O |
P |
T |
S |
X |
R |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
O |
P |
R |
S |
X |
T |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
O |
P |
R |
S |
X |
T |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
O |
P |
R |
S |
T |
X |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
O |
P |
R |
S |
T |
X |
Рис.1. Пример работа сортировки выбором
В этом примере первый проход не дал результата, поскольку слева от А в массиве нет элемента, меньшего А. На втором проходе другой элемент А оказался наименьшим среди оставшихся, поэтому он меняется местами с элементом S, занимающим вторую позицию. Далее, на третьем проходе, элемент Е, находящийся в середине массива, меняется местами с О, занимающим третью позицию; затем, на четвертом проходе, еще один элемент Е меняется местами с R, занимающим четвертую позицию и т.д.
Для каждого i от I до г-1 поменять местами элемент a[i] с минимальным элементом в последовательности a[i],...,a[r],. По мере продвижения индекса i слева направо, элементы слева от него занимают свои окончательные позиции в массиве (дальнейшим перемещениям они не подлежат), таким образом, массив будет полностью отсортирован, когда i достигнет его правого конца.
Недостаток сортировки выбором заключается в том, что время ее выполнения лишь в малой степени зависит от того, насколько упорядочен исходный массив. Процесс нахождения минимального элемента за один проход массив дает очень мало сведений о том, где может находиться минимальный элемент на следующем проходе этого массива. На сортировку почти отсортированного массива требуется столько же времени, сколько и на сортировку массива, упорядоченного случайным образом!
Сортировка вставками
Метод сортировки заключается в том, что отдельно анализируется каждый конкретный элемент, который затем помещается в надлежащее место среди других, уже отсортированных элементов. Следует позаботиться о том, чтобы освободить место для вставляемого элемента путем смещения больших элементов на одну позицию вправо, после чего на освободившееся место помещается вставляемый элемент.
Как и в случае сортировки выбором, элементы, находящиеся слева от текущего индекса, отсортированы в соответствующем порядке, тем не менее, они еще не занимают свои окончательные позиции, ибо могут быть передвинуты с целью освобождения места под меньшие элементы, которые обнаруживаются позже. Массив будет полностью отсортирован, когда индекс достигнет правой границы массива.
|
A |
S |
O |
R |
T |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
S |
O |
R |
T |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
O |
S |
R |
T |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
O |
R |
S |
T |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
O |
R |
S |
T |
I |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
I |
O |
R |
S |
T |
N |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
I |
N |
O |
R |
S |
T |
G |
E |
X |
A |
M |
P |
L |
E |
|
A |
G |
I |
N |
O |
R |
S |
T |
E |
X |
A |
M |
P |
L |
E |
|
A |
E |
G |
I |
N |
O |
R |
S |
T |
X |
A |
M |
P |
L |
E |
|
A |
E |
G |
I |
N |
O |
R |
S |
T |
X |
A |
M |
P |
L |
E |
|
A |
A |
E |
G |
I |
N |
O |
R |
S |
T |
X |
M |
P |
L |
E |
|
A |
A |
E |
G |
I |
M |
N |
O |
R |
S |
T |
X |
P |
L |
E |
|
A |
A |
E |
G |
I |
M |
N |
O |
P |
R |
S |
T |
X |
L |
E |
|
A |
A |
E |
G |
I |
L |
M |
N |
O |
P |
R |
S |
T |
X |
E |
|
A |
A |
E |
E |
G |
I |
L |
M |
N |
O |
P |
R |
S |
T |
X |
Во время первого прохода сортировки вставками элемент S, занимающий вторую позицию, больше А, так что трогать его не надо. На втором проходе, когда в третьей позиции встречается элемент О, он меняется местами с S, так что последовательность становится АО S отсортированной и т.д.
Пузырьковая сортировка
Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по массиву с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока массив не будет окончательно отсортирован.
Предположим, что мы всегда передвигаемся по массиву справа налево. Если удается обнаружить минимальный элемент на первом проходе, он меняется местами с каждым элементом, стоящим от него слева, и, в конце концов, этот элемент помещается в позицию на левой границе массива. Затем на втором проходе в соответствующую позицию устанавливается второй по величине элемент и т.д. Таким образом, вполне достаточно выполнить N проходов, т.е., пузырьковую сортировку можно рассматривать как один из видов сортировки выбором, хотя при этом для помещения каждого элемента в соответствующую позицию приходится выполнять больший объем действий. В общем случае пузырьковый метод обладает несколько меньшим быстродействием.
В процессе пузырьковой сортировки элементы с малыми значениями устремляются влево. Поскольку сортировка производится в направлении справа налево, каждый элемент меняется местами с элементом слева до тех пор, пока не будет обнаружен элемент с меньшим значением. На первом проходе Е меняется местами с L, Ри М, пока не остановится справа от А; далее уже А продвигается к началу массива, пока не остановится перед другим А, который уже занимает окончательную позицию, i-й по величине элемент устанавливается в свое окончательное положение после i-ого прохода, как и в случае сортировки выбором, но при этом и другие элементы также приближаются к своим окончательным позициям.
Быстрая сортировка
Алгоритм быстрой сортировки обладает привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего лишь небольшого вспомогательного стека), на выполнение сортировки N элементов в среднем затрачивается время, пропорциональное N log N и для него характерны исключительно короткие внутренний циклы.
Его недостатком является то, что он неустойчив, для его выполнения в наихудшем случае требуется N2 операций, он хрупок в том смысле, что даже простая ошибка в реализации может пройти незамеченной и вызвать ошибки в работе алгоритма на некоторых видах массивов.
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". Он делит сортируемый массив на две части, затем сортирует эти части независимо друг от друга. Суть метода заключается в процессе разбиения массива, который переупорядочивает массив таким образом, что выполняются следующие условия:
Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.
Ни один из элементов a[i],..., a[i-l] не превышает a[i].
Ни один из элементов a[i+l],..., а[г] не является меньшим a[i].
Быстрая сортировка представляет собой рекурсивный процесс разбиения массива на части: мы разбиваем его, помещая некоторый (разделяющий) элемент в свою окончательную позицию и выполняем перегруппировку массива таким образом, что элементы, меньшие по значению, остаются слева от разделяющего элемента, а элементы, большие по значению, — справа. Далее мы рекурсивно сортируем левую и правую части массива. Конечным результатом такого вида сортировки является полностью отсортированный массив.
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а[r], лучше чтобы r был ближе к середине — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Мы продолжаем дальше в том же духе, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.
Листинг: Алгоритм быстрой сортировки
// Шаблон quicksort задает рекурсивную функцию сортировки
// элементов массива методом быстрой сортировки.
// - Key - класс, задающий тип элементов массива;
// - array - упорядочиваемый массив;
// -.low, high - индексы, задающие диапазон сортировки.
template <class Кеу>
void quicksort(Key * array, int low, int high) {
// Предполагается, что в начале работы low <= high
// В результате сортировки получается упорядоченный фрагмент
// массива в диапазоне от low до high
int pLow = low,
pHigh - high; // указатели концов фрагмента массива
Key elem = array[low]; // выбранный произвольный элемент
while (pLow != pHigh) {
// 1. Просмотр элементов массива снизу
while (pHigh > pLow && array[pHigh] >= elem) pHigh--;
if (pHigh > pLow) {
array[pLow] =array[pHigh]; // Обмен местами элементов
// 2. Просмотр элементов массива "сверху"
while (pLow < pHigh && array[pLow] <= elem) pLow++;
array[pHigh] = array [pLow]; // Еще один обмен
}
}
// Теперь указатели pLow и pHigh столкнулись, массив разделен,
array[pLow] = elem;
// Далее следуют рекурсивные вызовы функции для двух половинок
if (pLow - low > 1) quickSort<Key>(array, low, pLow-1);
if (high - pHigh > 1) quickSort<Key>(array, pHigh+1, high);
}
сортировка слиянием
Рассматривается сортировка слиянием (mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.
Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует массив, состоящий из N элементов, за время, пропорциональное NlogN, независимо от характера входных данных.
Сортировка слиянием — это устойчивая сортировка, и данное обстоятельство склоняет чашу весов в ее пользу в тех приложениях, в которых устойчивость имеет важное значение.
Другое свойство сортировки слиянием, которое приобретает важное значение в некоторых ситуациях, является тот факт, что сортировка слиянием обычно реализуется таким образом, что она осуществляет, в основном, последовательный доступ к данным (один элемент за другим).
Имея два упорядоченных входных массива, их можно объединить в один упорядоченный выходной массив просто отслеживая наименьший элемент в каждом массиве и входя в цикл, в котором меньший из двух элементов, наименьших в своих массивах, переносится в выходной массив; процесс продолжается до тех пор, пока оба входных массива не будут исчерпаны.
Листинг: Алгоритм сортировки слиянием
//-------------------------------------------------------------
// Шаблон move задает вспомогательную функцию, которая просто
// переносит элементы массива из одного фрагмента массива
// в другой фрагмент того же самого или другого массива.
// - Key - класс, задающий тип элементов массива;
// - src - исходный фрагмент массива;
// - sLow, sHigh - индексы, задающие диапазон в исходном массиве;
// - dst - результирующий фрагмент массива;
// - dLow - индекс, задающий нижнюю границу результирующего массива.
//-------------------------------------------------------------
template <class Кеу>
void move(Key * src, int sLow, int sHigh, Key * dst, int dLow) {
for (int pSrc = sLow, pDst = dLow; pSrc <= sHigh;) { dst[pDst++] = src[pSrc++];
}
}
//-------------------------------------------------------------
// Шаблон mergeSort задает функцию сортировки элементов
// массива методом последовательного слияния.
// - Key - класс, задающий тип элементов массива;
// - array - упорядочиваемый массив;
// - low, high - индексы, задающие диапазон сортировки.
//-------------------------------------------------------------
template <class Кеу>
void mergeSort(Key * array, int low, int high) {
// Предполагается, что в начале работы low <= high
// В результате сортировки получается упорядоченный фрагмент
// массива в диапазоне от low до high
int n = high - low +1; // Длина массива
int frag = n; // Число упорядоченных фрагментов
int len = 1; // Длина сливаемых фрагментов
Key * source = array, // Массив, из которого происходит слияние
* dest = new Key[n]; // Массив, в который происходит слияние
int sourceLow = low, // Нижняя граница индексов массива-источника
destLow = 0; // Нижняя граница индексов массива-назначения
while (frag > 1) {
// Один шаг цикла слияния состоит в попарном слиянии фрагментов
// исходного массива и переносе оставшихся неслитыми элементов
// из исходного массива в результирующий.
// Индексы pSource и pDest задают нижние границы этих массивов,
int pSource = sourceLow, pDest = destLow;
do {
int nextSource =min(pSource + 2*len, sourceLow + n);
// Выполняем слияние двух фрагментов или
// перенос последнего оставшегося фрагмента
if (nextSource > pSource + len) {
merge<Key>(source, pSource, pSource+len-1, source, pSource+len, nextSource-1, dest, pDest);
} else {
move<Key>(source, pSource, nextSource-1, dest, pDest);
}
pSource = nextSource;
pDest += 2*len; }
while (pSource < sourceLow+n);
len*= 2; // Длина фрагментов увеличивается вдвое
frag = (frag+l)/2; // Число фрагментов уменьшается вдвое
// Переставляем местами массивы источника и назначения:
Key * tempArray = dest; dest =source; source = tempArray;
int tempLow = destLow; destLow = sourceLow; sourceLow = tempLow;
}
// Если в конце работы результат оказался не на месте,
//то организуется его перенос в исходный массив
if (source != array) {
move<Key>(source, sourceLow, sourceLow+n-1, dest, destLow);
}
}
Пирамидальная сортировка
Итак, мы постепенно переходим от более-менее простых к сложным, но эффективным методам.
В качестве некоторой прелюдии к основному методу, рассмотрим перевернутую сортировку выбором. Во время прохода, вместо вставки наименьшего элемента в левый конец массива, будем выбирать наибольший элемент, а готовую последовательность строить в правом конце.
Пример действий для массива a[0]... a[7]:
44 55 12 42 94 18 06 67 исходный массив
44 55 12 42 67 18 06 |94 94 <-> 67
44 55 12 42 06 18 |67 94 67 <-> 06
44 18 12 42 06 |55 67 94 55 <-> 18
06 18 12 42 |44 55 67 94 44 <-> 06
06 18 12 |42 44 55 67 94 42 <-> 42
06 12 |18 42 44 55 67 94 18 <-> 12
06 |12 18 42 44 55 67 94 12 <-> 12
Вертикальной чертой отмечена левая граница уже отсортированной(правой) части массива.
Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором
- все узлы имеют глубину k или k-1 - дерево сбалансированное.
- при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид:
- выполняется "свойство пирамиды": каждый элемент меньше, либо равен родителю.
Как хранить пирамиду? Наименее хлопотно - поместить ее в массив.
|
Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме:
|
Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2].
Плюсы такого хранения пирамиды очевидны:
- никаких дополнительных переменных, нужно лишь понимать схему.
- узлы хранятся от вершины и далее вниз, уровень за уровнем.
- узлы одного уровня хранятся в массиве слева направо.
Запишем в виде массива пирамиду, изображенную выше.. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42. На рисунке место элемента пирамиды в массиве обозначено цифрой справа-вверху от него.
Восстановить пирамиду из массива как геометрический объект легко - достаточно вспомнить схему хранения и нарисовать, начиная от корня.
Фаза 1 сортировки: построение пирамиды
Hачать построение пирамиды можно с a[k]...a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i,j: i = 2i+1 ( или j = 2i+2 )... Просто потому, что такие i,j находятся за границей массива.
Следует заметить, что неправильно говорить о том, что a[k]..a[n] является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]...a[n].
Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления - тот, который стоит перед уже готовой частью.
Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]..a[n] на элемент a[i] влево:
- Смотрим на сыновей слева и справа - в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них.
- Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе конец процедуры.
Новый элемент "просеивается" сквозь пирамиду.
template<class T>
void downHeap(T a[], long k, long n) {
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
T new_elem;
long child;
new_elem = a[k];
while(k <= n/2) { // пока у a[k] есть дети
child = 2*k;
// выбираем большего сына
if( child < n && a[child] < a[child+1] )
child++;
if( new_elem >= a[child] ) break;
// иначе
a[k] = a[child]; // переносим сына наверх
k = child;
}
a[k] = new_elem;
}
Учитывая, что высота пирамиды h <= log n, downheap требует O(log n) времени. Полный код процедуры построения пирамиды будет иметь вид:
// вызвать downheap O(n) раз для преобразования массива в пирамиду целиком
for(i=size/2; i >= 0; i--) downHeap(a, i, size-1);
Ниже дана иллюстрация процесса для пирамиды из 8-и элементов:
44 55 12 42 // 94 18 06 67 Справа - часть массива, удовлетворяющая
44 55 12 // 67 94 18 06 42 свойству пирамиды,
44 55 // 18 67 94 12 06 42
44 // 94 18 67 55 12 06 42 остальные элементы добавляются
// 94 67 18 44 55 12 06 42 один за другим, справа налево.
В геометрической интерпретации ключи из начального отрезка a[size/2]...a[n] является листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так - пока не будет построена вся пирамида.
На рисунках ниже изображен процесс построения. Неготовая часть пирамиды (начало массива) окрашена в белый цвет, удовлетворяющий свойству пирамиды конец массива - в темный.
Фаза 2: собственно сортировка
Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:
- Берем верхний элемент пирамиды a[0]...a[n] (первый в массиве) и меняем с последним местами. Теперь "забываем" об этом элементе и далее рассматриваем массив a[0]...a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.
- Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.
Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.
94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы сортировки
67 55 44 06 42 18 12 // 94 во внутреннем представлении пирамиды
55 42 44 06 12 18 // 67 94
44 42 18 06 12 // 55 67 94
42 12 18 06 // 44 55 67 94
18 12 06 // 42 44 55 67 94
12 06 // 18 42 44 55 67 94
06 // 12 18 42 44 55 67 94
Код внешней процедуры сортировки:
template<class T>
void heapSort(T a[], long size) {
long i;
T temp;
// строим пирамиду
for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);
// теперь a[0]...a[size-1] пирамида
for(i=size-1; i > 0; i--) {
// меняем первый с последним
temp=a[i]; a[i]=a[0]; a[0]=temp;
// восстанавливаем пирамидальность a[0]...a[i-1]
downHeap(a, 0, i-1);
}
}
Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.
Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.
Пирамидальная сортировка не использует дополнительной памяти.
Метод не является устойчивым: по ходу работы массив так беребирается, что исходный порядок элементов может измениться случайным образом.
Поведение неестественно: частичная упорядоченность массива никак не учитывается.
Контрольные вопросы
- Опишите алгоритм работы сортировки методом выбора.
- Опишите алгоритм работы сортировки методом вставки.
- Опишите алгоритм работы сортировки методом пузырька.
- Опишите алгоритм работы быстрой сортировки.
- Опишите алгоритм работы сортировки слиянием.
- Опишите алгоритм работы пирамидальной сортировки.
- Какой из алгоритмов является более стабильным?
- Какой из алгоритмов сортировки быстродейственен?
Задания для практической работы
Реализовать все алгоритмы сортировки. Провести сравнительные характеристики работы алгоритмов при одинаковых входных параметрах. Протестировать работу всех сортировок, изменяя размерность входных данных.
Алгоритмы поиска
Введение
Некоторые алгоритмы поиска информации мы рассмотрели:
- Поиск первого подходящего в дереве на основе полного обхода{Error calculating value!: Bookmark "_Toc228245310" was not found in this document.}
- Поиск в дереве максимального (минимального) значения
- Поиск и включение в двоичное дерево
- Обходы в графах
В этой части мы рассмотрим алгоритмы поиска применяемые к массивам:
Для неупорядоченных массивов используются одни методы поиска, а для упорядоченных массивов используются другие методы поиска.
Последовательный поиск
Алгоритм последовательного поиска имеет очень простой вид: предполагая, что массив неотсортирован (неупорядочен), требуется проведения последовательного просмотра массива. Просмотр начинается с первого элемента и завершается либо найденным элементом, либо достижением конца массива При прямом последовательном поиске в среднем проверяются n/2 элементов. В лучшем случае будет проверяться только один элемент, а в худшем случае будут проверятся n элементов.
Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его значение больше значения требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.
Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел 1 2 3 4 5. Здесь средним элементом является 3. Это меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел 4 5. На следующем шаге нужный элемент будет найден. При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
Работа со словарем. Иоиск и вставка. Хеширование.
Довольно часто встречаются ситуации, когда обработке подлежат много маленьких строк — слов, которые надо сохранять в некоторой единой структуре — словаре. Сами слова не требуют для своего представления сложной структуры: для их представления вполне достаточно стандартных способов описания строк. Однако для словаря необходимо выбрать такое представление, которое бы обеспечило максимальную эффективность выполнения основной операции над словарем — поиска слова в словаре.
Самым простым представлением для словаря будет, конечно, массив слов. Для обеспечения эффективности поиска можно обеспечить упорядоченность элементов этого массива, тогда поиск слов можно производить с помощью алгоритма двоичного поиска, изученного ранее, который обеспечивает нахождение нужного слова среди множества из п слов за количество операций, пропорциональное log2 п. К сожалению, эффективность работы со словарем, организованным таким образом, резко снижается, когда требуется добавлять в него новые слова или удалять имеющиеся. Каждая вставка или удаление слова требуют сдвига в среднем около половины всех имеющихся в массиве слов. Кроме того, при вставке слов возникает проблема отведения новой памяти, если первоначально отведенной под словарь памяти не хватает для размещения новых элементов.
Одним из способов решения этой проблемы является использование так называемой функции расстановки или хеширования. Слово хеширование происходит от английского hash, означающего "крошить", "резать на кусочки", и отражает характер работы этой функции.
Основная идея применения функции расстановки состоит в следующем. Словарь будем представлять в виде массива слов, но помещать слова в него будем не в соответствии с алфавитным порядком, а в соответствии со значениями некоторой простой функции, вычисленной над словом. Такая функция — функция расстановки, — получая в качестве аргумента некоторое слово, выдает в качестве результата некоторое целое число — индекс в словаре, под которым следует хранить это слово. Если каждому слову будет соответствовать свое значение функции расстановки, то поиск в словаре становится ненужным. Вместо поиска осуществляется вычисление значения функции расстановки, после чего слово находится сразу же по вычисленному индексу.
К сожалению, на практике оказывается невозможным определить функцию расстановки так, чтобы каждому слову соответствовало свое уникальное значение индекса. Это приводит к тому, что два или более слов получают одно и то же значение функции расстановки. Говорят, что в этом случае происходит конфликт хеш-индексов (коллизия). Один из самых простых способов разрешения коллизий состоит в том, чтобы помещать слово, вызвавшее конфликт в один из соседних элементов массива. Тогда поиск и вставка новых слов будет производиться хотя и не за один шаг, но все же достаточно быстро.
Естественным требованием для функции расстановки будет требование простоты ее вычисления. Но это далеко не единственное, что требуется от хорошей функции расстановки. Прежде всего, надо обеспечить равномерное распределение вычисленных индексов слов в словаре.
Пусть функция code (с) по заданной букве выдает ее номер в латинском алфавите (если символ не является буквой латинского алфавита, то будем считать, что функция code возвращает значение 0). Вот как, например, может выглядеть эта функция:
int code(char c)
{
return strchr("abcdefghijklmnopqrstuvwxyz", c) + 1;
}
На самом деле, на практике обычно просто используют внутренний код каждого символа, так что фактически в использовании функции code нет необходимости.
Далее эту функцию можно использовать как базовую для определения функции расстановки. Прежде всего, обеспечим зависимость значения функции расстановки от всех символов слова. Для этого сложим коды всех букв. Дополнительно, для того чтобы позиция буквы в слове также играла некоторую роль, будем добавлять к коду каждой буквы номер ее позиции. Далее решим, словарь какого размера нам потребуется. В конечном итоге значение функции хеширования должно получиться достаточно равномерно распределенным на множестве всех обрабатываемых слов, и попадать в диапазон [0, n-1], где п — размер словаря. Достаточно равномерное распределение получается, если вычислять индекс по формуле (Р * Х+ Q) % n, где числа Р и Q — это некоторые простые числа, по порядку близкие к п, X— вычисленная сумма кодов букв слова, а символ % задает операцию вычисления остатка от целочисленного деления. Если, например, считать, что словаря в 1000 слов будет достаточно для наших целей, то можно выбрать для Р и Q значения 557 и 811, и тогда функция расстановки примет следующий вид:
int hash(const string & str) {
int sum = 0;
for (int i = 0; i < str.length(); i++) {
sum += code(str[i]) + i;
}
return (557 * sum + 811) % 1000;
}
Теперь можно задать словарь, в котором будет храниться некоторое множество слов. Мы определим функцию добавления слова в словарь и функцию, выясняющую, содержит ли словарь заданное слово. В обеих функциях слово (или место для этого слова) ищется схожим образом: по слову вычисляется значение функции расстановки, затем происходит перебор позиций слов в массиве, предназначенном для их хранения, до тех пор, пока либо искомое слово не будет найдено, либо не встретится пустое значение.
Если слова не удаляются из словаря, а только добавляются в него, то такой алгоритм поиска будет корректным, хотя при большой загруженности словаря поиск может осуществляться достаточно долго. В предельном случае, когда все позиции в словаре заняты, при поиске слова может оказаться необходимым перебрать все слова.
Листинг : Определение простого словаря
файл dictionary.h
// Класс, представляющий словарь в виде хеш-таблицы
class HashDictionary
{
private :
static const int P = 557;
static const int Q = 811;
static const int LENGTH = 1000;
string *dict[1000]; // хранилище на 1000 слов
// Функция определяет код буквы как ее
// порядковый номер в латинском алфавите
static int code(const char с);
public :
// Функция расстановки, основанная на сложении кодов
// букв со смещением, соответствующим их позиции
static int hash(const string & str);
private :
// Внутренняя функция поиска позиции слова в словаре
int findPos(const string & word) const;
public :
// Конструктор записывает в словарь пустые ссылки
HashDictionary() { memset(dict, 0, sizeof (dict)); }
//Функция добавления слова в словарь. Если слово уже было
// в словаре, то второй раз оно в словарь не попадает
void add(const string & word);
// Функция проверки наличия слова в словаре
bool hasWord(const string & word) const;
};
Файл dictionary.cpp
// Реализация функций
int HashDictionary::code(char c)
{
return strchr("abcdefghijklmnopqrstuvwxyz", c) + 1;
}
int HashDictionary::hash(const string & str) {
int sum =0;
for (int i = 0; i < str.length(); i++) {
sum += code(str[i]) + i;
}
return (P * sum + Q) % LENGTH;
}
int HashDictionary::findPos(const string & word) const {
int i = hash(word); // текущий индекс слова в словаре
for (int counter = 0;
counter < LENGTH; counter++)
{
if (dict[i] == NULL || *dict[i] — word) {
return i; // слово или позиция для его вставки найдено
} else if (++i — LENGTH) {
i = 0; // переход к следующему индексу
}} return -l; // перебраны все позиции в словаре!
}
void HashDictionary::add(const string & word) {
int i = findPos(word); // позиция слова в словаре
if (i==-1) return; // только в случае переполнения словаря!
if (dict[i] == NULL) dict[i] = new string();
*dict[i] = word; // добавление слова или его перезапись
}
bool HashDictionary::hasWord(const string & word) const {
int i = findPos(word); // позиция слова в словаре
return i !=1 && dict[i] != NULL; }
Обычно требуется хранить слова не сами по себе, а связывать с этими словами некоторую информацию, например количество этих слов в тексте, или другую информацию, зависящую от задачи. Так, например, если в компиляторе требуется организовать словарь из всех используемых в тексте программы идентификаторов, то с каждым идентификатором можно связать информацию о его типе, локализации и т. д. Поэтому чаще всего словари (которые еще называют хеш-таблицами) содержат не просто слова, а пары, в которых с каждым словом связан некоторый дополнительный объект. В этом случае слово, по которому происходит поиск, называют ключом поиска, а соответствующий объект — значением, связанным с этим ключом. По смыслу операции поиска в хеш-таблице каждый ключ находится в таблице в единственном экземпляре, однако несколько разных ключей могут иметь одно и то же значение функции расстановки.
В следующем листинге приведена реализация хеш-таблицы, в которой с каждым словом (ключом) связан некоторый объект, а конфликты разрешаются путем организации списков для каждого значения ключа. Сама функция расстановки несколько модифицирована и сделана более универсальной: в качестве кодов букв выбираются внутренние коды символов.
Листинг: Реализация хеш-таблицы
Файл "hashtable.h".
// Класс, представляющий хеш-таблицу пар (ключ, значение), причем
// ключом является строка, а значением может быть произвольный объект.
//В таблице хранятся не сами эти объекты, а ссылки на них.
template <class Object>
class HashTable {
private :
static const int P= 557;
static const int Q= 811;
static const int LENGTH = 1000;
// Элемент списка, содержащий ключ и связанный с ним объект
struct ListElem {
string key; // ключ
Object *obj; // связанный объект
ListElem *next; // ссылка на следующий элемент
// Простой конструктор для создания элементов списка
ListElem(const string & k, Object *o, ListElem *n) {
key = k; obj = o; next =n; }
};
// Массив списков, содержащих слова словаря
ListElem * diсt[LENGTH];
public :
// Конструктор
HashTable() { memset (dict, 0, sizeof (dict)); }
// Функция расстановки, основанная на сложении кодов символов
static int hash{const char * str);
// Функция добавления нового объекта по ключу. Если объект,
// связанный с этим ключом, уже содержится в словаре,
//то новый объект замещает собою старый, а старое значение
// возвращается в качестве результата работы функции.
Object * add(const char * key, Object * obj);
// Функция поиска объекта по ключу. Если ключ не найден,
//то функция возвращает пустую ссылку
Object * find(const char * key) const;
// Функция удаления объекта по заданному ключу.
// Результат функции - указатель на удаляемый объект.
// Если ключ не найден, то функция возвращает пустую ссылку
Object * remove(const char * key) ;
};
template <class Object>
int HashTable<Object>::hash(const char * str) {
int sum = 0;
for (int i = 0; str[i]; i++) {
sum += str[i] + i;
}
return ((P * sum + Q) & 0x7FFF) % LENGTH;
}
template <class Object>
Object * HashTable<Object>::add(const char * key, Object * obj) {
if (key == NULL || key[0] == 0 || obj == NULL) {
throw NullValueException();
}
int index - hash(key); // Значение hash-функции
ListElem *current =dict[index]; // Текущий элемент списка
// Поиск ключа в словаре:
while (current && key != current->key) {
current = current->next; }
Object * result = NULL;
if (current) { // Ключ уже есть в словаре
result = current->obj;
current->obj = obj;
} else {
// Создаем новый элемент списка и добавляем в начало списка
ListElem * newElem = new ListElem(key, obj, dict[index]);
dict[index] = newElem;
}return result;}
template <class Object>
Object * HashTable<Object>::find(const char * key) const {
if {key == NULL || key[0] == 0) {
throw NullValueException();
}
int index = hash(key); // Значение hash-функции
ListElem *current * dict[index]; // Текущий элемент списка
// Поиск ключа в словаре:
while (current && key !- current->key) {
current = current->next;
}
if (current == NULL) return NULL; // Ключ не найден
return current->obj;
}
template <class Object>
Object * HashTable<Object>::remove(const char * key) {
if (key == NULL || key[0] == 0) {
throw NullValueException();
}
int index = hash(key); // Значение hash-функции
ListElem *current = diсt[index]; // Текущий элемент списка
ListElem *pred = NULL; // Предыдущий элемент списка
// Поиск ключа в словаре:
while (current && key != current->key) {
pred = current;
current = current->next;
}
if (current = NULL) return NULL; // Ключ не найден
// Исключение элемента из списка:
if (pred == NULL) {
diсt[index] = current->next;
} else {
pred->next = current->next;
}
// Возврат результата:
Object * result = current->obj;
delete current;
return result;
}
С помощью такого определения словаря можно решать самые разнообразные задачи по обработке текстов. Для большинства задач необходимо, по крайней мере, еще несколько функций, которые выдавали бы информацию обо всем словаре в целом. Можно определить следующие функции:
int size(); // Количество слов в словаре
Iterator<string> keys (); // Итератор всех ключей словаря
Iterator<Object> objects (); // Итератор всех связанных объектов
Тем не менее у приведенной реализации имеется ряд недостатков. Наиболее серьезный из них — то, что размер таблицы выбран произвольно, и он никак не зависит от количества хранящихся в таблице объектов. При небольшом количестве объектов это приводит к напрасному расходу памяти. Наоборот, если количество хранимых объектов велико, то списки элементов с одним и тем же значением функции расстановки для ключей становятся длинными, а это приводит к сильному замедлению всех основных операций с таблицей.
Лучше всего в таких случаях связывать алгоритм работы функции расстановки и общую организацию таблицы с количеством объектов, хранящихся в ней. Например, если общее количество объектов более, чем в два раза превышает размер массива списков объектов diet, то можно провести так называемое перехеширование. При этом массив расширяется (например, в два раза), функция расстановки изменяется в соответствии с новым размером таблицы, а все слова вместе со связанными с ними объектами перемещаются в новые списки в соответствии с новыми значениями функции расстановки. Конечно, перехеширование— это серьезная и длительная операция, но зато после ее выполнения все операции со словарем начинают работать быстрее.
На самом деле совершенно неважно, являются ли ключами для поиска в хеш-таблице именно слова. Фактически ключами могут служить любые объекты, лишь бы для них можно было определить подходящую функцию расстановки.
Поиск подстроки в строке
Часто приходится сталкиваться со специфическим поиском, так называемом поиском подстроки в строке. Его можно определить следующим образом. Пусть задана строка S из N элементов и строка p из M элементов. Описаны они так:
string S[N], P[M];
Задача поиска подстроки P в строке S заключается в нахождении первого слева вхождения P в S, т.е. найти значение индекса i, начиная с которого
S[i] = P, S[i + 1] = P,…, S[i + M – 1] = P[M – 1].
Разберем самый очевидный, самый «прямолинейный» алгоритм поиска.
Алгоритм прямого поиска подстроки в строке
1. Установить i на начало строки S, т.е. i = 0.
2. Проверить, не вышло ли i + M за границу N строки S. Если да, то алгоритм завершен (вхождения нет).
3. Начиная с i-го символа s, провести посимвольное сравнение строк S и p, т. е. S[i] и P, S[i+1] и P,…, S[i + M – 1] и P[M – 1].
4. Если хотя бы одна пара символов не совпала, то увеличить i и повторить шаг 2, иначе алгоритм завершен (вхождение найдено).
Приведем пример, иллюстрирующий этот процесс. Символы образца, подвергшиеся сравнению, выделены синим цветом. Здесь
S: на дворе трава, на траве дрова;
P: траве.
|
н |
а |
д |
в |
о |
р |
е |
т |
р |
а |
в |
а |
, |
н |
а |
т |
р |
а |
в |
е |
|
д |
р |
о |
в |
а |
||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
|||||||||||||||||||||||||
|
т |
р |
а |
в |
е |
Приведем две блок-схемы, описывающие алгоритм. В первой блок-схеме (рис.1) используется дополнительная переменная flag, которая явно изменяет свое значение с 0 на 1 при обнаружении вхождения образца P в текст S.
Рис. 1. Блок-схема: Алгоритм прямого поиска подстроки в строке.
Во второй блок-схеме (рис.2) используется тот факт, что при j = M мы дошли до конца образца P, тем самым обнаружив его вхождение в строку S.
Рис. 2. Блок-схема: Алгоритм прямого поиска подстроки в строке.
Алгоритм работает достаточно эффективно, если при сравнении образца P с фрагментом текста S довольно быстро выявляется несовпадение (после нескольких сравнений во внутреннем цикле). Это случается довольно часто, но в худшем случае (когда в строке часто встречаются фрагменты, во многих символах совпадающие с образцом) производительность алгоритма значительно падает. Приведем пример. Здесь
S: учить, учиться, учитель
P: учитель
|
у |
ч |
и |
т |
ь |
, |
у |
ч |
и |
т |
ь |
с |
я |
, |
у |
ч |
и |
т |
е |
л |
ь |
||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
||||||||||||||||
|
у |
ч |
и |
т |
е |
л |
ь |
БМ-поиск (Боуера–Мура)
Рассмотрим самый «плохой» для линейного поиска случай:
Подсчитаем для него число сравнений. Так как несовпадение символов происходит на последней букве образца, в каждом внешнем цикле производится M сравнений. Так как образец находится в конце строки, число внешних циклов равно N – M + 1, т.е. общее число сравнений есть M(N – M + 1). В 1975 году Р. Боуер и Д. Мур предложили алгоритм, который значительно ускоряет обработку данного случая. Алгоритм носит название БМ-поиска.
В отличие от линейного поиска, сравнение в БМ-поиске начинается не с начала, а с конца образца P. Кроме того, образец предварительно анализируется и благодаря этому он сдвигается не на один символ, а в общем случае на несколько. Рассмотрим механизм сдвига на примере.
S: на дворе трава, на траве дрова
P: дрова
Начинаем сравнение с последнего символа образца. Символы, подвергшиеся сравнению, выделены: в строке – красным цветом, в образце – синим. Индекс k указывает на первый сравниваемый символ в строке S (первоначально k = M - 1), индексы i и j – на сравниваемые символы в образце и строке соответственно. Сначала i = M - 1, j = k, затем i и j уменьшаются на единицу, пока не произойдет несовпадение символов S[j] и P[i] либо не закончится образец (i = -1).
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
|
д |
в |
о |
р |
е |
|
т |
р |
а |
в |
а |
, |
|
н |
а |
|
т |
р |
а |
в |
е |
|
д |
р |
о |
в |
а |
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Совпадения не произошло при первом же сравнении, необходимо сдвинуть образец, т.е. увеличить индекс k. В БМ-поиске образец сдвигается так, чтобы «под» символом S[k] (в таблице) оказался совпадающий с ним ближайший к концу символ образца (иначе при j = k совпадение S[j] и P[i] точно не произойдет). Значит, в данном случае сдвигаем образец на одну позицию вправо, т.е. увеличиваем индекс k на единицу.
|
k |
|||||||||||||||||||||||||||||
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
|
д |
в |
о |
р |
е |
|
т |
р |
а |
в |
а |
, |
|
н |
а |
|
т |
р |
а |
в |
е |
|
д |
р |
о |
в |
а |
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Совпадения образца со строкой опять не произошло, сдвигаем образец. Теперь S[k] = ‘о’ и расстояние от конца образца до символа ‘о’ в нем равно двум, значит, индекс k увеличиваем на два.
|
k |
|||||||||||||||||||||||||||||
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
|
д |
в |
о |
р |
е |
|
т |
р |
а |
в |
а |
, |
|
н |
а |
|
т |
р |
а |
в |
е |
|
д |
р |
о |
в |
а |
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
И опять не произошло совпадения образца со строкой. Теперь S[k] = ‘е’, такого символа в образце нет, поэтому мы можем сдвинуть образец сразу на его длину, т.е. увеличить индекс k на M.
|
k |
|||||||||||||||||||||||||||||
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
|
д |
в |
о |
р |
е |
|
т |
р |
а |
в |
а |
, |
|
н |
а |
|
т |
р |
а |
в |
е |
|
д |
р |
о |
в |
а |
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Здесь S[k] = ’в’, расстояние от конца образца до символа ‘в’ равно единице, значит, индекс k увеличиваем на единицу.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
д |
в |
о |
р |
е |
т |
р |
а |
в |
а |
, |
н |
а |
т |
р |
а |
в |
е |
д |
р |
о |
в |
а |
|||||
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Теперь S[k] = ’а’, такой символ в образце есть, но лишь в последней позиции, в остальной части образца его нет, поэтому увеличиваем индекс k на длину образца M.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
д |
в |
о |
р |
е |
т |
р |
а |
в |
а |
, |
н |
а |
т |
р |
а |
в |
е |
д |
р |
о |
в |
а |
|||||
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Символа S[k] = ’ ’ в образце нет, увеличиваем индекс k на M.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
д |
в |
о |
р |
е |
т |
р |
а |
в |
а |
, |
н |
а |
т |
р |
а |
в |
е |
д |
р |
о |
в |
а |
|||||
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Символа S[k] = ’е’ в образце нет, увеличиваем индекс k на M.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
д |
в |
о |
р |
е |
т |
р |
а |
в |
а |
, |
н |
а |
т |
р |
а |
в |
е |
д |
р |
о |
в |
а |
|||||
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Символ S[k] = ’в’ в образце есть, расстояние от него до конца образца равно единице, увеличиваем индекс k на единице.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
j |
|||||||||||||||||||||||||||||
|
н |
а |
д |
в |
о |
р |
е |
т |
р |
а |
в |
а |
, |
н |
а |
т |
р |
а |
в |
е |
д |
р |
о |
в |
а |
|||||
|
д |
р |
о |
в |
а |
|||||||||||||||||||||||||
|
i |
Здесь индекс i = –1, следовательно, образец в строке найден.
В целом индекс k S[k] меняется следующим образом:
- если символа S[k] в образце нет (кроме, может быть, последнего символа!), то k увеличивается на длину образца M;
- если символ S[k] в образце есть и он не последний, то индекс k увеличивается на расстояние от конца образца до ближайшего символа S[k].
Разумеется, величины сдвигов вычисляются заранее и заносятся в таблицу TAB. Блок-схема для формирования таблицы TAB представлена на рис.3.
Рис.3.Блок-схема для формирования таблицы TAB:
Следует особенно отметить, что j < M – 1, так как TAB[P[M – 1]] должен быть равен M, а не нулю.
Далее достаточно очевидно, что образ в строке найден, если индекс j стал меньше нуля, и образ в строке не найден, если индекс i дошел до конца строки, т.е. стал больше или равен N (i может стать больше N, так как изменяется «скачками»).
Теперь можно привести блок-схему БМ-поиска (рис.4).
Рис.4. Блок-схема БМ-поиска.
КМП-поиск (Кнута–Мориса и–Пратта)
В линейном поиске мы каждый раз сдвигаем образец на одну позицию в строке. В 1970 году Д. Кнут, Д. Морис и В. Пратт изобрели алгоритм, называемый КМП-поиском, который основывается на следующем соображении: если произошло совпадение нескольких символов образца и строки, то мы получили некоторую информацию о строке, которую можно использовать для сдвига образца. Изучим механизм сдвига на примерах.
Пусть в образце все буквы не совпадают с первой, например:
S: от топота копыт пыль по полю летит
P: поле
Рассмотрим несколько случаев. Символы, подвергшиеся сравнению, выделены. Индексы i и j указывают на сравниваемые символы в образце и строке соответственно. Сначала i = j = 0, затем i и j увеличиваются на единицу, пока не произойдет несовпадение символов S[j] и P[i] либо не закончится образец (i = M).
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
П |
о |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пусть уже первый символ образца не совпадает с символом в строке, тогда, не имея информации о составе строки после индекса j, мы увеличиваем j на единицу и оставляем i равным нулю, т.е. сдвигаем образец на одну позицию в строке.
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
П |
о |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Продолжаем действовать так до тех пор, пока не обнаружим совпадения символов образца и строки. Обратим внимание, что индекс j лишь увеличивается.
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
П |
о |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Через несколько шагов получаем:
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
П |
о |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теперь совпали два символ образца и строки. Так как все символы образца не совпадают с первым символом (в частности, P ≠ P) и S[j] ≠ P, то возможно, что S[j] = P. С другой стороны, P ≠ P и S[j - 1] = P, значит, S[j - 1] ≠ P, и не имеет смысла сравнивать эти символы. Поэтому в данном случае индекс j не меняется, а индекс i полагается равным нулю. Следующие несколько шагов сведем в одну таблицу.
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
П |
о |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Остановимся на случае, когда совпал один символ.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
п |
о |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Так как все символы в образце не совпадают с первым и S[j] = P, значит, возможно, что S[j] = P. Поэтому, как и в предыдущем случае, индекс j не меняется, а индекс i полагается равным нулю. Следующие несколько шагов опять сведем в одну таблицу.
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
п |
О |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
О |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
Теперь совпали три буквы образца.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
о |
т |
|
т |
о |
п |
о |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
п |
О |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
Если провести рассуждения, аналогичные предыдущим, то получим, что индекс j не меняется, а индекс i полагается равным нулю.
Можно заметить, что индекс j не меняется, если совпала хотя бы часть образца, и увеличивается на единицу, если ни один символ не совпал. Значит, нет смысла запоминать позицию в строке, где начинается образец, как это делается в линейном поиске (индекс k). Сдвиг образца в КМП-поиске происходит за счет изменения индекса i (это можно видеть в сводной таблице внизу, где выделены рассмотренные символы и показан сдвиг образца). Если хотя бы часть образца совпала, индекс i обнуляется. Затем P[i] сравнивается с S[j]. Если же ни один символ не совпал, i остается равным нулю, а j увеличивается на единицу. То есть можно считать, что i = –1, а затем сравнить P[i + 1] с S[j + 1].
|
j |
|
|
|
|
|
|
j |
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
о |
т |
|
т |
о |
п |
О |
т |
а |
|
к |
о |
п |
ы |
т |
|
п |
ы |
л |
ь |
|
п |
о |
|
п |
о |
л |
ю |
|
л |
е |
т |
и |
т |
|
п |
о |
л |
е |
|
п |
О |
л |
е |
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
п |
о |
л |
е |
|
|
п |
о |
л |
е |
|
|
|
|
|
|
|
|
|
|
п |
о |
л |
е |
|
|
|
|
i |
|
|
|
|
|
|
i |
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
Всю эту информацию можно занести в массив D, где D[k] – новое значение индекса i при условии, что совпало k символов.
|
k |
0 |
1 |
2 |
3 |
|
D[k] |
–1 |
0 |
0 |
0 |
|
P[k] |
п |
о |
л |
е |
Очевидно, что массив имеет подобный же вид во всех случаях, когда ни один из символов образца не совпадает с первым.
|
k |
0 |
1 |
… |
m |
|
D[k] |
–1 |
0 |
0 |
0 |
Общие правила построения массива D таковы:
- D = -1
- Если перед P[j] нет фрагмента, который совпадает с началом образца, и P[j] ≠ P, то D[j] = 0
Рассмотрим теперь ситуацию, когда несколько первых символов образца повторяются в образце еще раз.
S: каравай каркнуть каркать
P: каркас
Здесь зеленым цветом выделены повторяющиеся фрагменты образца.
На основании этих наблюдений можно сформулировать правило:
- Если перед P[j] есть фрагмент длины k, который совпадает с началом образца, и P[j] = P[k], то D[j] = D[k].
Рассмотрим ситуацию, когда совпало пять символов.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
к |
а |
р |
а |
в |
а |
й |
|
к |
а |
р |
к |
н |
у |
т |
ь |
|
к |
а |
р |
к |
а |
т |
ь |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
к |
а |
р |
к |
а |
с |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
Несовпадение символов произошло при i = 5, т.е. S[j] ≠ P, и при этом S[j – 1] = P = P и S[j – 2] = P = P. Так как P ≠ P и S[j] ≠ P, возможно, что S[j] = P, и образец надо сдвинуть следующим образом:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
к |
а |
р |
а |
в |
а |
й |
|
к |
а |
р |
к |
н |
у |
т |
ь |
|
к |
а |
р |
к |
а |
т |
ь |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
к |
а |
р |
к |
а |
с |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
к |
а |
р |
к |
а |
с |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
Образец сдвигается так, чтобы совместить совпадающие части образца и строки (выделенные зеленым цветом). Здесь индекс j не меняется, а индекс i равен двум (числу символов в совпадающих частях образца). Еще раз подчеркнем, что нет необходимости сдвигать назад индекс j, так как в ходе предыдущих сравнений получено, что S[j - 2]S[j - 1] = PP = PP = ка.
Общее правило здесь такое:
- Если перед P[j] есть фрагмент длины k, который совпадает с началом образца, и P[j] ≠ P[k], то D[j] = k.
Всю эту информацию можно занести в массив D, где D[k] – новое значение индекса i при условии, что совпало k символов.
|
k |
0 |
1 |
2 |
3 |
4 |
5 |
|
D[k] |
–1 |
0 |
0 |
–1 |
0 |
2 |
|
P[k] |
к |
а |
р |
к |
а |
с |
В общем случае, когда первые q символов образца повторяются, начиная с l-го символа (P…P[q - 1] = P[l]…P[l + q - 1]), массив D имеет вид:
|
k |
0 |
1 |
… |
l - 1 |
l |
l + 1 |
… |
l + q - 1 |
l + q |
l + q + 1 |
… |
M - 1 |
|
D[k] |
–1 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
q |
0 |
0 |
0 |
При этом не обязательно l > q – 1! Например, если образец имеет вид , то массив (фрагмент P…P[M – 2] совпадает с началом образца P…P[M - 3]), массив D выглядит так:
|
k |
0 |
… |
M - 2 |
M - 1 |
|
D[k] |
–1 |
… |
–1 |
M - 2 |
|
P[k] |
a |
… |
a |
b |
Перечислим здесь все выведенные нами правила формирования массива D:
- D = -1.
- Если перед P[j] нет фрагмента, который совпадает с началом образца, и P[j] ≠ P, то D[j] = 0.
- Если перед P[j] нет фрагмента, который совпадает с началом образца, и P[j] = P, то D[j] = -1.
- Если перед P[j] есть фрагмент длины k, который совпадает с началом образца, и P[j] ≠ P[k], то D[j] = k.
- Если перед P[j] h есть фрагмент длины k, который совпадает с началом образца, и P[j] = P[k], то D[j] = D[k].
Таким образом, чтобы построить массив D, необходимо исследовать образец и найти в нем фрагменты, совпадающие с его началом, т.е., по сути, решить задачу поиска подстроки в строке. Это можно осуществить с помощью того же алгоритма КМП-поиска. Приведем блок-схему построения массива D(рис.5).
Рис.5. Блок-схема построения массива D.
Пример 1
|
k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
D[k] |
–1 |
0 |
0 |
0 |
–1 |
0 |
0 |
3 |
–1 |
|
P[k] |
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
S |
a |
b |
c |
a |
b |
k |
a |
b |
c |
d |
a |
a |
b |
c |
d |
a |
b |
c |
d |
e |
a |
b |
c |
d |
a |
b |
c |
e |
f |
h |
|
P |
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
|
|
|
|
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
c |
d |
a |
b |
c |
e |
f |
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
Блок-схема КМП-поиска имеет вид:
Рис.6. Блок-схема КМП-поиска.
Обсудим преимущества данного алгоритма. Как вы могли заметить на примерах, индекс j, который передвигается по строке, может только увеличиваться. В связи с этим можно выделить два важных момента.
Во-первых, рассмотрим самый плохой случай для линейного поиска.
Как было показано, число сравнений в линейном поиске равно M(N – M +1). Рассмотрим, как в этом случае работает КМП-поиск.
|
k |
0 |
… |
M - 2 |
M - 1 |
|
D[k] |
–1 |
… |
–1 |
M - 2 |
|
P[k] |
a |
… |
a |
b |
|
S |
a |
… |
a |
a |
a |
… |
a |
… |
a |
b |
|
P |
a |
… |
a |
b |
|
|
|
|
|
|
|
i |
|
|
|
M - 1 |
|
|
|
|
|
|
|
P |
|
… |
a |
a |
b |
|
|
|
|
|
|
i |
|
|
|
|
M - 1 |
|
|
|
|
|
|
… |
|
|
|
|
|
… |
|
|
|
|
|
P |
|
|
|
|
|
|
a |
… |
a |
b |
|
i |
|
|
|
|
|
|
|
|
|
M - 1 |
При значениях индекса i = 0, 1, …, M - 2 символы строки и образца совпадают: S[j] = P[i]. При i = M - 1 обнаруживается несовпадение и образец сдвигается так, что i = M - 2, т.е. на одну позицию, при этом символ S[j] сравнивается с символом P[M - 2]. Таким образом, символы строки, начиная с j = M - 1 (кроме последнего), сравниваются сначала с P[M - 1], а затем с P[M - 2], т.е. подвергаются двум сравнениям. Остальные символы строки сравниваются с символами образца лишь один раз. Таким образом, общее число сравнений есть 2N - M + 1, что в общем случае существенно меньше, чем в линейном поиске.
Во-вторых, индекс j, движущийся по строке, может только увеличиваться. Это позволяет искать образец в строке, заданной не массивом, а файлом, не используя дополнительных массивов для хранения информации.
Контрольные вопросы
- Перечислите основные алгоритмы поиска в массивах.
- Опишите принцип работы последовательного алгоритма поиска.
- Опишите принцип работы двоичного алгоритма поиска.
- Как реализован принцип хеширования.
- Какая должна быть хеш-функция?
- Когда возникает коллизия и как она разрешается?
- Перечислите основные алгоритмы поиска подстроки в строке.
- В чем суть линейного алгоритма поиска?
- Опишите алгоритм БМ-поиска.
- Опишите агоритм БМП-поиска.
- Какой из алгоритмов поиска оптимальнее?
- Какой алгоритм поиска быстродейственее?
Задания для практической работы
- Реализовать алгоритмы последовательного и двоичного поиска. Провести сравнительный анализ при разных входных данных.
- Хеширование:
1. Задан текст программы на языке Паскаль. Определить частоту использования:
а) идентификаторов;
б) ключевых слов:
в) символьных констант.
2. Задан текстовый файл. Сформировать список слов, употребляющихся в тексте более пяти раз.
3. Задан текстовый файл. Сформировать набор словосочетаний по два и более слова, встречающихся в тексте не менее двух раз.
4. Задан набор записей следующей структуры: табельный номер. ФИО. заработная плата. По табельном}* номеру найти остальные сведения.
5. Задан набор записей следующей структуры: номер телефона. ФИО адрес. По номеру телефона найти сведения о ФИО владельца и его адресе.
Задан набор записей следующей структуры: название кинофильма, режиссер, список актеров, краткое содержание. По заданному названию фильма найти остальные сведения.
6. Задан набор записей следующей структуры: номер автомобиля, его марка и ФИО владельца. По номеру автомобиля найти остальные сведения.
7. Задан список имен людей. Определить частоту использования каждого имени в некотором тексте.
8. Создать модуль, реализующий методы для работы с хеш-таблицей: инициализация, добавление элемента, удаление элемента, поиск. Кроме того, при заполнении хеш-таблицы выше заданного уровня размер хеш-таблицы должен автоматически увеличиваться.
9. Исследовать зависимость числа коллизий от коэффициента заполненности хеш-таблицы.
10.Из файла, содержащего текст на русском языке, слова помещаются в хеш-таблицу. Определить среднее число коллизий для нескольких заданных хеш-функций.
- Реализовать и провести сравнительный анализ приведенных алгоритмов поиска подстроки в строке.
PAGE 77
2. реферату Поняття про волю теорії волі розвиток волі в дитячому віціРозділ Психологія Поняття про волю те
3. Основы психодиагностики для студентов заочного отделения факультета психологии 1
4. Ієрархічна структура управління фізичною культурою і спортом в Хмельницькій області у м. Камянець-Подільському
5. Профилактика переохлаждения и отморожений
6. Muse за то что вдохновили меня на создание целой саги
7. соответсвие требованиям нормам права 2
8. Проект реконструкции ИП Ермишкина ЛИ г Арсеньев по производству сдобных булочных изделий
9. соблюдение религиозных обрядов
10. тема представляющая единство трех составляющих- 1 биологического анатомофизиологические задатки тип н
11. Когда впервые раскрылись Небо и Земля имена богов явившихся на Равнине Высокого Неба были- БогПравител
12. Сумен жабды~тау ж~йесі.html
13. реферат дисертації на здобуття наукового ступеня кандидата медичних наук1
14. Укладіть термінологічний словник не менше 30 одиниць за своїм фахом
15. Крымская кампания планы союзных держав
16. Тема 13 32 ВЫБОР ЭФФЕКТИВНОГО СТИЛЯ РУКОВОДСТВА Вопросы Факторы и элементы эффективного стиля руковод
17. Задание Нарисовать предложенные ниже объекты используя инструменты создания и редактирования векторной г.
18. НИЖНЕТАГИЛЬСКИЙ ТОРГОВОЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ портфолио по дисциплине-
19. Темпераментом называется характерная для данного человека совокупность психических особенностей связанн
20. ширк означает уравнивание двух вещей