Классификация краев в DFS

Согласно книге (Введение в алгоритм), в dfs ребра классифицируются как 4 вида:

  • Tree Edge, если в ребро (u, v), v сначала обнаружено, то (u, v) является край дерева.
  • Back Edge, если......, v уже обнаружен, а v является предком, тогда это задний край.
  • Forward Edge, если......, v уже обнаружен, а v является потомком u, передним краем.
  • Cross Edge, все ребра, за исключением трех выше.

Мой вопрос в том, как я могу определить, является ли v предком или потомком, когда я пытаюсь выяснить, является ли (u, v) обратное или переднее ребро?

Ответы

Ответ 1

Если вам это действительно нужно, вы можете проверить его, сохранив так называемые времена входа и выхода для каждого node. Во время выполнения алгоритма вы увеличиваете переменную time (начиная с 0, конечно) каждый раз, когда вы сталкиваетесь с новой вершиной. Времена entry_t(v), exit_t(v) изначально не установлены для всех вершин.

Когда вы впервые сталкиваетесь с вершиной, вы устанавливаете entry(v):=time. Когда вы выходите из вершины вверх по краю (т.е. Вставляете вершину из стека), вы устанавливаете ее exit(v):=time. При этом у вас есть

  • Если entry(u) установлено и exit(u) не задано, то u является предком текущей вершины (т.е. vu является задним ребром)
  • if entry(u)>entry(current), тогда u является потомком из текущей вершины (current- > u является передним ребром)
  • в противном случае это кросс-ребро

Обратите внимание, что эти отношения выполняются для проверки во время выполнения алгоритма. После того, как алгоритм завершен, проверка предка в основном

u is_descendant_of v = entry(u)>entry(v) and exit(u)<=exit(v)