Реализация перебора графа с использованием очередей и стеков - Графы

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

Представление графов

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

Граф G = (V, E) имеет два естественных параметра: количество узлов |V| и количество ребер |E|. Для их обозначения мы будем использовать запись n = |V| и m = |E|. Время выполнения будет формулироваться в зависимости от этих двух параметров. Как обычно, мы будем ориентироваться на полиномиальное время выполнения, желательно с низкой степенью. Но когда время выполнения зависит от двух параметров, сравнение не всегда однозначно. Какое время лучше — O(m²) или O(n³)? Это зависит от отношений между n и m. Если любая пара узлов соединяется не более чем одним ребром, количество ребер m не превышает С другой стороны, во многих практических ситуациях рассматриваются связные графы, а согласно (3.1) связный граф должен иметь не менее m ≥ n - 1 ребер. Однако из этих сравнений не всегда очевидно, какой из двух вариантов времени выполнения (например, m² или n³) лучше, поэтому мы будем анализировать время выполнения с учетом обоих параметров. В этом разделе будет реализован базовый алгоритм поиска в графе с временем O(m + n). Это время будет называться линейным, потому что время O(m + n) необходимо просто для чтения ввода. Учтите, что при работе со связными графами время выполнения O(m + n) эквивалентно O(m), потому что m ≥ n - 1.

Возьмем граф G = (V, E) с n узлами, множество которых обозначается V = {1, ..., n}. В простейшем способе представления графа используется матрица смежности. Это матрица A размером n х n, в которой элемент A[u, v] равен 1, если граф содержит ребро (u, v), или 0 в противном случае. Для ненаправленного графа матрица A симметрична, а A[u, v] = A[v, u] для всех узлов u, v ∈V. С представлением матрицы смежности наличие в графе заданного ребра (u, v) проверяется за время O(1). Тем не менее такое представление имеет два основных недостатка.

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

♦ Многие алгоритмы графов требуют проверки всех ребер, инцидентных заданному узлу v. В представлении матрицы смежности для этого требуется перебрать все остальные узлы w и проверить элемент матрицы A[v, w], чтобы узнать, существует ли ребро (v, w), а эта проверка занимает время Ө(n). В худшем случае v может иметь Ө(n) инцидентных ребер, тогда проверка всех ребер будет выполняться за время Ө(n) независимо от представления. Но на практике во многих графах количество инцидентных ребер для большинства узлов существенно меньше, поэтому было бы полезно иметь возможность более эффективно искать инцидентные ребра.

Для представления графов в книге используется список смежности, который лучше подходит для разреженных графов, то есть графов, у которых количество ребер существенно меньше n². В представлении списка смежности для каждого узла v создается запись со списком всех узлов, с которыми узел v соединен ребрами. А если говорить точнее, создается массив Adj, в котором Adj[v] — запись со списком всех узлов, смежных с узлом v. Для ненаправленного графа G = (V, E) каждое ребро e = (v, w) ∈ E присутствует в двух списках смежности: узел w присутствует в списке узла v, а узел v присутствует в списке узла w.

Сравним представления матрицы смежности и списка смежности. Начнем с пространства, необходимого для представления. Матрица смежности имеет размеры n х n, а следовательно, занимает пространство O(n²). С другой стороны, мы утверждаем, что для хранения списка смежности достаточно пространства O(m + n). Ниже приводится обоснование.

Для начала нам понадобится массив указателей длины n для организации хранения списков в Adj, а также место для самих списков. Длины списков могут отличаться от узла к узлу, но, как указано в предыдущем абзаце, каждое ребро e = (v, w) входит ровно в два списка: для v и для w. Таким образом, общая длина всех списков составляет 2m = O(m).

Есть и другой (по сути, эквивалентный) способ обоснования этой границы. Степенью n_v узла v называется количество ребер, инцидентных этому узлу. Длина списка в позиции Adj [v] равна n_v, так что общая длина по всем узлам равна Сумма степеней графа — характеристика, часто встречающаяся при анализе алгоритмов графов, поэтому полезно выяснить, чему она равна.

(3-9)

Доказательство. Каждое ребро e = (v, w) вносит вклад в эту сумму ровно два раза: один раз в величине n_v, и один раз в величине n_w. Так как в сумме учитываются вклады всех ребер, она составит 2m. ■

Сравнение матриц смежности со списками смежности можно резюмировать следующим образом.

(3.10) Представление графа в виде матрицы смежности требует пространства O(n²), а для представления в виде списка смежности достаточно пространства O(m + n).

Так как мы уже выяснили, что m ≤ n², ограничение O(m + n) никогда не бывает хуже O(n²), и оно намного лучше для разреженных графов, в которых m намного меньше n².

