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

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

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

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

a, b, c, d, e, f, g, h = range(8)
N = [
{b, c, d, e, f}, # a
{c, e}, # b
{d}, # c
{e}, # d
{f}, # e
{c, g, h}, # f
{f, h}, # g
{f, g} # h
]

print(b in N[a])
print(len(N[f]))

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

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

print(b in N[a])

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

print(len(N[f]))

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

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

 

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

a, b, c, d, e, f, g, h = range(8)
N = [
   {b, c, d, e, f}, # a
   {c, e}, # b
   {d}, # c
   {e}, # d
   {f}, # e
   {c, g, h}, # f
   {f, h}, # g
   {f, g} # h
]

#импортируем класс очереди
from queue import Queue

#соответсвие цифры букве
letters="abcdefgh"
visited_nodes={}

#Начальные переменные
queue=Queue()
beg_node=a
target_node=h

#шаг 1.    Поместить узел, с которого начинается поиск, в изначально пустую очередь.
queue.put(beg_node)
visited_nodes={beg_node}

# это у нас цикл с постусловием
while True:
   #шаг 2. Извлечь из начала очереди узел "u" и пометить его как развёрнутый.
   u=queue.get()
   print("Обходим узел",letters[u])

   #Если узел "u" является целевым узлом, то завершить поиск с результатом «успех».
   if u==target_node:
      print("Поиск успешно завершен")
      break
   else:
      #В противном случае, в конец очереди добавляются все преемники узла "u", которые ещё не развёрнуты и не находятся в очереди.
      for node in N[u]:
         print(" -- Смотрим ребро", letters[node])
         if not(node in visited_nodes):
            print("   ---- Узел", letters[node],"добавили в очередь")
            visited_nodes.add(node)
            queue.put(node)

   #шаг 3.    Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел
   # недостижим из начального; завершить поиск с результатом «неудача».
   if queue.empty():
      print("Вершина ",letters[u]," не найдена")

   #шаг 4. Вернуться к п. 2.

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

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

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

    /// <summary>
    /// Вершина графа
    /// </summary>
    public class Node
    {
        /// <summary>
        /// Номер вершины
        /// </summary>
        public int vertex_number;

        /// <summary>
        /// Список вершин, в которые ведут ребра из этой вершины
        /// </summary>
        public List<Node> vertex_edges;

        /// <summary>
        /// Дополнительная информация
        /// </summary>
        public object tag;

        /// <summary>
        /// Конструктор
        /// </summary>
        /// <param name="a_vertex_number">Номер вершины</param>
        public Node(int a_vertex_number)
        {
            vertex_edges = new List<Node>();
            vertex_number = a_vertex_number;
        }
    }

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

    /// <summary>
    /// Граф
    /// </summary>
    public class Graph
    {
        /// <summary>
        /// Узлы графа
        /// </summary>
        public List<Node> nodes;

        /// <summary>
        /// Конструктор
        /// </summary>
        public Graph()
        {
            nodes = new List<Node>();
        }

        /// <summary>
        /// Инициализация вершин
        /// </summary>
        /// <param name="count">Кол-во вершин</param>
        public void init(int count)
        {
            for (int i = 1; i <= count; i++) nodes.Add(new Node(i));
        }

        /// <summary>
        /// Добавить ребро
        /// </summary>
        /// <param name="a_vertex_number_form">Из какой вершины исходит</param>
        /// <param name="a_vertex_number_to">В какую вершину ведет</param>
        public void add(int a_vertex_number_from, int a_vertex_number_to)
        {
            nodes[a_vertex_number_from - 1].vertex_edges.Add(nodes[a_vertex_number_to - 1]);
        }

        /// <summary>
        /// Сбросить метки узлов
        /// </summary>
        public void reset_tags()
        {
            foreach(Node node in nodes) node.tag = null;
        }
    }

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

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

            graph = new Graph();
            graph.init(8);
            graph.add(1, 2);
            graph.add(2, 3);
            graph.add(2, 4);
            graph.add(2, 5);
            graph.add(3, 1);
            graph.add(4, 1);
            graph.add(4, 6);
            graph.add(4, 8);
            graph.add(5, 6);
            graph.add(6, 7);
            graph.add(7, 5);
            graph.add(8, 6);

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

        /// Построить дерево обхода в глубину
        /// </summary>
        /// <param name="a_vertex_number">Начальный номер вершины</param>
        /// <param name="start">Это стартовая точка</param>
        /// <returns>Результатирующее дерево</returns>
        public List<Node> dfs_tree(int a_vertex_number, bool start)
        {
            List<Node> res = new List<Node>();
            Node node = nodes[a_vertex_number - 1];
            if (node.tag != null) return new List<Node>();
            node.tag = true;
            List<Node> additig_list = null;
            if (start)
            {
                Node root_item = new Node(a_vertex_number);
                res.Add(root_item);
                additig_list = root_item.vertex_edges;
            }
            else
            {
                additig_list = res;
            }
            foreach (Node item in node.vertex_edges)
            {
                if(item.tag==null)
                {
                    Node adding_item = new Node(item.vertex_number);
                    adding_item.vertex_edges = dfs_tree(item.vertex_number,false);
                    additig_list.Add(adding_item);
                }
            }            
            return res;
        }

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

        private void btnDfs_Click(object sender, EventArgs e)
        {
            graph.reset_tags();
            List<Node> tree = graph.dfs_tree(1,true);
            tvDfs.Nodes.Clear();
            draw_tree(tree, tvDfs.Nodes);
        }

        /// <summary>
        /// Вывести дерево
        /// </summary>
        /// <param name="tree">Дерево</param>
        /// <param name="tree_nodes">Узлы визуального дерева</param>
        private void draw_tree(List<Node> tree, TreeNodeCollection tree_nodes)
        {
            foreach(Node node in tree)
            {
                TreeNode tree_node = new TreeNode(node.vertex_number.ToString());
                tree_nodes.Add(tree_node);
                if (node.vertex_edges.Count > 0) draw_tree(node.vertex_edges, tree_node.Nodes);
            }
        }

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

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

 

Comments

So empty here ... leave a comment!

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

Sidebar