ИТ Блог. Администрирование серверов на основе Linux (Ubuntu, Debian, CentOS, openSUSE)

Основные графовые алгоритмы встречаются на собеседованиях по программированию

Основные графовые алгоритмы встречаются на собеседованиях по программированию

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

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

 

1. Поиск в глубину (DFS)

Поиск в глубину (DFS)

Поиск в глубину (DFS)

 

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

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

DFS особенно полезен в таких сценариях, как:

 

Как работает DFS:

 

Реализация:

Рекурсивная DFS: использует системную рекурсию (стек вызовов функций) для возврата к предыдущему состоянию.

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(f"Посещение {node}")
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

 

Объяснение:

 

Итеративная DFS: использует явный стек для имитации поведения при вызове функции.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(f"Посещение {node}")
            # Добавление соседей в стек
            stack.extend([сосед за соседом в graph[node] если сосед не в гостях])
    return visited

 

Объяснение:

 

Временная сложность: O(V + E), где V — количество вершин, а E — количество рёбер. Это связано с тем, что алгоритм посещает каждую вершину и каждое ребро по одному разу.

Сложность по памяти: O(V), из-заиспользования стека для рекурсии (при рекурсивной реализации) или явного стека (при итеративной реализации).

 

2. Поиск по ширине (BFS)

Поиск по ширине (BFS)

Поиск по ширине (BFS)

 

BFS — это фундаментальный алгоритм обхода графа, который систематически исследует вершины графа уровень за уровнем.

Начиная с выбранного узла, BFS сначала посещает все его непосредственные соседние узлы, а затем переходит к соседним узлам этих соседних узлов. Это гарантирует, что узлы будут исследованы в порядке их удалённости от начального узла.

BFS особенно полезен в таких сценариях, как:

 

Как работает BFS:

  1. Инициализация: создайте очередь и поместите в неё начальный узел.
    • Отметьте начальный узел как посещенный.
  2. Цикл обхода: Пока очередь не пуста:
    • Удаление узла из очереди в начале очереди.
    • Посетите всех непрошеных соседей:
      • Отметьте каждого соседа как посещенного.
      • Поставьте соседа в очередь.
  3. Завершение: Алгоритм завершается, когда очередь пуста, то есть все достижимые узлы посещены.

 

Реализация:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(f"Посещение {vertex}")
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

 

Временная сложность: O(V + E), где V — количество вершин, а E — количество рёбер. Это связано с тем, что BFS посещает каждую вершину и ребро ровно один раз.

Сложность по памяти: O(V)для очереди и набора посещённых элементов, используемых для обхода.

 

3. Топологическая сортировка

Топологическая сортировка

Топологическая сортировка

 

Алгоритм топологической сортировки используется для упорядочивания вершин ориентированного ациклического графа (DAG) в линейной последовательности таким образом, что для каждого направленного ребра u → v вершина u предшествует вершине v в порядке следования.

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

Топологическая сортировка особенно полезна в таких сценариях, как:

 

Существует два распространенных метода выполнения топологической сортировки:

1. Алгоритм, основанный на поиске в глубину (DFS):

def topological_sort_dfs(graph):
    visited = set()
    stack = []

    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(vertex)

    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    return stack[::-1]  # Переверните стопку, чтобы получить правильный порядок

 

Объяснение:

 

2. Топологическая сортировка на основе BFS (алгоритм Кана):

from collections import deque

def topological_sort_kahn(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] = in_degree.get(v, 0) + 1

    queue = deque([u for u in in_degree if in_degree[u] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(topo_order) == len(in_degree):
        return topo_order
    else:
        raise Exception("График имеет по крайней мере один цикл")

 

Объяснение:

 

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

Сложность по пространству: O(V) для хранения топологического порядка и вспомогательных структур данных, таких как множество посещённых вершин или массив степеней.

 

4. Поиск объединения

Поиск объединения

Поиск объединения

 

Объединение в группу — это структура данных, которая отслеживает набор элементов, разделённых на непересекающиеся (не имеющие общих элементов) подмножества.

Он поддерживает две основные операции:

  1. Поиск (Find-Set): Определяет, к какому подмножеству относится конкретный элемент. Это можно использовать для проверки, находятся ли два элемента в одном подмножестве.
  2. Объединение: объединяет два подмножества в одно, фактически соединяя два элемента.

 

Поиск обьединения особенно полезен в таких сценариях, как:

 

Как работает Union Find:

Структура данных Union Find обычно состоит из:

  1. Родительский массив (parent): Массив, в котором parent[i] хранится родительский элемент i. Изначально каждый элемент является своим собственным родителем.
  2. Массив рангов (rank): Массив, который приблизительно соответствует глубине (или высоте) дерева, представляющего каждый набор. Используется для оптимизации объединений.

 

Операции:

 

Реализация:

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]  # Изначально каждый узел является своим собственным родительским узлом
        self.rank = [0] * size  # Ранг (глубина) каждого дерева

    def find(self, x):
        if self.parent[x] != x:
            # Сжатие контура: сглаживание дерева
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Найдите корни множеств, содержащих x и y
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            # Уже в том же наборе
            return

        # Объединение по рангу: прикрепите меньшее дерево к корню большего дерева
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_y] < self.rank[root_x]:
            self.parent[root_y] = root_x
        else:
            # Ранги равны; выберите один из них в качестве нового корня и увеличьте его ранг
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

 

