Почему деревья DFS не содержат перекрестных ребер.

Question

В то время как при первом поиске глубины, почему это необходимо, чтобы не было перекрестных ребер?

Answer 1

Потому что, если есть перекрестные ребра, это уже не дерево (дерево не может содержать циклы).

Любое дерево с n узлами содержит n-1 ребра. Если вы добавляете ребро, любое ребро (крест, назад и т. Д.), У вас теперь есть n ребер. Два узла, которые вы только что связали, добавив этот край, уже имели путь между ними (потому что есть путь между любыми двумя узлами в дереве) и добавлением этого края вы закрыли круг. Итак, теперь граф больше не является деревом.