Согласно книге (Введение в алгоритм), в dfs, ребра классифицируются как 4 вида:
- Край дерева, если в ребре (u,v), v сначала обнаруживается, то (u, v) - это
край дерева.
- Задний край, если ......, v уже обнаружен, а v - это предок, то это задний край.
- Передняя граница, если ......, v уже обнаружена и v является потомком u, передняя граница - это она.
- Перекрестный край, все рёбра, кроме вышеуказанных трёх.
Мой вопрос в том, как определить, является ли v предком или потомком u, когда я пытаюсь выяснить, является ли (u, v) задней или передней гранью?
задан dsolimano 25 October 2011 в 14:09
поделиться