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

Сначала пометим все вершины графа, как непосещенные. Поиск в глубину начинается с произвольной вершины графа, например с первой, обозначим ее v. При этом значение метки v меняется на противоположное (вершина уже посещалась). Затем, для каждой вершины, смежной с v, которая ранее не посещалась, рекурсивно вновь применяется поиск в глубину. Легко показать, что при этом все вершины, достижимые из начальной, то есть образующие одну компоненту связности, будут пройдены. Если некоторые вершины оказались непройденными, то граф не связан. Для полного его обхода выбираем любую еще непосещенную вершину и поиск продолжается. Очевидно, что таким образом можно не только проверять связность графа, но и подсчитывать количество компонент связности. Приведем процедуру поиска в глубину и фрагмент основной программы, решающей эту задачу. Считаем, что граф задан с помощью матрицы булевской матрицы смежности a (см. предыдущую лекцию), а метятся вершины графа с помощью массива vert: array[1..nmax] of boolean.

procedure d_f_s(v:byte);

var i:byte;

begin

{ writeln(v); или другая обработка вершины v}

vert[v]:=false;{вершина посещена}

for i:=1 to n do

if a[v,i] and vert[i] then

d_f_s(i)

end;

begin

…{заполняем матрицу смежности}

{метим все вершины как непосещенные}

fillchar(vert,sizeof(vert),true);

cnt:=0;{счетчик компонент связности}

for i:=1 to n do

if vert[i] then

begin

inc(cnt);

d_f_s(i)

end;

writeln(cnt)

end.

Подсчитаем вычислительную сложность предложенной реализации алгоритма. Так как для каждой вершины процедура d_f_s вызывается ровно один раз, а количество операций в ней пропорционально N -- количеству вершин в графе, то количество операций в алгоритме есть O(N2), а его применимость ограничена лишь размером памяти, необходимой для представления матрицы смежности. Ниже будет приведена и более эффективная реализация данного алгоритма.

Перейдем теперь к рассмотрению поиска в ширину. Свое название он получил из-за того, что при достижении во время обхода любой его вершины v в очередь на рассмотрение попадают сразу все еще не просмотренные вершины, связанные с вершиной v. На каждом шаге из начала очереди извлекается один элемент, а в конец добавляются связанные с ним вершины, еще не находящиеся в очереди. Поэтому элементы метятся как обработанные в момент попадания в очередь, а не извлечения из нее. Так как максимальное количество элементов в очереди равно количеству вершин в графе, организовать ее можно и с помощью одномерного массива (структура данных очередь и способы ее представления подробно описаны в [4]). В приведенной ниже программе для этого используется массив list: array[1..nmax] of byte и целочисленные переменные p и q, являющиеся указателями на индексы элементов, соответствующих началу и концу очереди. Приведем только процедуру поиска в ширину, так как основная программа остается прежней (вызов процедуры поиска в глубину заменяется в ней на процедуру поиска в ширину), отметим, что эта процедура нерекурсивна.

procedure b_f_s(v:byte);

var i,k,p,q:byte;

begin

fillchar(list,sizeof(list),0);

list[1]:=v;

vert[v]:=false;

p:=1;{указатель на начало очереди}

q:=1;{указатель на конец очереди}

while p<=q do{пока очередь не исчерпана}

begin

{обработать первую в очереди вершину,

например, writeln(list[p]);}

k:=list[p]; p:=p+1;

for i:=1 to n do

if a[k,i] and vert[i] then

{добавляем i-й элемент в очередь}

begin

vert[i]:=false;

q:=q+1;

list[q]:=i

end

end

end

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

Для полноты изложения приведем реализации обоих алгоритмов, основанные на другом представлении графа -- одномерном массиве списков вершин, связанных с каждой из вершин. Для этого будем использовать такую структуру данных, как динамический связанный список (см. [4]). Так как основная программа остается прежней, приведем лишь описание основных структур данных, модифицированные процедуры поиска и начало программы, в котором и создаются упомянутые списки. Для описания графа используется массив указателей a на начала динамических списков и массив указателей на конечные элементы списков b (последний нужен лишь для организации поиска в ширину). В основной программе может вызваться любая из описанных процедур. При поиске в ширину в очередь будут помещаться все элементы, связанные с вершиной, находящейся в начале очереди, зато за одну операцию соединения списков. Помечаться же как обработанные вершины будут лишь при удалении из очереди.

const nmax=500;

type ptr = ^el; {указатель на элемент списка}

el = record

i:integer; next:ptr

end;

var a,b: array[1..nmax] of ptr;

vert: array[1..nmax] of boolean;

p:ptr;

i,j,k,m,n,cnt:integer;

procedure d_f_s(v:integer);

begin

vert[v]:=false;

while a[v]<>nil do

{пока список вершин, связанных с v,

не исчерпан}

begin

if vert[a[v]^.i] then

d_f_s(a[v]^.i);

{переходим к следующему элементу списка}

a[v]:=a[v]^.next

end

end;

procedure b_f_s(v:integer);

var p,q:ptr;

begin

vert[v]:=false;

