Пошук в глибину
Матеріал з Вікіпедії — вільної енциклопедії.
Алгори́тм пошуку́ в глибину́ (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графа. Робота алгоритма починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.[1]
[ред.] Псевдокод
Рекурсивна версія алгоритму:[2]
def dfs(v):
помітити v як відвідану
обійти-в-прямому-порядку(v)
для всіх ребер i інцидентних до v таких що i не відвідано
dfs(i)
обійти-в-зворотньому-порядку(v)
Версія без рекурсії:
dfs(граф G)
{
список L = порожній
дерево T = порожнє
обрати початкове ребро x
пошук(x)
поки(L не порожній)
{
видалити ребро (v, w) з голови L
якщо w не відвідано
{
додати (v, w) до T
пошук(w)
}
}
}
пошук(вершина v)
{
відвідати v
для кожного ребра (v, w)
додати ребро (v, w) на початок L
}
[ред.] Примітки
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. «22.3», Introduction to Algorithms, вид. 2-ге (2001) (англ. ), 540-549, MIT Press. ISBN 0-262-03293-7.
- ↑ див. алгоритм наведений на англ. вікі.
[ред.] Див. також
 |
Це незавершена стаття про комп'ютери. Ви можете допомогти проекту, виправивши або дописавши її. |
