Деревья и графы

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

Дерево — связный граф без циклов (замкнутых путей). В нём есть одна особая вершина — корень; у каждой остальной вершины есть один «родитель», а вершины без потомков называются листьями. Примеры деревьев: структура папок на компьютере, родословная, схема логического выбора. В дереве из n вершин всегда ровно n − 1 ребро.

В Python удобно хранить граф списками соседних вершин: каждой вершине соответствует список её соседей. Например, создаём словарь g = dict(), затем g["A"] = ["B", "C"], g["B"] = ["A", "D"], g["C"] = ["A"], g["D"] = ["B"]. При такой записи соседи вершины A лежат в g["A"], их легко найти, а памяти тратится немного.

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

Главное

• Граф состоит из вершин и рёбер; рёбра могут быть направленными или ненаправленными.
• Дерево — связный граф без циклов; в дереве из n вершин n − 1 ребро.
• В дереве есть корень, отношение родитель — потомок и листья.
• В Python граф удобно хранить в словаре со списками соседних вершин.
• Поиск в ширину находит кратчайший (по числу рёбер) путь.