Временная сложность каждой операции:

 

5. Обнаружение циклов

Обнаружение циклов

Обнаружение циклов

 

Обнаружение циклов заключается в определении того, содержит ли граф циклы — пути, в которых первая и последняя вершины совпадают, а рёбра не повторяются.

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

Обнаружение цикла особенно важно в таких сценариях, как:

 

Существуют различные подходы к обнаружению циклов в графах:

Обнаружение циклов в неориентированных графах с использованием DFS:

def has_cycle_undirected(graph):
    visited = set()

    def dfs(vertex, parent):
        visited.add(vertex)
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif neighbor != parent:
                return True  # Обнаружен цикл
        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, None):
                return True
    return False

 

Объяснение:

 

Обнаружение циклов в ориентированных графах с использованием DFS:

def has_cycle_directed(graph):
    visited = set()
    recursion_stack = set()

    def dfs(vertex):
        visited.add(vertex)
        recursion_stack.add(vertex)
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in recursion_stack:
                return True  # Обнаружен цикл
        recursion_stack.remove(vertex)
        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex):
                return True
    return False

 

Объяснение:

 

Обнаружение цикла с помощью Union-Find (неориентированные графы):

class UnionFind:
    def __init__(self):
        self.parent = {}

    def find(self, x):
        # Сжатие пути
        if self.parent.get(x, x) != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent.get(x, x)

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # Обнаружен цикл
        self.parent[root_y] = root_x
        return True

def has_cycle_union_find(edges):
    uf = UnionFind()
    for u, v in edges:
        if not uf.union(u, v):
            return True
    return False

 

Объяснение:

 

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

Сложность по памяти: O(V) для набора посещенных вершин и стека рекурсии в DFS.

 

6. Связанные компоненты

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

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

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

 

Как найти связанные компоненты:

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

Идея состоит в том, чтобы:

  1. Инициализировать:
    • Создайте набор visited для отслеживания посещенных узлов.
    • Инициализируйте список components для хранения каждого подключенного компонента.
  2. Обход:
    • Для каждого непросмотренного узла выполните DFS или BFS.
    • Отметьте все доступные узлы из этого узла как часть одного и того же компонента.
    • Добавьте компонент в список components.
  3. Повторение:
    • Продолжайте процесс до тех пор, пока не будут посещены все узлы.

 

Реализация:

def connected_components(graph):
    visited = set()
    components = []

    def dfs(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor, component)

    for node in graph:
        if node not in visited:
            component = []
            dfs(node, component)
            components.append(component)

    return components

 

Объяснение:

 

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

Сложность по памяти: O(V) из-за набора visited и стека рекурсии (в DFS) или очереди (в BFS).

 

Сильно связанные компоненты в ориентированных графах:

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

Шаги алгоритма Косараджу:

  1. Первый проход: Выполните DFS на исходном графе, чтобы вычислить время завершения работы каждого узла.
  2. Транспонировать граф: изменить направление всех ребер на обратное.
  3. Второй проход: Выполните DFS на транспонированном графе в порядке убывания времени завершения первого прохода.
  4. Результат: каждый обход DFS во втором проходе идентифицирует сильно связанный компонент.

 

7. Двудольные графы

Двудольные графы

Двудольные графы

 

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

Другими словами, никакое ребро не соединяет вершины в пределах одного набора.

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

 

Свойства двудольных графов:

 

Как проверить, является ли граф двудольным:

Мы можем определить, является ли граф двудольным, попытавшись раскрасить его двумя цветами, не присваивая один и тот же цвет смежным вершинам. Если это удалось, то граф является двудольным.

Это можно сделать с помощью:

 

Реализация с использованием BFS

from collections import deque

