Dev Easy Notes

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

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

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

👉 поиск в глубину
👉 поиск в ширину

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

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

def dfs(graph, start):
    visited = set()
    visited.add(start)

    stack = [start]
    while stack:
        vertex = stack.pop()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

Если же это поиск в ширину, то все, то же самое, только для списка используем очередь:

def bfs(graph, start):
    visited = set()
    visited.add(start)
    queue = deque(start)

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

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

    Ты
   / \
Папа Папа

Ладно, ладно, ну вы сами знали на кого, подписывались, смотрите пример в картинке...

Нафига два разных алгоритма? Разные обходы нужны для разных целей. DFS хорошо подходит для поиска циклов: условие if neighbor not in visited в блоке else мы попадем только если у графа есть цикл. BFS же вроде как подходит для поиска кротчайшего пути, но я на практике такую штуку не реализовывал.

www.tgoop.com/dev_easy_notes/362

2.8K viewsedited  Feb 3 at 12:44

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

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

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

👉 поиск в глубину
👉 поиск в ширину

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

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

def dfs(graph, start):
    visited = set()
    visited.add(start)

    stack = [start]
    while stack:
        vertex = stack.pop()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

def bfs(graph, start):
    visited = set()
    visited.add(start)
    queue = deque(start)

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    Ты
   / \
Папа Папа

BY Dev Easy Notes