 |
|
Модераторы: Daevaorn |
 
|
|
Направленный ациклицеский граф, Топологическая сортировка 
| pavel777MD |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 16.4.2014 Репутация: нет Всего: нет |
Всем привет.
Пытаюсь разработать алгоритм, который будет определять, является ли данная последовательность вершин топологической сортировкой для ДАГ. В общем суть проблемы понятна, но все проблема в том, что сложность не должна превышать О(E+V). а у меня это никак не получается. Может у кого-то есть какие-то идеи или подсказки. Пы. сы. свой алгоритм не привожу, так как он тривиален, как мне кажется. Тупо проверяю весь список. Это сообщение отредактировал(а) pavel777MD - 16.4.2014, 14:03 |
|||
|
||||
Загрузка ...
| xvr |
|
|||
|
Эксперт  Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
Можно так - удаляете вершины из исходного графа в порядке, заданном входной последовательностью. Перед удалением вершины проверяете, что у нее нет входящих дуг (если есть - то заданная последовательность не является топологической сортировкой), после удаления удаляете все исходящие дуги. Все
|
|||
|
||||
| pavel777MD |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 16.4.2014 Репутация: нет Всего: нет |
Похоже, идея классная. Проверю ее и отвечу. Вот что значит, свежий взгляд на проблему. xvr, Спасибо
 Это сообщение отредактировал(а) pavel777MD - 16.4.2014, 14:13 |
|||
|
||||
| pavel777MD |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 16.4.2014 Репутация: нет Всего: нет |
Хотя, не так уж и хорошо это. Проверки много слишком занимают времени.
|
|||
|
||||
| xvr |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
А это уже зависит от способа хранения графа. Проверки можно сделать за константное время (при правильном способе представления графа) |
|||
|
||||
| pavel777MD |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 16.4.2014 Репутация: нет Всего: нет |
В моем случае граф первоначально представлен в следующем виде:
массив массивов(vector' ов в данном случае) целых чисел, где для строки i (вершины i) элементами являются смежные вершины. У вас есть идеи, как из этого представления получить нужное? Не то я снова в тупике... Не знаю, правильно ли, но мои суждения вроде доказывают, что удовлетворяется условие сложности в данном случае. |
|||
|
||||
| xvr |
|
||||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
Т.е. индексы в внешнем массиве - это узлы, а содержимое внутренних массивов - это дуги (точнее их конечный узел)? Если так, то к этому представлению нужно добавить 1 счетчик на каждый узел - счетчик входящих дуг (inp_count). Далее все элементарно -
|
||||
|
|||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0731 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |