Алгоритмы обхода графов на Python и C#

Если вы во время учебы в институте пренебрегали теорией графов, то зря. Ибо граф – это замечательная абстракция, к которой можно свести много различных задач и решить их через алгоритмы на графах. К графам сводятся не только задачи транспортной логистики. В виде графа можно представить, например, компьютерную сеть, сеть социальных контактов, да и вообще различные взаимоотношения между людьми, а так же многие другие задачи, которые можно решить программированием на языках C# и Python. В частности, задачу паросочетаний можно представить в виде двудольного графа:

А теперь рассмотрим практический пример. Допустим, у нас есть вот такой вот граф:

Вершины графа могут быть закодированы как буквами, так и цифрами. Цифрами – удобнее, так как они могут быть индексами, по которыми мы можем обраться к определённой вершине. Давайте это проверим. В нашем примере мы назначим буквам соответствующую цифру и построим такой граф (пример на Python):

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

Как обратиться к конкретной вершине? По номеру, вот так, например, проверить, ведет ли ребро из одной вершины (a) к другой вершине (b)

Степень вершины мы можем узнать, просто посмотрев размер множества исходящих из нее рёбер, вот так:

Теперь попробуем реализовать алгоритм обхода графа в ширину. Вот шаги этого алгоритма:

  1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
  2. Извлечь из начала очереди узел u {\displaystyle u} u и пометить его как развёрнутый.
    • Если узел u {\displaystyle u} u является целевым узлом, то завершить поиск с результатом «успех».
    • В противном случае, в конец очереди добавляются все преемники узла u {\displaystyle u}u, которые ещё не развёрнуты и не находятся в очереди.
  3. Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
  4. Вернуться к п. 2.

 

Вот пример реализации данного алгоритма на Python

Алгоритм обхода графа в ширину (не обязательно это поиск) мы можем использовать, когда надо раскрыть все вершины графа последовательно, уровень за уровнем. То есть, сначала мы раскрываем вершины первого уровня, затем второго и так далее. Вот как это выгляди на практике:

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

А теперь для разнообразия попробуем реализовать этот алгоритм на языке C#. Для начала объявим класс узла (вершины):

Для удобства программирования создадим еще и класс Graph, который инкапсулирует в себя описание графа.

В качестве примера вот такой граф:

Закодируем его:

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

Выведем полученное дерево в TreeVeiw:

И вот что в итоге у нас получается:

Теперь поговорим о том, в каком случае какой алгоритм использовать. Если мы предполагаем, что искомая вершина может находиться достаточно далеко от той, с которой мы начинаем поиск (предполагается, что будет много уровней), то лучше использовать алгоритм поиска в глубину. Если мы знаем, что вершина будет где-то близко, на верхних уровнях дерева раскрытия вершин, то лучше использовать алгоритм поиска в ширину. Но, ни в коем случае не используйте алгоритм поиска в ширину, если у вас потенциально может быть очень много уровней – алгоритм может «повеситься».

 

Comments

So empty here ... leave a comment!

Добавить комментарий

Sidebar