| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Направленный ациклицеский граф |
| Автор: pavel777MD 16.4.2014, 12:37 |
| Всем привет. Пытаюсь разработать алгоритм, который будет определять, является ли данная последовательность вершин топологической сортировкой для ДАГ. В общем суть проблемы понятна, но все проблема в том, что сложность не должна превышать О(E+V). а у меня это никак не получается. Может у кого-то есть какие-то идеи или подсказки. Пы. сы. свой алгоритм не привожу, так как он тривиален, как мне кажется. Тупо проверяю весь список. |
| Автор: xvr 16.4.2014, 12:45 |
| Можно так - удаляете вершины из исходного графа в порядке, заданном входной последовательностью. Перед удалением вершины проверяете, что у нее нет входящих дуг (если есть - то заданная последовательность не является топологической сортировкой), после удаления удаляете все исходящие дуги. Все |
| Автор: pavel777MD 16.4.2014, 14:02 |
| Похоже, идея классная. Проверю ее и отвечу. Вот что значит, свежий взгляд на проблему. xvr, Спасибо |
| Автор: pavel777MD 16.4.2014, 20:41 |
| Хотя, не так уж и хорошо это. Проверки много слишком занимают времени. |
| Автор: xvr 16.4.2014, 22:22 | ||
А это уже зависит от способа хранения графа. Проверки можно сделать за константное время (при правильном способе представления графа) |
| Автор: pavel777MD 16.4.2014, 22:35 |
| В моем случае граф первоначально представлен в следующем виде: массив массивов(vector' ов в данном случае) целых чисел, где для строки i (вершины i) элементами являются смежные вершины. У вас есть идеи, как из этого представления получить нужное? Не то я снова в тупике... Не знаю, правильно ли, но мои суждения вроде доказывают, что удовлетворяется условие сложности в данном случае. |
| Автор: xvr 17.4.2014, 12:43 | ||||
Т.е. индексы в внешнем массиве - это узлы, а содержимое внутренних массивов - это дуги (точнее их конечный узел)? Если так, то к этому представлению нужно добавить 1 счетчик на каждый узел - счетчик входящих дуг (inp_count). Далее все элементарно -
|
