При решении ряда практических задач на информационных сетях возникает необходимость определения возможности передать информацию в тот или иной узел назначения. Причём речь не идет о выборе самого пути передачи. В этом случае достаточно определить связность узлов сети. Для этого можно воспользоваться методами определения связности вершин графа. Две вершины графа называются связными, если существует путь их соединяющий. Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа. Рассмотрим некоторые из них.
Поиск в глубину в графе
Рассмотрим метод поиска в неориентированном графе, который применяется наиболее широко и называется поиском в глубину.
Общая идея метода. Поиск начинается с некоторой фиксированной вершины Vo. Затем выбираем некоторую вершину Vi cмежную с Vo и повторяем процесс от Vi.
В общем случае предположим, что мы находимся в вершине Vk. В стеке, наряду с Vk, хранится список вершин через которые мы попали в Vk. Если существует новая (которой еще не было в стеке) не просмотренная вершина Vl, то Vl помещается в стек, и поиск ведется далее от Vl, которая перестает быть новой. Если же не существует ни одной новой вершины, смежной с Vk, то мы считаем, что вершина Vk использована (помещаем её в список использованных вершин), возвращаемся в вершину, из которой мы попали в Vk и продолжаем процесс. В ходе процесса будет формироваться список использованных вершин. Окончание процесса произойдет тогда, когда мы вернемся в вершину Vo и отметим ее как использованную. Другими словами, поиск в глубину из вершины Vo основывается на поиске в глубину из всех новых вершин, смежных с Vo. Данный метод просматривает каждую вершину в точности один раз и его вычислительная сложность порядка k(n+m), где k - некоторая константа, выражающая сложность внутреннего алгоритма просмотра очередной вершины.
Представим более подробный алгоритм поиска в глубину.
1. Начальную вершину S помещаем в стек.
2. Определяем новую вершину смежную с S, если такой нет, то поиск закончен; вершина S не связана ни с какой другой вершиной графа; если S смежна с некоторой вершиной vi, то vi помещаем в стек.
3. Определяем новую вершину, смежную с последней вершиной, занесенной в стек. Если новая вершина есть, то заносим её в стек и повторяем п.3 от неё, иначе - вершину, занесенную в стек последней считаем использованной и перемещаем её из стека в список использованных вершин, а поиск продолжаем из крайней вершины стека.
4. Выполняем п.3 до тех пор, пока из стека в список использованных вершин не перейдёт начальная вершина S.
В списке использованных вершин содержатся вершины связные с начальной вершиной S.
Рассмотрим произвольный граф (рис.2.12).
Рисунок 2.12 – Неориентированный граф
Проведем поиск в глубину по вышеизложенному алгоритму. Поиск начнем с вершины V1. Слева будем изображать стек, справа список использованных вершин.
Стек
1 новая вершина 3
13 новая вершина 6
136 новая вершина 7
1367 новая вершина 4
13674 новых вершин нет вершина 4 использована
1367 новых вершин нет вершина 7 использована
136 новая вершина 5
1365 новая вершина 2
13652 новых вершин нет вершина 2 использована
1365 новых вершин нет вершина 5 использована
136 новых вершин нет вершина 6 использована
13 новых вершин нет вершина 3 использована
1 новых вершин нет вершина 1 использована
конец
Список связных с 1 вершин {2, 3, 4, 5, 6, 7}.
Методика поиска в глубину очевидным образом переносится на ориентированные графы. Нетрудно проверить, что в случае ориентированного графа за k(n+m) шагов можно посетить все вершины Vi такие, что существует путь из S в Vi.
Рассмотрим пример. Граф представлен на рис.2.13. Начальная вершина S=2.
Рисунок 2.13 – Ориентированный граф
Поиск начинаем с вершины 2.
Стек
2 новая вершина 3
23 новая вершина 6
236 новая вершина 5
2365 новых вершин нет вершина 5 использована
236 новых вершин нет вершина 6 использована
23 новых вершин нет вершина 3 использована
2 новая вершина 4
24 новых вершин нет вершина 4 использована
2 новых вершин нет вершина 2 использована
конец.
Список связанных с 2 вершин - {3, 4, 5, 6}.
Отметим в заключение основную особенность метода: чем позднее будет посещена вершина, тем раньше она будет отмечена, как использованная.
Поиск в ширину в графе
Рассмотрим иной метод поиска называемый поиском в ширину. В отличие от предыдущего метода здесь вершина считается использованной, как только она встречается и просматривается не одна, а сразу все смежные вершины. Прежде чем описать его, отметим, что при поиске в глубину чем позднее будет посещена вершина, тем раньше она будет использована - точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины скапливаются в стеке. Поиск в ширину грубо говоря, основывается на замене стека очередью. После такой модификации чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще не просмотренных соседей этой вершины.
Процесс начинается с вершины S - она тут же считается использованной. Далее ищутся все вершины, связанные с S и они тут же считаются использованными. После этого делается третий шаг поиска. При этом использованными считаются только новые вершины, то есть те, которых нет в списке уже использованных. Процесс прекращается, когда в очереди побывают все вершины из списка использованных вершин. Если метод поиска в глубину позволяет отыскать путь от S к искомой вершине (путь к вершине Vk находится в стеке, как только вершина Vk встретилась), то метод поиска в ширину позволяет отыскать кратчайший путь по количеству входящих в него ребер.
Алгоритм поиска в ширину
1. Начальную вершину S помещаем в очередь.
2. Определяем новые вершины смежные с S, если таких нет, то поиск закончен; вершина S не связана ни с какой другой вершиной графа; если же S смежная с некоторыми вершинами vi,…, vj, то вершину S считаем использованной, а вершины vi,…, vj, смежные с S считаются новыми и сразу становятся использованными, после чего вершины S, vi,…, vj помещаем в список новых и использованных вершин.
3. Из списка использованных вершин выбирается следующая за S вершина vi и помещается в очередь. Определяются смежные с ней новые вершины (которых нет в списке использованных вершин) и помещаются в список новых и использованных вершин, если новых смежных вершин нет, то п.4.
4. В очередь помещается следующая вершина из списка использованных вершин, для которой выполняются действия, аналогичные п.3.
5. Поиск заканчивается тогда, когда в очереди будут просмотрены все вершины из списка использованных вершин.
Пример. Дан произвольный граф рис.2.14.
Рисунок 2.14 – Граф для поиска в ширину
| Очередь | Новые вершины | Использованные вершины |
| 2, 3, 5 | 1, 2, 3, 5 | |
| нн | ||
| нн | ||
| Нн |
Список связанных с 1 вершин {2,3,4,5,6,7,8,9,10}.
Данный алгоритм анализирует каждую вершину в точности один раз. Сложность его такая же k(m+n). Данный метод также применяется к ориентированным графам при этом обязательно учитывается направление дуг.
Проанализируем рассмотренные алгоритмы с точки зрения их возможностей и сложности программной реализации. Поиск в глубину в графе помимо определения связности вершин графа позволяет легко определить путь из одной вершины в другую, однако решение полученное этим методом, в общем случае, не является оптимальным (по количеству ребер пути) поэтому применяют его для этих целей тогда, когда важно получить хоть какой-либо результат.
Кроме того, по сравнению с другими методами его легче реализовать в виде программ и легче интерпретировать результаты, так как в стеке обычно содержится меньше узлов, и они связаны тем порядком, в котором записывались, а не явными указателями. Этот метод выглядит психологически более естественным, так как из-за весьма ограниченного объема человеческой памяти для оперативной информации люди используют те стратегии решения задач, которые не требуют одновременного запоминания многих фактов, что делает более привлекательным метод поиска в глубину (попробуйте быстро определить путь в графе при использовании метода поиска в ширину!)
При игре в шахматы (которую можно сформулировать как задачу поиска на графе) очень хорошие игроки пользуются модифицированным методом поиска в глубину. Проводились эксперименты, в которых испытуемым задавались в явном виде задачи поиска на графе и предлагалось решить их рассмотренными методами. Метод поиска в глубину не вызывал особых затруднений, тогда как при использовании метода поиска в ширину при выполнении довольно простых заданий возникали трудности.
Вот почему не всегда ясные и понятные человеку алгоритмы дают оптимальные решения. Использование ЭВМ позволяет устранить некоторые недостатки человеческой памяти и довольно просто получать оптимальные решения, правда в этом случае платой является более высокий уровень искусства программирования.
Построение дерева путей
Еще одним методом определения связности вершин графа является метод построения дерева путей, который кроме решения задачи связности позволяет найти все возможные пути от некоторой начальной вершины в графе, что расширяет круг задач, решаемых данным методом особенно для различных комбинаторных задач. Также метод может применятся для нахождения кратчайших путей по числу ребер в пути.
Построение дерева путей ведется по следующему алгоритму.
1. Корню дерева путей, образованному начальной вершиной, присваивается нулевой уровень.
2. Из корня дерева путей строятся ветви первого уровня, на концах которых помещаются вершины первого уровня, непосредственно связанные в графе с начальной вершиной.
3. Ветви второго уровня дерева путей строят из вершин, находящихся на первом уровне дерева, являющихся для этих ветвей корневыми. При этом из каждой вершины первого уровня дерева путей выходит столько ветвей, со сколькими вершинами графа смежна данная вершина первого уровня, исключая начальную вершину.
4. Строятся ветви и вершины третьего и последующих уровней аналогично пункту 3. При этом всякая вершина графа может включаться в очередной уровень дерева путей, если эта вершина в соответствующем образующемся пути ранее не встречалась.
5. Построение дерева путей заканчивается тогда, когда в каждом пути будут охвачены все связи в графе. Как правило, в неориентированном графе это означает, что в каждом пути будут содержаться все узлы.
Рассмотрим пример.
Задан неориентированный граф G рис.2.15. Начальная вершина 1.
Рисунок 2.15 – Неориентированный граф
| 0 уровень |
| 3 уровень |
| 2 уровень |
| 1 уровень |
| 5 уровень |
| 4 уровень |
Рисунок 2.16 – Дерево путей
Дерево путей представлено на рис.2.16. Оно показывает все возможные пути от начальной вершины к остальным вершинам графа. Кратчайшим путем от начальной к заданной конечной вершине будет тот путь, в котором конечная вершина встречается на более низком уровне дерева путей. Так от 1 вершины к 4 вершине кратчайшим будет путь 1-2-4, так как вершина 4 впервые встречается на 2 уровне. Кроме этого между 1 и 4 вершинами есть ещё 5 путей.
При решении задачи определения связности вершин графа методом построения дерева путей с помощью ЭВМ топологическую структуру графа удобно задавать матрицей смежности или списком смежности. Вершины графа, включаемые в k-й уровень дерева путей, для которых вершина i является корневой, выявляются при анализе содержимого i-строки матрицы смежности или списка смежности. При этом номера столбцов матрицы смежности, в которых на i-ой строке записаны единицы, и будут равны номерам вершин графа, включаемых в k-й очередной уровень дерева путей. Но при этом, перед включением каждой очередной вершины в k-й уровень дерева путей необходимо еще проверить дополнительное условие на отсутствие этой вершины среди предшествующих вершин образуемого пути.