def is_bipartite(graph):
    color = {}
    for node in graph:
        if node not in color:
            queue = deque([node])
            color[node] = 0  # Назначьте первый цвет
            while queue:
                current = queue.popleft()
                for neighbor in graph[current]:
                    if neighbor not in color:
                        color[neighbor] = 1 - color[current]  # Назначьте противоположный цвет
                        queue.append(neighbor)
                    elif color[neighbor] == color[current]:
                        return False  # Соседние узлы имеют одинаковый цвет
    return True

 

Объяснение:

 

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

Сложность по памяти: O(V) из-за набора color и стека рекурсии (в DFS) или очереди (в BFS).

 

8. Заливка флудом

Заливка — это алгоритм, который определяет и изменяет область, связанную с заданным узлом в многомерном массиве.

Начиная с начальной точки, он находит или заполняет (или перекрашивает) все связанные пиксели или ячейки с одинаковым цветом или значением.

Как работает заливка флудом:

  1. Начальная точка: начните с начального пикселя (начальных координат).
  2. Проверьте цвет: если цвет текущего пикселя совпадает с целевым цветом (который нужно заменить), продолжайте.
  3. Замените цвет: измените цвет текущего пикселя на новый.
  4. Рекурсивный визит к соседям:
    • Перейдите к соседним пикселям (вверх, вниз, влево, вправо или по диагонали, в зависимости от реализации).
    • Повторите процесс для каждого соседа, который соответствует целевому цвету.
  5. Завершение: Алгоритм завершается, когда все связанные пиксели целевого цвета обработаны.

 

Реализация

Рекурсивное заполнение потоком:

def flood_fill_recursive(image, sr, sc, new_color):
    rows, cols = len(image), len(image[0])
    color_to_replace = image[sr][sc]
    if color_to_replace == new_color:
        return image

    def dfs(r, c):
        if (0 <= r < rows and 0 <= c < cols and image[r][c] == color_to_replace):
            image[r][c] = new_color
            # Исследуйте соседей: up, down, left, right
            dfs(r + 1, c)  # Вниз
            dfs(r - 1, c)  # Вверх
            dfs(r, c + 1)  # Влево
            dfs(r, c - 1)  # Вправо

    dfs(sr, sc)
    return image

 

Объяснение:

 

Итеративное заполнение потоком:

from collections import deque

def flood_fill_iterative(image, sr, sc, new_color):
    rows, cols = len(image), len(image[0])
    color_to_replace = image[sr][sc]
    if color_to_replace == new_color:
        return image

    queue = deque()
    queue.append((sr, sc))
    image[sr][sc] = new_color

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # Направления: up, down, left, right
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == color_to_replace):
                image[nr][nc] = new_color
                queue.append((nr, nc))

    return image

 

Объяснение:

 

Временная сложность: O(N), где N — количество пикселей в области, которую нужно заполнить. Каждый пиксель посещается не более одного раза.

Пространственная сложность:

 

9. Минимальное связующее дерево

Минимальное связующее дерево (MST)

Минимальное связующее дерево (MST)

 

MST — это подмножество ребер связного, неориентированного, взвешенного графа, который соединяет все вершины вместе без каких-либо циклов и с минимально возможным общим весом ребер.

Проще говоря, это самый дешёвый способ соединить все узлы в сети без каких-либо петель.

 

Ключевые алгоритмы поиска MST:

1. Алгоритм Крускала:

 

Реализация:

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            # Сжатие пути
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # Обнаружен цикл
        # Объединение по рангу
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_y] < self.rank[root_x]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

def kruskal_mst(num_nodes, edges):
    # edges - это список кортежей: (weight, node_u, node_v)
    uf = UnionFind(num_nodes)
    mst = []
    total_weight = 0

    # Сортировка ребер по весу
    edges.sort(key=lambda x: x[0])

    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
            print(f"Edge добавлен: ({u}, {v}) with weight {weight}")
        else:
            print(f"Edge ({u}, {v}) с весом {weight} создает цикл и пропускается.")

    print(f"Общий вес MST: {total_weight}")
    return mst

 

Объяснение:

 

Временная сложность: O(E log E), так как сортировка рёбер занимает O(E log E), а операции объединения и поиска выполняются практически за постоянное время

Сложность по пространству: O(V + E), O(V) для хранения массивов родительских вершин и рангов в алгоритме объединения и O(E) для хранения рёбер.

 

2. Алгоритм Прима:

import heapq

def prim_mst(graph, start=0):
    num_nodes = len(graph)
    visited = [False] * num_nodes
    min_heap = [(0, start, -1)]  # (weight, current_node, parent_node)
    mst = []
    total_weight = 0

    while min_heap and len(mst) < num_nodes - 1:
        weight, u, parent = heapq.heappop(min_heap)
        if not visited[u]:
            visited[u] = True
            if parent != -1:
                mst.append((parent, u, weight))
                total_weight += weight
                print(f"Edge добавлен: ({parent}, {u}) with weight {weight}")

            for v, w in graph[u]:
                if not visited[v]:
                    heapq.heappush(min_heap, (w, v, u))

    if len(mst) != num_nodes - 1:
        print("График не подключен.")
        return None

    print(f"Общий вес MST: {total_weight}")
    return mst

 