Теперь нужно разобраться с простотой обращения к информации, хранящейся в этих двух представлениях. Вспомните, что в матрице смежности проверка присутствия в графе конкретного ребра (u, v) выполняется за время O(1). В списке смежности проверка может занимать время, пропорциональное степени O(n_v): чтобы узнать, входит ли ребро v в список, нужно пройти по указателям списка смежности u. С другой стороны, если алгоритм в настоящее время проверяет узел u, он может прочитать список соседей с постоянными затратами времени на каждого соседа.

С учетом сказанного список смежности является естественным представлением для изучения графов. Если алгоритм в настоящее время рассматривает узел u, он может прочитать список соседей с постоянным временем на каждого соседа; переместиться к соседу v после его обнаружения в списке за постоянное время; и быть готовым к чтению списка, связанного с узлом v. Таким образом, списковое представление соответствует физическому “изучению” графа, в котором при переходе к узлу и вы узнаете его соседей и можете прочитать их с постоянным временем для каждого соседа.

Очереди и стеки

Во многих алгоритмах имеется внутренняя фаза, в которой они должны обработать множество элементов: например, множество всех ребер, инцидентных узлу графа, множество проверенных узлов в алгоритмах BFS и DFS или множество всех свободных мужчин в алгоритме устойчивых паросочетаний. Для этой цели естественно использовать для множества элементов представление связного списка, как это было сделано для множества свободных мужчин в алгоритме устойчивых паросочетаний.

Одним из важных аспектов такого представления является порядок рассмотрения элементов в таком списке. В алгоритме устойчивых паросочетаний порядок рассмотрения свободных мужчин не влиял на результат, хотя этот факт потребовал достаточно неочевидных доказательств. Во многих других алгоритмах (таких, как DFS и BFS) порядок рассмотрения элементов критичен.

Два простейших и самых естественных варианта организации множеств элементов — очередь и стек. Элементы очереди извлекаются в порядке “первым пришел, первым вышел” (FIFO, First-In, First-Out), то есть в том же порядке, в котором они добавлялись. Элементы стека извлекаются в порядке “последним пришел, первым вышел” (LIFO, Last-In, First-Out): при каждом извлечении выбирается элемент, который был добавлен последним. И очереди и стеки легко реализуются на базе двусвязного списка. В обоих случаях всегда выбирается первый элемент списка; отличается позиция вставки нового элемента. В очереди новый элемент добавляется в конец списка в последнюю позицию, а в стеке он размещается в первой позиции списка. Помните, что в двусвязном списке хранятся указатели First и Last на начало и на конец списка соответственно, поэтому в обоих случаях вставка выполняется за постоянное время.

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

Реализация поиска в ширину

Структура данных списка смежности идеально подходит для реализации поиска в ширину. Алгоритм поочередно проверяет ребра, выходящие из заданного узла. Когда мы проверяем ребра, выходящие из и, и добираемся до ребра (u, v), необходимо знать, был ли узел v обнаружен ранее в ходе поиска. Для упрощения этой задачи создается массив Discovered длины п, а при первом обнаружении v в процессе поиска присваивается значение Discovered[v] = true. Алгоритм, описанный в предыдущем разделе, строит из узлов уровни L₁, L₂, ..., где L_i — множество узлов, находящихся на расстоянии i от источника 5. Для хранения узлов уровня L_i создается список L[i] для всех i = 0, 1, 2, ....

В этой реализации несущественно, хранится каждый список L[i] в формате очереди или стека, поскольку алгоритму разрешено рассматривать узлы уровня L_i в произвольном порядке.

(3.11) Приведенная выше реализация алгоритма BFS выполняется за время O(m + n) (то есть в линейной зависимости от размера ввода), если граф описывается представлением списка смежности.

Доказательство. Для начала легко продемонстрировать для времени выполнения алгоритма ограничение O(n²) (более слабая граница, чем заявленная O(m + n)). Чтобы убедиться в этом, достаточно заметить, что достаточно создать максимум n списков L[i], а эта операция выполняется за время O(n). Теперь необходимо рассмотреть узлы и этих списков. Каждый узел входит не более чем в один список, поэтому цикл будет выполнен не более n раз по всем итерациям цикла Пока. Рассматривая узел и, необходимо просмотреть все ребра (u, v), инцидентные и. Таких ребер не больше n, и на каждое ребро тратится время O(1). Итак, общее время, затраченное на одну итерацию внутреннего цикла, не более O(n). Соответственно мы заключаем, что внутренний цикл состоит не более чем из n итераций, а каждая итерация выполняется за время не более O(n), так что общее время не превышает O(n²).

Чтобы прийти к усиленной границе O(m + n), следует увидеть, что внутренний цикл, обрабатывающий узел u, может выполняться за время меньше O(n) при небольшом количестве соседей у u. Как и прежде, n_u обозначает степень узла u, то есть количество ребер, инцидентных u. Время, потраченное во внутреннем цикле, в котором проверяются ребра, инцидентные u, составляет O(n_u), так что суммарное время по всем узлам составляет Вспомните из (3.9), что а общее время, потраченное на проверку ребер для всего алгоритма, составляет O(m). Дополнительное время O(n) понадобится для подготовки списков и управления массивом Discovered. Таким образом, общие затраты времени составляют O(m + n), как и утверждалось выше. ■

