введем порядок: путь предшествует своему продолжению; если два
пути расходятся в некоторой вершине, то меньшим считается тот,
который выходит из нее по меньшему ребру. Вершины теперь упоря-
дочиваются в соответствии с минимальными путями, в них ведущими.
Обход вершин графа ы указанном порядке называется поиском в глу-
бину.
9.2.2. Написать программу поиска в глубину.
Указание. Возьмем программу обхода дерева (корень - левое
поддерево - правое поддерево) из главы о рекурсии или из гравы
об устранении рекурсии и используем ее применительно к обсто-
ятельствам. Главное изменение: не надо посещать вершины повтор-
но. Так что если мы попали в уже посещенную вершину, то можно с
ней ничего не делать. (Если путь не минимален среди ведущих в
данную вершину, то и все его продолжения не минимальны - их
просматривать не надо).
Замечание. Существуют две возможности устранения рекурсии в
программе обхода дерева. Можно хранить в стеке корни подлежащих
посещению поддеревьев (как это делалось в главе об устранении
рекурсии). А можно применять метод из главы об обходе дерева, то
есть реализовать операции "вверх_налево", "вправо" и "вниз".
Чтобы их реализовать, необходимо хранить в стеке путь из корня к
текущей вершине. Оба способа - примерно одинаковой сложности, и
в конкретной ситуации любой из них может оказаться более удоб-
ным.
Поиск в глубину лежит в основе многих алгоритмов на графах,
порой в несколько модифицированном виде.
9.2.3. Неориентированный граф называется двудольным, если
его можно раскрасить в два цвета так, что концы любого ребра -
разного цвета. Составить алгоритм проверки, является ли заданный
граф двудольным (число действий не провосходит C*(число ребер +
число вершин).
Указание. (а) Каждую связную компоненту можно раскрашивать
отдельно. (б) Выбрав цвет одной вершины и обходя ее связную ком-
поненту, мы определяем единственно возможный цвет остальных.
Замечание. В этой задаче безразлично, производить поиск в
ширину или в глубину.
9.2.4. Составить нерекурсивный алгоритм топологической сор-
тировки ориентированного графа без циклов. (См. задачу 7.4.2 в
главе о рекурсии.)
Решение. Предположим, что граф имеет вершины с номерами
1..n, для каждой вершины i известно число num[i] выходящих из
нее ребер и номера вершин dest[i][1],..., dest[i][num[i]], в ко-
торые эти ребра ведут. Будем условно считать, что ребра перечис-
лены "слева направо": левее то ребро, у которого номер меньше.
Нам надо напечатать все вершины в таком порядке, чтобы конец лю-
бого ребра был напечатан перед его началом. Мы предполагаем, что
в графе нет ориентированных циклов - иначе такое невозможно.
Для начала добавим к графу вершину 0, из которой ребра ве-
дут в вершины 1,...,n. Если ее удастся напечатать с соблюдением
правил, то тем самым все вершины будут напечатаны.
Алгоритм хранит путь, выходящий из нулевой вершины и иду-
щий по ребрам графа. Переменная l отводится для длины этого пу-
ти. Путь образован вершинами vert[1],..., vert[l] и ребрами,
имеющими номера edge[1]...edge[l]. Номер edge[s] относится к ну-
мерации ребер, выходящих из вершины vert[s]. Тем самым для всех
s должны выполняться неравенство
edge[s] <= num[vert[s]]
и равенство
vert[s+1] = dest [vert[s]] [edge[s]]
Впрочем, для последнего ребра мы сделаем исключение, разрешив
ему указывать "в пустоту", т.е. разрешим
edge[l] равняться num[vert[l]]+1.
В процессе работы алгоритм будет печатать номера вершин,
при этом соблюдая требование "вершина напечатана только после
тех вершин, в которые из нее ведут ребра". Наконец, будет выпол-
няться такое требование:
(И) вершины пути, кроме последней (т.е. vert[1]..vert[l])
не напечатаны, но свернув с пути налево, мы немедленно
упираемся в напечатанную вершину
Вот что получается:
l:=1; vert[1]:=0; edge[1]:=1;
while not( (l=1) and (edge[1]=n+1)) do begin
| if edge[l]=num[vert[l]]+1 then begin
| | {путь кончается в пустоте, поэтому все вершины,
| | следующие за vert[l], напечатаны - можно
| | печатать vert[l]}
| | writeln (vert[l]);
| | l:=l-1; edge[l]:=egde[l]+1;
| end else begin
| | {edge[l] <= num[vert[l]], путь кончается в
| | вершине}
| | lastvert:= dest[vert[l]][edge[l]]; {последняя}
| | if lastvert напечатана then begin
| | | edge[l]:=edge[l]+1;
| | end else begin
| | | l:=l+1; vert[l]:=lastvert; edge[l]:=1;
| | end;
| end;
end;
{путь сразу же ведет в пустоту, поэтому все вершины
левее, то есть 1..n, напечатаны}
9.2.4. Доказать, что если в графе нет циклов, то этот алго-
ритм заканчивает работу.
Решение. Пусть это не так. Каждая вершина может печататься
только один раз, тако что с некоторого момента вершины не печа-
таются. В графе без циклов длина пути ограничена (вершина не мо-
жет входить дважды), поэтому подождав еще, мы можем дождаться
момента, после которого путь не удлиняется. После этого может
разве что увеличиваться edge[l] - но и это не беспредельно.
Глава 10. Сопоставление с образцом.
10.1. Простейший пример.
10.1.1. Имеется последовательность символов x[1]..x[n]. Оп-
ределить, имеются ли в ней идущие друг за другом символы "abcd".
(Другими словами, требуется выяснить, есть ли в слове x[1]..x[n]
подслово "abcd".)
Решение. Имеется примерно n (если быть точным, n-3) позиций,
на которых может находиться искомое подслово в исходном слове.
Для каждой из позиций можно проверить, действительно ли там оно
находится, сравнив четыре символа. Однако есть более эффективный
способ. Читая слово x[1]..x[n] слева направо, мы ожидаем появле-
ния буквы 'a'. Как только она появилась, мы ждем за ней букву
'b', затем 'c', и, наконец, 'd'. Если наши ожидания оправдывают-
ся, то слово "abcd" обнаружено. Если же какая-то из нужных букв
не появляется, мы оказываемся у разбитого корыта и начинаем все
сначала.
Этот простой алгоритм можно описать в разных терминах. Ис-
пользуя терминологию так называемых конечных автоматов, можно
сказать, что при чтении слова x слева направо мы в каждый момент
находимся в одном из следующих состояний: "начальное" (0),
"сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3)
и "сразу после abcd" (4). Читая очередную букву, мы переходим в
следующее состояние по правилу
Текущее Очередная Новое
состояние буква состояние
0 a 1
0 кроме a 0
1 b 2
1 a 1
1 кроме a,b 0
2 c 3
2 a 1
2 кроме a,c 0
3 d 4
3 a 1
3 кроме a,d 0
Как только мы попадем в состояние 4, работа заканчивается.
Соответствующая программа очевидна:
i:=1; state:=0;
{i - первая непрочитанная буква, state - состояние}
while (i<> n+1) and (state <> 4) do begin
if state = 0 then begin
if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 1 then begin
if x[i] = b then begin
state:= 2;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 2 then begin
if x[i] = c then begin
state:= 3;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 3 then begin
if x[i] = d then begin
state:= 4;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end;
end;
answer := (state = 4);
Иными словами, мы в каждый момент храним информацию о том,
какое максимальное начало нашего образца "abcd" является концом
прочитанной части. (Его длина и есть то "состояние", о котором
шла речь.)
Терминология, нами используемая, такова. Слово - это любая
последовательность символов из некоторого фиксированного конеч-
ного множества. Это множество называется алфавитом, его элементы
- буквами. Если отбросить несколько букв с конца слова, останет-
ся другое слово, называемое началом первого. Любое слово также
считается своим началом. Конец слова - то, что останется, если
отбросить несколько первых букв. Любое слово считается своим
концом. Подслово - то, что останется, если отбросить буквы и с
начала, и с конца. (Другими словами, подслова - это концы начал,
или, что то же, начала концов.)
В терминах индуктивных функций (см. раздел 1.3) ситуацию
можно описать так: рассмотрим функцию на словах, которая прини-
мает два значения "истина" и "ложь" и истинна на словах, имеющих
"abcd" своим подсловом. Эта функция не является индуктивной, но
имеет индуктивное расширение
x ->длина максимального начала слова abcd, являющегося концом x
10.2. Повторения в образце - источник проблем.
10.2.1. Можно ли в предыдущих рассуждениях заменить слово
"abcd" на произвольное слово?
Решение. Нет, и проблемы связаны с тем, что в образце могут
быть повторяющиеся буквы. Пусть, например, мы ищем вхождения
слова "ababc". Вот появилась буква "a", за ней идет "b", за ней
идет "a", затем снова "b". В этот момент мы с нетерпением ждем
буквы "c". Однако - к нашему разочарованию - вместо нее появля-
ется другая буква, и наш образец "ababc" не обнаружен. Однако
нас может ожидать утешительный приз: если вместо "c" появилась
буква "a", то не все потеряно: за ней могут последовать буквы
"b" и "c", и образец-таки будет найден.
Вот картинка, поясняющая сказанное:
x y z a b a b a b c .... <- входное слово
a b a b c <- мы ждали образца здесь
a b a b c <- а он оказался здесь
Таким образом, к моменту
|
x y z a b a b | <- входное слово
|
a b a b | c <- мы ждали образца здесь
|
a b | a b c <- а он оказался здесь
|
есть два возможных положения образца, каждое из которых подлежит
проверке. Тем не менее по-прежнему возможен конечный автомат,
читающий входное слово буква за буквой и переходящий из состо-
яния в состояние в зависимости от прочитанных букв.
10.2.2. Указать состояния соответствующего автомата и таб-
лицу перехода (новое состояние в зависимости от старого и чита-
емой буквы).
Решение. По-прежнему состояния будут соответствовать на-
ибольшему началу образца, являющемуся концом прочитанной части
слова. Их будет шесть: 0, 1 ("a"), 2 ("ab"), 3 ("aba"), 4
("abab"), 5 ("ababc"). Таблица перехода:
Текущее Очередная Новое
состояние буква состояние
0 a 1 (a)
0 кроме a 0
1 (a) b 2 (ab)
1 (a) a 1 (a)
1 (a) кроме a,b 0
2 (ab) a 3 (aba)
