Краевая классификация в DFS - PullRequest
Новая
       39

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

16 голосов
/ 09 сентября 2011

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

  1. Край дерева, если в ребре (u, v) сначала обнаруживается v, то (u, v) кромка дерева.
  2. Back Edge, если ......, v уже обнаружен и v является предком, то это задний край.
  3. Forward Edge, если ......, v уже обнаружен и v является потомком u, передний край это.
  4. Перекрестные края, все ребра, кроме указанных выше трех.

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

1 Ответ

19 голосов
/ 09 сентября 2011

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

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

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

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

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