Графы для школьников: вершины, ребра и поиск пути

Автор: Казачкин Даниил Михайлович · Обновлено 23 августа 2026 г.

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

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

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

Как хранить граф

Один из удобных способов — словарь списков. Ключ — вершина, значение — список соседей.

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

for vertex, neighbours in graph.items():
    print(vertex, '->', neighbours)

Такой формат называется списком смежности.

Поиск в ширину

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

start = 'A'
target = 'D'
queue = [start]
visited = {start}

while queue:
    vertex = queue.pop(0)

    if vertex == target:
        print('путь есть')
        break

    for neighbour in graph[vertex]:
        if neighbour not in visited:
            visited.add(neighbour)
            queue.append(neighbour)
else:
    print('пути нет')

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

Где встречаются графы

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

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

Практикум: маршрут между кабинетами

Представьте школьные кабинеты вершинами, а прямые переходы — рёбрами. Для связей A–B, A–C, B–D, C–D, D–E составьте список смежности и найдите кратчайший по числу переходов путь из A в E поиском в ширину. На каждом слое записывайте очередь и множество посещённых вершин. Проверьте путь из вершины в себя и отдельный несвязанный кабинет F. Храните предка каждой вершины, чтобы восстановить маршрут, а не только сообщить факт достижимости.

Контрольная точка

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

Частые вопросы

Когда граф должен быть ориентированным?

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