p:=a[v];{указатель на начало очереди}

q:=b[v];{указатель на конец очереди}

while p<>nil do

{пока очередь не исчерпана}

begin

if vert[p^.i] then

begin

vert[p^.i]:=false;

{добавим в очередь сразу все

элементы, связанные с p^.i}

q^.next:=a[p^.i];

q:=b[p^.i];

end;

p:=p^.next {меняем начало очереди}

end;

end;

begin {основная программа}

readln(n);{n - количество вершин}

for i:=1 to n do a[i]:=nil;

readln(m);{m - количество ребер}

for i:=1 to m do {cчитываем ребра}

begin

read(j,k);{ребро из j в k}

{добавляем элемент в список a[j]}

new(p);

p^.i:=k;

p^.next:=a[j];

if a[j]=nil then b[j]:=p;

a[j]:=p;

{добавляем элемент в список a[k]}

new(p);

p^.i:=j;

p^.next:=a[k];

if a[k]=nil then b[k]:=p;

a[k]:=p

end;

{структура для описания графа создана}

…{далее программа совпадает с первой}

end.

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

2. Поиск эйлерова пути в графе

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

Теорема 1. Эйлеров путь в неориентированном графе существует тогда и только тогда, когда граф связан и содержит не более двух вершин нечетной степени.

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

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

v:=произвольная вершина графа, обычно первая;

STACK<=v;{вершина заносится в стек}

while (STACK не пуст) do

begin

v:=верхний элемент стека STACK;

if (в графе еще есть вершины,

связанные с v) then

begin

u:=любая вершина, связанная с v;

STACK<=u;

удаляем ребро {v,u} из графа;

end

else

begin

v<=STACK;{вершина удаляется из стека}

RES<=v{вершина заносится в результат}

end

end.

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

procedure search(v:byte);

var j:byte;

begin

for j:=1 to n do

if a[v,j]=1 then

begin

a[v,j]:=0;a[j,v]:=0;

search(j)

end;

inc(p);

res[p]:=v

end.

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

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

Очевидно, что при наличии двух вершин ненулевой степени в ориентированном графе, начинаться эйлеров путь должен в вершине со степенью 1, а заканчиваться -- в вершине со степенью -1. Интересно, что схема поиска самого пути при этом остается неизменной. А в процедуре search следует лишь убрать обнуление элемента матрицы смежности a[j,v], т.к. в ориентированном графе каждому ребру соответствует один элемент матрицы, а не два.

Попробуйте теперь решить следующую задачу, которая была рекомендована для областных олимпиад по информатике в 2001/2002 уч. году.

Задача 1. Для решения транспортной проблемы в некотором городе до недавнего времени использовались N (N?100) автобусных маршрутов. Каждый маршрут начинался на одной из M (M?200) площадей и там же заканчивался.

В процессе проезда по маршруту автобус мог несколько раз проезжать одну и ту же площадь, но не мог проезжать более одного раза по одной и той же улице в том же самом направлении.

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

Если по каким-либо улицам автобусы ездили в обоих направлениях, то и новый маршрут должен проходить по этим улицам в обоих направлениях, но дважды по одной улице в одном направлении автобус проезжать не может. По тем улицам и в тех направлениях, по которым раньше автобусы не ездили, новый маршрут проходить не должен.

Требуется написать программу, которая для заданных исходных данных определяет требуемый местным властям автобусный маршрут.

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

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

3. Построение минимального остова во взвешенном неориентированном графе

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

Алгоритмы, решающие эту задачу, относятся к классу так называемых жадных. Наиболее простым в реализации является алгоритм Прима. Он в некоторой степени похож на алгоритм Дейкстры поиска кратчайшего пути во взвешенном графе. Формирование остова начинается с произвольной вершины графа. Первым в остовное дерево включается ребро наименьшего веса, выходящее из выбранной вершины. На каждом шаге к дереву добавляется ребро наименьшего веса среди ребер, соединяющих вершины этого дерева с вершинами, пока в дерево не вошедшими. При реализации важно уметь быстро выбирать требуемое ребро минимальное веса. Для того, чтобы на каждом шаге не пересчитывать расстояние от текущего остовного дерева до всех не вошедших в него вершин, эти расстояния удобно хранить в линейном массиве (в программе d), пересчитывая его значения после добавления в остов нового элемента. Как и ранее для пометки вершин, уже вошедших в остовное дерево, будем использовать булевский массив vert. Следующие две процедуры показывают, как для произвольного графа, вес ребер которого задается с помощью функции a(i,j), а отсутствие ребра между двумя вершинами обозначается весом, равным (конкретное числовое значение для этого параметра подбирается исходя из условия задачи), построить остовное дерево.

procedure calc(i:integer);

{пересчитывает расстояние до остова, i -- вершина, включенная в остов последней}

var j:integer;

begin

for j:=1 to n do

if not vert[j] then

if d[j]>a(i,j) then

begin

d[j]:=a(i,j);

res[j]:=i

end

end;

procedure build;

{cтроит минимальный остов}

var i,j,imin:integer;

