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

Согласно книге (Intro to Algorithm), в dfs ребра подразделяются на 4 вида:

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

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


graph-theory edges depth-first-search
person Alcott    schedule 09.09.2011    source источник
comment
Это также объясняется в pdf-файле: csd.uoc.gr/~hy583 /papers/ch3_4.pdf   -  person Nivetha    schedule 28.07.2014

Ответы (1)


arrow_upward
24
arrow_downward

Если вам это действительно нужно, вы можете проверить это, поддерживая так называемое время входа и выхода для каждого узла. Во время выполнения алгоритма вы увеличиваете переменную 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)
person jpalecek    schedule 09.09.2011