Топологическая сортировка: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Топологическая сортировка''' (''Topological sorting'') - такая ''нумерация вершин'' бес...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Топологическая сортировка''' (''Topological sorting'') | '''Топологическая сортировка''' (''[[Topological sorting]]'') — | ||
такая ''нумерация вершин'' бесконтурного графа, при которой номер начала | такая ''[[нумерация вершин]]'' [[бесконтурный орграф|бесконтурного]] [[граф|графа]], при которой номер [[начало дуги|начала дуги]] всегда меньше номера ее [[конец дуги|конца]]. Если нумерация такова, что номер | ||
дуги всегда меньше номера ее конца. Если нумерация такова, что номер | начала дуги всегда больше номера ее конца, то говорят об ''[[обратная топологическая сортировка|обратной топологической сортировке'']]. | ||
начала дуги всегда больше номера ее конца, то говорят об ''обратной | |||
топологической сортировке''. | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
Текущая версия от 12:07, 20 сентября 2011
Топологическая сортировка (Topological sorting) — такая нумерация вершин бесконтурного графа, при которой номер начала дуги всегда меньше номера ее конца. Если нумерация такова, что номер начала дуги всегда больше номера ее конца, то говорят об обратной топологической сортировке.
Литература
- Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.