В чем разница графа и дерева

Что проверяют

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

Как отвечать

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

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

Покажите, как это выглядит в коде. Граф на Python обычно хранят списком смежности, например collections.defaultdict(list), дерево часто узлами с полями left/right или children. Проверка «граф это дерево»: рёбер ровно n - 1, и обход из любой вершины доходит до всех n. Если под рукой networkx, есть готовая nx.is_tree().

Хорошо добавить разницу в алгоритмах: при обходе дерева от корня множество посещённых вершин не нужно, а обход графа без visited на первом же цикле уйдёт в бесконечность.

Где спотыкаются

Говорят, что у дерева обязательно есть корень. Корень это выбор при представлении, а не свойство структуры: неориентированное дерево корня не имеет.

Путают дерево с ориентированным ациклическим графом. В DAG у вершины может быть несколько родителей, и это уже не дерево.

Пишут рекурсивный DFS на глубоком графе и упираются в предел рекурсии Python, по умолчанию он около 1000 вызовов. Лучше сразу сказать про итеративный вариант со стеком, а для BFS взять collections.deque.