В нашем описании алгоритма упоминались n разных списков L[i] для каждого уровня L_i. Вместо нескольких разных списков можно реализовать алгоритм с одним списком L, который организован в формате очереди. В этом случае алгоритм обрабатывает узлы в том порядке, в котором они были изначально обнаружены; каждый обнаруженный новый узел добавляется в конец очереди, а алгоритм всегда обрабатывает ребра, выходящие из узла, который в настоящее время является первым в очереди.

Если хранить обнаруженные узлы в этом порядке, то все узлы уровня L_i+1 будут находиться в очереди до всех узлов уровня L_i+1 для i = 0, 1, 2... Следовательно, все узлы уровня L_i образуют непрерывную последовательность, за которой следуют все узлы уровня L_i+1, и т. д. Из этого вытекает, что такая реализация на базе одной очереди приводит к тому же результату, что и описанная ранее реализация BFS.

Реализация поиска в глубину

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

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

В алгоритме BFS, приступая к проверке узла и в уровне L, мы добавляли всех его вновь обнаруженных соседей в следующий уровень L_i+1, а непосредственная проверка этих соседей откладывалась до перехода к обработке уровня L_i+1. С другой стороны, алгоритм DFS действует более “импульсивно”: при проверке узла и он перебирает соседей и, пока не найдет первый непроверенный узел v (если он есть), после чего немедленно переключается на проверку v.

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

Также в этой реализации используется массив Explored, аналогичный массиву Discovered из реализации BFS. Различие заключается в том, что Explored[v] присваивается значение true только после перебора ребер, инцидентных v (когда поиск DFS находится в точке v), тогда как алгоритм BFS присваивает Discovered[v] значение true при первом обнаружении v. Полная реализация приведена ниже.

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

(3.12) Приведенный выше алгоритм реализует поиск DFS в том смысле, что он посещает узлы точно в таком же порядке, как и рекурсивная процедура DFS из предыдущего раздела (не считая того, что списки смежности обрабатываются в обратном порядке). Если мы хотим, чтобы алгоритм также строил дерево DFS, для каждого узла u в стеке S также должна храниться информация об узле, который “привел” к включению и в стек. Задача легко решается при помощи массива parent: при каждом добавлении узла v в стек из-за ребра (u, v) выполняется присваивание parent[v] = u. Когда узел u ≠ s помечается как “проверенный”, ребро (u,parent[u]) также можно добавить в дерево T. Учтите, что узел v может включаться в стек S многократно, поскольку он может быть смежным с несколькими проверяемыми узлами, и для каждого такого узла в стек S добавляется копия v. Однако для проверки узла v будет использоваться только одна из этих копий — та, которая была добавлена последней. В результате для каждого узла v достаточно хранить только одно значение parent[v], просто перезаписывая значение parent[v] при каждом добавлении в стек S новой копии v.

Основной фазой алгоритма является добавление и удаление узлов из стека S, которое выполняется за время O(1). Следовательно, чтобы определить границу времени выполнения, необходимо оценить количество таких операций. Чтобы подсчитать количество операций со стеком, достаточно подсчитать количество узлов, добавленных в S, так как для каждого удаления из S узел должен быть сначала добавлен.

Сколько элементов будет добавлено в S? Как и прежде, пусть n_v — степень узла v. Узел v будет добавляться в стек S каждый раз, когда проверяется один из п его смежных узлов, так что общее количество узлов, добавленное в S, не превышает Это доказывает искомую оценку O(m + N) для времени выполнения DFS.

(3.13) Для графа, заданного представлением списка смежности, приведенная выше реализация алгоритма DFS выполняется за время O(m + n) (то есть в линейной зависимости от размера входных данных).

Определение всех компонент связности

В предыдущем разделе говорилось о том, как использовать алгоритм BFS (или DFS) для поиска всех компонент связности в графе. Вы начинаете с произвольного узла s и используете BFS (или DFS) для построения его компоненты связности. Затем находится узел v (если он есть), который не был посещен при поиске от s, и алгоритм BFS (или DFS) начинает от узла v и генерирует его компоненту связности, — которая, согласно (3.8), будет изолирована от компоненты 5. Этот процесс продолжается до тех пор, пока не будут посещены все узлы.

Хотя ранее время выполнения BFS и DFS выражалось в виде O(m + n), где m и n — общее количество ребер и узлов в графе, фактически оба вида поиска — и BFS и DFS — работают только с ребрами и узлами компоненты связности, содержащей начальный узел. (Другие ребра и узлы им не видны.) Таким образом, приведенный выше алгоритм, хотя он и может выполнять BFS и DFSнесколько раз, выполняет постоянный объем работы для каждого конкретного узла или ребра в итерации для той компоненты связности, которой этот узел или ребро принадлежит. А следовательно, общее время выполнения алгоритма по-прежнему остается равным O(m + n).