Графики — один из самых распространенных вопросов, которые могут возникнуть в ходе технического собеседования, особенно в наши дни, когда многие реальные приложения могут быть представлены узлами и ребрами, такими как социальные сети!

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

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

Постановка задачи

Дана ссылка на узел в связном неориентированном графе. Вернуть глубокую копию графа.

class Node {
    public int val;
    public List<Node> neighbors;
}

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

Понимание проблемы

Было упомянуто несколько терминов, которые необходимо понять, чтобы решить проблему.

Предположим, что в неориентированном графе узел 1 указывает на узел 2. Это также подразумевает, что узел 2 также будет указывать на узел 1.

Другой тип графа — это ориентированныйграф, в котором, если узел 1 указывает на узел 2, это не обязательно означает, что узел 2 указывает обратно на узел 1.

Для нашего вывода мы хотим сделать глубокую копию графика. Глубокая копия означает, что мы создаем новый экземпляр узла с тем же значением и соседями, которые также являются глубокой копией. Это не позволяет нам просто вернуть данный узел.

Алгоритм высокого уровня

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

Есть компромиссы, которые можно использовать для обоих алгоритмов, но они реализованы почти одинаково. Для простоты мы собираемся решить эту проблему с помощью BFS.

На высоком уровне алгоритм BFS позволит нам сначала исследовать все соседние узлы, всех соседей нашего соседа и т. д., пока мы не исследуем каждый отдельный узел.

Алгоритм BFS требует двух вещей:

  1. Очередь для размещения наших узлов. Очередь следует политике «первым пришел — первым вышел», которая, как мы позже увидим, позволяет нам создать алгоритм BFS, обрабатывая в первую очередь наши соседние узлы. Это отличается от использования стека, который следует политике «первым пришел — последним обслужен», используемой для DFS.
  2. Посещенный Set для отслеживания узлов, которые мы посетили, чтобы мы не исследовали их снова, что особенно важно, поскольку графы могут формировать цикл, а наш алгоритм может работать вечно.

Обычно алгоритм BFS (или DFS) состоит из 3 шагов.

  1. Поместите данный начальный узел в очередь и посещенный набор
  2. Итерация по очереди очищается
  3. Извлеките узел из очереди, выполните итерацию по его дочерним элементам и добавьте их в посещенный набор и в очередь, если мы их раньше не видели.

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

Вот пример.

Дан небольшой граф из 4 узлов:.

На графике все эти узлы однонаправленные. Начнем с того, что поместим Node 1 в нашу очередь и посещенный набор:

Затем мы начнем обрабатывать нашу очередь

  • Удалить Node 1 из очереди и обработать его соседей: Node 2 и Node 4.
  • Поскольку мы раньше не видели ни одного из этих узлов, мы добавим их в нашу очередь и наш набор.

Продолжая, мы начинаем обрабатывать следующий узел в нашей очереди.

  • Убираем Node 2 из очереди и обрабатываем его соседей: Node 1 и Node 3.
  • Поскольку узел 1 находится в нашем посещенном наборе, мы не хотим повторно посещать его, однако мы добавим узел 3 в наш посещенный набор и в очередь.

Продолжая, мы будем:

  • Обработайте Node 4 и его соседи Node 1 и Node 3.
  • Оба соседа находятся в посещаемом наборе, поэтому мы не будем ставить их в очередь.

Примечание. Я также хочу отметить порядок обхода графа: мы начали с 1, затем перешли к его соседу 2, а затем перешли к другому соседу 4. Это как очередь позволяет нам запускать алгоритм BFS. Если мы хотим сделать DFS, мы будем использовать стек.

Наконец, чтобы завершить этот пример:

  • Удалите узел 3 из очереди, а затем посмотрите на его соседей: узел 2 и узел 4.
  • Оба находятся в посещаемом наборе, поэтому мы ничего не будем делать.

На данный момент наша очередь пуста, и мы завершили алгоритм BFS.

Адаптация алгоритма к задаче

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

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

Нам нужно отслеживать все созданные нами узлы, чтобы не создавать их заново. Для этого мы можем поместить их на карту, где мы используем значение узла в качестве ключа и глубокую копию в качестве значения.

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

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

Время выполнения и космическая сложность

Время выполнения

Время выполнения этого алгоритма составляет O(V + E),V представляет все узлы, которые мы посещаем, а E представляет все ребра, существующие между каждым узлом.

Примечание. Ребро — это связь между двумя узлами.

Космическая сложность

Наихудшая пространственная сложность этого алгоритма составляет O(N). Хотя наша очередь может хранить не все узлы в графе, наш посещенный набор будет хранить все, чтобы мы не обрабатывали один и тот же узел дважды.

Выполнение

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList();
        Map<Integer, Node> cloneMap = new HashMap();
        queue.add(node);
        cloneMap.put(node.val, new Node(node.val));
       
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
            Node clone = cloneMap.getOrDefault(cur.val, new Node(cur.val));
            cloneMap.put(cur.val, clone);
            for (Node child : cur.neighbors) {
                Node childClone = cloneMap.getOrDefault(child.val, new Node(child.val));
                clone.neighbors.add(childClone);
                if (!cloneMap.containsKey(child.val)) {
                    queue.add(child);
                }
                cloneMap.put(child.val, childClone);
            }
        }
        return cloneMap.get(node.val);
    }
}

Вывод

Ключевой урок, который следует извлечь из решения проблемы Clone Graph, заключается в том, чтобы знать, как применять алгоритм BFS.

Графические алгоритмы очень важно знать, потому что они часто используются в интервью. Они могут показаться пугающими, заставляя вас выяснять связи между несколькими точками данных.

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