Определение связности вершин графа 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Определение связности вершин графа



Поиск в глубину в графе.

Существует много алгоритмов на графах, в основе которых ле­жит систематический перебор вершин графа, такой, что каждая вершина просматривается точно один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе. Какой метод считается хорошим. Отметим два признака хорошего метода поиска:

1 - метод позволяет легко вставить себя в алгоритм нашей задачи;

2 - каждое ретро графа анализируется не более одного раза (или число раз, ограниченное константой).

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

Общая идея метода. Поиск начинается с некоторой фиксированной вершины V o. Затем выбираем некоторую вершину Vi смежную с V o и повторяем процесс от Vi.

В общем случае предположим, что мы находимся в вершине Vk. В стеке хранится список вершин через которые мы попали в Vk. Если существует новая (которой еще нет в стеке и не Vk) непросмотренная вершина, то Vk помещается в стек, поиск ведется далее от новой вершины, которая перестает быть новой. Если же не существует ни одной новой вершины, смежной с Vk, то мы считаем, что вершина Vk использована, возвращаемся в вершину, из которой мы попали в Vk и продолжаем процесс. В ходе процесса будет формироваться список использованных вершин. Окончание процесса произойдет тогда, когда мы вернемся в вершину V o и отметим ее как использованную. Другими словами, поиск в глубину из вершины V o основывается на поиске в глубину из всех новых вершин, смежных с V o. Данный алгоритм просматривает каждую вершину в точности один раз и его сложность порядка К ·(n + m), где К - некоторая константа, выражающая сложность внутреннего алгоритма просмотра очередной вершины.

Рассмотрим произвольный граф.

Рис. 5.11

Проведем поиск в глубину по вышеизложенному алгоритму. Поиск начнем с вершины V 1. Слева будем изображать стек, справа список использованных вершин.

Стек

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 = 1 конец

Список связных вершин 1 2 3 4 5 6 7.

Методика поиска в глубину очевидным образом переносится на ориентированные графы. Нетрудно проверить, что в случае ориентированного графа за К ·(n + m) шагов можно посетить все вершины Vi такие, что существует путь из V o в Vi.

Рис. 5.12

Поиск начинаем с вершины 2.

Стек

2 новая вершина 3

23 новая вершина 6

236 новая вершина 5

2365 новых вершин нет вершина 5 использована

236 новых вершин нет вершина 6 использована

23 новых вершин нет вершина 3 использована

2 новая вершина 4

24 новых вершин нет вершина 4 использована

2 новых вершин нет вершина 2 использована

2 = 2 конец.

Список связанных с 2 вершин - 2 3 4 5 6.

Отметим в заключение, что чем позднее будет посещена вершина, тем раньше она будет отмечена, как использованная.

Поиск в ширину в графе.

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

Процесс начинается с вершины V o - она тут же считается использованной. Далее ищутся все вершины, связанные с V o и они тут же считаются использованными. После этого делается третий шаг поиска. При этом использованными считаются только новые вершины, то есть те, которых нет в списке уже использованных. Процесс прекращается, когда на очередном шаге не находится ни одна новая вершина. Если метод поиска в глубину позволяет отыскать путь от V o к искомой вершине (путь к вершине Vk находится в стеке, как только вершина Vk встретилась), то метод поиска в ширину позволяет отыскать кратчайший путь по количеству входящих в него ветвей.

Дан произвольный граф.

 

Рис. 5.13

 

Vo = 1

1 использована 1

2 3 5 использована 1 2 3 5

4 8 6 использована 1 2 3 5 4 8 6

7 10 9 использована 1 2 3 4 5 6 7 8 9 10

Новых нет - конец

Данный алгоритм анализирует каждую вершину в точности один раз. Сложность его такая же К ·(m + n). Данный метод также легко применяется к ориентированным графам.

Очередь (просмотр с вершины 1) по шагам:

Очередь№шага

1 _1 - в очередь поставлена 1 вершина;

235 2 - 1я вершина обслужена;

4 3 - 2я вершина обслужена;

6 4 - 3я вершина обслужена;

8 5 - 5я вершина обслужена;

7 6 - 4я вершина обслужена;

9 7 - 6я вершина обслужена;

10 8 - 8я вершина обслужена;

9 - 7я вершина обслужена;

10 - 9я вершина обслужена;

11 -10я вершина обслужена.

 

При обслуживании вершин 7, 9, 10 новых (необслуженных) вершин не обнаружено.

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

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

Вот почему не всегда ясные и понятные человеку алгоритмы дают оптимальные решения. Использование ЭВМ позволяет устранить некоторые недостатки человеческой памяти и довольно просто получать оптимальные решения, правда в этом случае платой является более высокий уровень искусства программирования.

Метод построения дерева путей.

Еще одним методом определения связности вершин графа является метод построения дерева путей. Он также может в дальнейшем применятся для нахождения кратчайших путей в графе.

Построение дерева путей ведется по следующему алгоритму.

1. Корню дерева путей, образованному узлом-источником, присваивается нулевой уровень.

2. Из корня дерева путей строятся ветви первого уровня, на концах которых помещаются узлы первого уровня, непосредственно связанные в графе с узлом-источником.

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

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

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

Рассмотрим пример.

Задан граф G рис. 5.14.

Рис. 5.14

Рис. 5.15.

При решении задачи определения связности вершин графа методом построения дерева путей с помощью ЭВМ удобно задавать топологическую структуру графа матрицей смежности. Узлы графа, включаемые в k -й уровень дерева путей, для которых узел i является корневым, выявляются при анализе содержимого i -строки матрицы смежности. При этом номера столбцов матрицы смежности, в которых на i -ой строке записаны единицы, и будут равны номерам узлов графа, включаемых в k -й очередной уровень дерева путей. Но при этом, перед включением каждого очередного узла в k -й уровень дерева путей необходимо еще проверить дополнительное условие на отсутствие этого узла среди предшествующих узлов образуемого пути.

Для нашего примера построим матрицу смежности.

Для построения первого уровня дерева путей выявляем по матрице U смежности узлы графа, непосредственно связанные с узлом источником 1. Для этого требуется проанализировать содержимое первой строки матрицы смежности. Узлами включаемыми в первый уровень дерева путей будут узлы 2,3,5,6, так как в столбцах этих матриц записаны единицы.

Множества узлов графа, включаемых во второй уровень дерева путей, размещаемых на концах ветвей, исходящих из узлов 2,3,5,6 определяются при анализе содержимого соответственно 2,3,5,6 строк матрицы смежности. Дерево путей, исходящих из узла 1 будет иметь вид, показанный на рис.5.15.



Поделиться:


Последнее изменение этой страницы: 2017-02-08; просмотров: 1406; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.192.53.34 (0.156 с.)