1279
правок
Поиск в глубину: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 12: | Строка 12: | ||
Поиск в глубину в [[орграф|орграфе]] отличается тем, что при движении вперед [[дуга|дуги]] проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на | Поиск в глубину в [[орграф|орграфе]] отличается тем, что при движении вперед [[дуга|дуги]] проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на | ||
четыре класса: ''древесные'', ''прямые'', замыкающие какой-либо [[путь]] из [[древесная дуга|древесных дуг]], ''обратные'', замыкающие [[контур]], и ''поперечные'', ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. [[Частичный граф|Частичный орграф]], порожденный древесными дугами, является либо корневым растущим [[ордерево|ордеревом]] (''[[дерево поиска в глубину]]''), либо [[лес|лесом]], каждая компонента которого есть [[корневое дерево|корневое растущее дерево]]. | четыре класса: ''древесные'', ''прямые'', замыкающие какой-либо [[путь]] из [[древесная дуга|древесных дуг]], ''обратные'', замыкающие [[контур]], и ''поперечные'', ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. [[Частичный граф|Частичный орграф]], порожденный древесными дугами, является либо корневым растущим [[ордерево|ордеревом]] (''[[дерево поиска в глубину]]''), либо [[лес|лесом]], каждая компонента которого есть [[корневое дерево|корневое растущее дерево]]. | ||
[[Файл:Basic numbering.png|500px]] | |||
Поиск в глубину является основой многих алгоритмов исследования структуры графа. | Поиск в глубину является основой многих алгоритмов исследования структуры графа. | ||
| Строка 22: | Строка 25: | ||
* ''[[L-Нумерация|<math>\,L</math>-нумерация]],'' | * ''[[L-Нумерация|<math>\,L</math>-нумерация]],'' | ||
* ''[[M-Нумерация|<math>\,M</math>-нумерация]],'' | * ''[[M-Нумерация|<math>\,M</math>-нумерация]],'' | ||
* ''[[N-Нумерация|<math>\,N</math>-нумерация]],'' | |||
* ''[[T-Нумерация|<math>\,T</math>-нумерация]],'' | * ''[[T-Нумерация|<math>\,T</math>-нумерация]],'' | ||
* ''[[Обход графа]],'' | * ''[[Обход графа]],'' | ||
| Строка 31: | Строка 35: | ||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | * Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
[[Категория:Деревья]] | |||
[[Категория:Обыкновенные графы]] | |||
[[Категория:Ориентированные графы]] | |||
[[Категория:Основные термины]] | |||
[[Категория:Потоковый анализ программ]] | |||
[[Категория:Преобразование программ]] | |||