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

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

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

Как отвечать

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

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

Проверка «граф является деревом»: рёбер ровно n-1 и граф связен. Это делается одним DFS или BFS либо через Union-Find, который заодно ловит цикл.

Для Java-собеседования добавьте практику. В JDK нет готового класса графа, его хранят списком смежности Map<Integer, List<Integer>> или List<List<Integer>>, а плотный граф матрицей boolean[][]. Деревья, наоборот, встречаются в стандартной библиотеке постоянно: TreeMap и TreeSet построены на красно-чёрном дереве, а HashMap при большом числе коллизий превращает корзину в дерево. Обход тоже отличается: при спуске по корневому дереву от родителя к детям в вершину повторно не попасть, а в графе без множества visited DFS зациклится.

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

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

Смешивают дерево вообще с бинарным деревом поиска. Упорядоченность ключей и не больше двух потомков это свойства BST, а не дерева как такового.

Пишут обход графа как обход дерева, без visited, и на первом же цикле получают бесконечную рекурсию и StackOverflowError.