Чтобы найти вид ребер графа, на котором мы применили алгоритм поиска в глубину, мы могли бы использовать это:
ребра дерева: x -> y, когда [d[y],f[y]] ⊂ [d[x],f[x]]
передние ребра: x -> y, когда [d[x],f[x]] ⊂ [d[y],f[y]]
задние ребра: x -> y, когда [d[y],f[y]] ⊂ [d[x],f[x]]
Перекрестные ребра: x -> y, когда [d[x],f[x]] ∩ [d[y],f[y]]=∅
Время обнаружения: время обнаружения d[v] – это количество узлов, обнаруженных или завершенных до того, как впервые появится v.
Время окончания: время окончания f[v] – это количество узлов, обнаруженных или завершенных до завершения расширения $v$.
Вот график, на который я смотрю:
И вот время открытия и окончания, которое я нашел:
Алгоритм:
Depthfirstsearch(G)
for each v ∈ V
color[v]=white
p[v]=NIL
time=0
for each v ∈ V
if color[v]=white then
Visit(v)
Visit(u)
color[u]=gray
time=time+1
d[u]=time
for each v ∈ Adj[u]
if color[v]=white then
p[v]=u
Visit(v)
color[u]=black
time=time+1
f[u]=time
Когда у нас есть, например, случай [d[y],f[y]] ⊂ [d[x],f[x]], как мы можем узнать, является ли это краем дерева или обратным краем?
Должны ли мы помечать родителя каждого узла, например:
и если есть красное ребро, мы знаем, что это ребро дерева? Если да, то не могли бы вы объяснить мне, почему?
Кроме того, разве jh,ia не является передним краем, а ag — задним краем? Или я ошибаюсь?
