Изменения

Перейти к: навигация, поиск

Обход в глубину, цвета вершин

8 байт добавлено, 02:46, 25 октября 2011
Дерево обхода в глубину
== Дерево обхода в глубину ==
[[Image:tree_edges.png|thumb|270px|Типы ребер, определяемые деревом обхода]]
Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>dfs(u)\ </tex> (для вершин, от которых <tex>dfs</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. Назовем ''ребрами дерева'' те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>. Рассмотрим такие ребра графа <tex>G</tex>, которые не попали в <tex>G_p</tex>. Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем ''обратными ребрами''. Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''прямыми ребрами''. Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.
Алгоритм <tex>dfs</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:
* Белый цвет вершины <tex>v</tex> по определению <tex>dfs</tex> говорит о том, что это ''ребро дерева''.
172
правки

Навигация