Объяснение:

 

Временная сложность: O(E log V) при использовании очереди с приоритетом (минимальная куча).

Сложность по памяти: O(V) для очереди с приоритетом и используемых массивов.

 

10. Кратчайший путь

Кратчайший путь

Кратчайший путь

 

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

Проще говоря, речь идёт о поиске наиболее эффективного маршрута от начальной точки к конечному пункту назначения в сети.

 

Ключевые алгоритмы поиска кратчайших путей:

1. Алгоритм Дейкстры:

import heapq

def dijkstra(graph, start):
    # график: список смежностей, где graph[u] = [(v, weight), ...]
    distances = {vertex: float('inf') для вершины в графе}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        # Пропустите, если мы уже нашли лучший путь
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            # Если найден более короткий путь к соседу
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

 

Объяснение:

 

Временная сложность: O(V + E log V) при использовании минимальной кучи (очереди с приоритетом).

Сложность по пространству: O(V) для хранения расстояний и очереди с приоритетом.

 

2. Алгоритм Беллмана-Форда:

def bellman_ford(graph, start):
    # график: список ребер [(u, v, weight), ...]
    num_vertices = len({u для ребра в графе для u в edge[:2]})
    distances = {vertex: float('inf') для ребра в графе, для вершины в edge[:2]}
    distances[start] = 0

    # Несколько раз расслабьте края
    for _ in range(num_vertices - 1):
        for u, v, weight in graph:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # Проверьте наличие циклов с отрицательным весом
    for u, v, weight in graph:
        if distances[u] + weight < distances[v]:
            raise Exception("График содержит цикл с отрицательным весом")

    return distances

 

Объяснение:

 

Временная сложность: O (V * E)

Сложность пространства: O (V) для хранения расстояний.

 

3. Поиск по ширине (BFS):

from collections import deque

def bfs_shortest_path(graph, start, target):
    visited = set()
    queue = deque([(start, [start])])  # Each element is a tuple (node, path_to_node)
    visited.add(start)

    while queue:
        current_node, path = queue.popleft()

        if current_node == target:
            return path  # Найден кратчайший путь

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # Путь не найден

 

4. Алгоритм A * (A-Star):

 

Как это работает:

 

Реализация:

import heapq

def a_star(graph, start, goal, heuristic):
    open_set = []
    heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start, [start]))  # (f_score, g_score, node, path)
    closed_set = set()

    while open_set:
        f_score, g_score, current_node, path = heapq.heappop(open_set)

        if current_node == goal:
            return path  # Найден кратчайший путь

        if current_node in closed_set:
            continue
        closed_set.add(current_node)

        for neighbor, weight in graph[current_node]:
            if neighbor in closed_set:
                continue
            tentative_g_score = g_score + weight
            tentative_f_score = tentative_g_score + heuristic(neighbor, goal)
            heapq.heappush(open_set, (tentative_f_score, tentative_g_score, neighbor, path + [neighbor]))

    return None  # Путь не найден

 

Временная сложность:

Сложность по памяти: O(b^d), так как необходимо хранить все сгенерированные узлы в памяти.

 

5. Алгоритм Флойда-Уорсхолла:

 

Реализация:

def floyd_warshall(graph):
    # Инициализируйте матрицы distance и next_node
    nodes = list(graph.keys())
    dist = {u: {v: float('inf') for v in nodes} for u in nodes}
    next_node = {u: {v: None for v in nodes} for u in nodes}

    # Инициализируйте расстояния на основе прямых ребер
    for u in nodes:
        dist[u][u] = 0
        for v, weight in graph[u]:
            dist[u][v] = weight
            next_node[u][v] = v

    # Алгоритм Флойда-Уоршалла
    for k in nodes:
        for i in nodes:
            for j in nodes:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]

    # Проверьте наличие отрицательных циклов
    for u in nodes:
        if dist[u][u] < 0:
            raise Exception("График содержит цикл с отрицательным весом")

    return dist, next_node

 

Временная сложность: O (V ^ 3)

Сложность по памяти: O(V^2) для хранения массива расстояний.

 

 

Надеюсь, вам понравилось читать эту статью.

Если вы нашли эту статью полезной, поставьте лайк ❤️.

Если у вас есть какие-либо вопросы или предложения, оставьте комментарий.

Exit mobile version