min:extended;

begin

fillchar(vert,sizeof(vert),false);

for i:=1 to n do d[i]:=;

vert[1]:=true;

calc(1);

for j:=1 to n-1 do

{остов состоит из n-1 ребра}

begin

min:=;

for i:=1 to n do

if not vert[i] then

if min>d[i] then

begin

min:=d[i];

imin:=i

end;

vert[imin]:=true;

calc(imin);

{в остов вошло ребро imin-res[imin]}

writeln(imin,' ',res[imin])

end

end.

Используя приведенные процедуры попробуйте решить следующую задачу (аналогичная задача “Highways” в англоязычной формулировке предлагалась на полуфинале студенческого чемпионата мира по программированию в г.Санкт-Петербурге в 1999 г., тесты к ней можно найти на сайте neerc.ifmo.ru).

Задача 2. Правительство России проанализировало систему дорог в России и выяснило, что только часть из них соответствует международным стандартам. Было принято решение создать систему скоростных автодорог, соединяющих крупные города. Сеть дорог требуется спроектировать так, чтобы по ним и по уже существующим хорошим дорогам можно было проехать из любого данного города в любой другой, однако затраты на строительство должны быть минимальны (будем считать, что минимальные затраты соответствуют минимальной суммарной длине построенных дорог).

Первая строка входного файла содержит целое число городов N (1 ? N ? 750), которые должны быть соединены приличными дорогами. Следующие N строк содержат по 2 целых числа, разделенных пробелами, xi и yi -- декартовы координаты городов в километрах от Москвы. Следующая строка содержит целое число M (0 ? M ? 1000), соответствующее количеству уже имеющихся хороших дорог между городами. В каждой из следующих M строк содержится пара номеров городов, которые соединены хорошей дорогой (номера городов соответствуют порядку описания их координат во входном файле, начиная с 1).

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

4. Построение максимального паросочетания в двудольном графе

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

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

Пусть в графе построено некоторое паросочетание такое, что из оставшихся свободными вершин новых пар составить уже нельзя (оно не обязательно максимально). Чередующейся цепью относительно этого паросочетания назовем такую последовательность вершин x0, y1, x2, y3, …,xk, yk+1, k>0, что вершины xi принадлежат одному из множеств двудольного графа и все, кроме x0, входят в текущее паросочетание, а вершины yi принадлежат другому множеству и все, кроме yk+1, входят в текущее паросочетание, причем паросочетанию принадлежат ребра (yi, xi+1), i=1, …, k-1, а ребра (xi, yi+1), i=0, …, k, в графе существуют, но в текущее паросочетание не входят. Тогда мы можем исключить из паросочетания первую группу ребер и включить вторую, увеличив тем самым количество пар на единицу. Следующая теорема позволяет применить описанную процедуру при решении задачи нахождения максимального паросочетания.

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

Наиболее подробно теория паросочетаний изложена в [5]. К сожалению, несмотря на наличие конструктивного алгоритма построения максимального паросочетания, его реализации в литературе по алгоритмам на графах достаточно громоздки. Программа, предлагаемая ниже, основана на схеме решения задачи о стабильных браках, приведенной в [4]. Несмотря на то, что механизм чередования цепочек в ней присутствует, логика выполняемых операций несколько отлична от описанной выше. В основной программе каждой вершине одного из множеств мы пытаемся найти допустимую пару (очевидно, что если каждой вершине пара будет найдена, то максимальное паросочетание построено). Делается это с помощью рекурсивной функции try. Если для вершины j свободной пары в противоположном множестве нет, то делается попытка построить чередующуюся цепочку, начинающуюся с j-й вершины.

const max=…{размер большего из двух множеств}

var v: array[1..max] of boolean;

res: array[1..max] of integer;

n, m, i, j, cnt: integer;

function try (j: integer): boolean;

{пытается найти вершине j пару}

var i: integer;

begin

if v[j] then

{j в текущем паросочетании уже просмотрена}

begin

try:= false; exit

end;

v[j]:= true;

for i:= 1 to n do

if a(i, j) {ребро между i и j существует}

and ((res[i] = 0) {у i еще нет пары}

or{пару i можно пристроить к другой вершине,

для чего нужно построить чередующуюся цепочку}

try(res[i])) then

begin

try:=true;

res[i]:=j;

exit

end;

try:=false

end;

begin

…{здесь вводим описание графа}

fillchar(res,sizeof(res),0);

cnt:=0;{счетчик ребер в паросочетании}

for j:= 1 to m do

{каждой вершине одного из множеств пытаемся найти пару}

begin

fillchar(v,sizeof(v),false);

if try(j) then inc(cnt)

end;

writeln(cnt);

for i:= 1 to n do

if res[i] <> 0 then

write(i,' ',res[i])

end.

Задача, при решении которой используется описанный алгоритм, предлагалась на I Всероссийской командной олимпиаде школьников по программированию в 2000 г.

Задача 3. “Кубики”.

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

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.

На первой строке входного файла находится число N (1N100) -- количество кубиков в наборе у Пети. На второй строке записано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

Заключение