📕 Алгоритм BFS (Breadth-First Search)

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

⚙️ Как работает BFS
1. Берём любую стартовую вершину.
2. Добавляем её в очередь.
3. Пока очередь не пуста:
- достаём вершину из очереди,
- посещаем всех её соседей,
- непосещённых соседей добавляем в очередь.

✅Релизация на python:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    order = []  # порядок обхода

    while queue:
        vertex = queue.popleft()

        if vertex not in visited:
            visited.add(vertex)
            order.append(vertex)

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

    return order

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(bfs(graph, 'A'))

#algorithm #python

🔹 DFS (Depth-First Search) — поиск в глубину в графе

💡Идея:

Исследуем граф «вглубь», пока не достигнем конца пути, затем возвращаемся.

Нужно хранить посещённые вершины (visited).

🔧Применение:

Поиск пути, топологическая сортировка, компоненты связности.

⚙️Рекурсивноя реализвация:

graph = {
    'A': ['B','C'], 'B': ['D','E'], 'C': ['F'],
    'D': [], 'E': ['F'], 'F': []
}

def dfs(graph, start, visited=None):
    if visited is None: visited = set()
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
dfs(graph, 'A')

⚙️Итеративно через стек:

def dfs_iter(graph, start):
    visited, stack = set(), [start]
    while stack:
        v = stack.pop()
        if v not in visited:
            print(v, end=' ')
            visited.add(v)
            stack.extend(reversed(graph[v]))
dfs_iter(graph, 'A')

✅Вывод:

A B D E F C

#algorithm #python