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

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

Краткий ответ

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

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

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

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

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

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('пути нет')

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

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

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

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

Что важно запомнить

https://yadro-code.ru/lessons/without-university/school-programming-basics/school-programming-21