Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
#1

Топологическая сортировка - C++

11.04.2013, 05:36. Просмотров 2577. Ответов 24
Метки нет (Все метки)

Здорова!
Тут от вычитал новое понятие "топологическая сортировка".
Вообщем есть задачка нужно сделать топологическу сортировку описаную в Кнут т1 (второе издание) ст 262.?????
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.04.2013, 05:36     Топологическая сортировка
Посмотрите здесь:

Топологическая сортировка - C++
Ошибка в строке 34, подскажите как исправить: 'reverse' was not declared in this scope // Top_Sort.cpp: определяет точку входа для...

Топологическая сортировка (содержание файла) - C++
Приветствую. Не так давно столкнулся с топологической сортировкой графа на c++. У программы задача отрисовывать граф и, соответственно,...

топологическая сортировка - Дискретная математика
Добрый вечер. Мне необходимо провести топологическую сортировку к отношению на мн-ве(см. картинка).Вроде на графе сортировка аналогична...

Топологическая сортировка на Си!!!! - C (СИ)
Народ!Помогите хоть кто-нибудь с курсовой работой на Си!!! Мне нужно сделать программу на тему топологическая сортировка. У меня есть код...

Топологическая сортировка - Delphi
Требуется организовать топологическую сортировку на примере списка изучаемых дисциплин.Список берётся из эксель-файла.Все предложения(в том...

Топологическая сортировка - Delphi
Нужно расположить вершины графа в правильном порядке с помощью смежной матрицы, с использованием компонента StringGrid. вот что я...

Топологическая сортировка графа - C (СИ)
Здравствуйте, у меня есть код сортировки, но он слишком громоздкий, помогите его сделать более компактные, только не полузуя структурами. ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UnsKneD
алкокодер
154 / 150 / 11
Регистрация: 27.12.2012
Сообщений: 548
11.04.2013, 05:48     Топологическая сортировка #2
ninja2, http://rain.ifmo.ru/cat/view.php/vis...2007/algorithm
http://hashcode.ru/questions/41924/c...B2%D0%BA%D0%B0
ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 11:41  [ТС]     Топологическая сортировка #3
Ничо не понял. Есть допустим ассоциативный массив map<string, int>, как мне его отсортировать по топологической сортировке????


Для массива нужно сделать Map своего, но если для своего можно, то значит и для просто map можно. Пример кода в студию!
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
11.04.2013, 15:53     Топологическая сортировка #4
по-моему, вы не понимаете, что делает этот алгоритм... он должен расставить вершины орграфа таким образом, чтобы ребра шли из вершин с меньшим номером в вершины с большим...
то есть надо найти некую перестановку вершин, чтобы можно было строго сказать, что из данной вершины мы пойдем только вперед по ребрам и сворачивать никуда не будем... (последнее - от себя, вероятно, коряво)
ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:06  [ТС]     Топологическая сортировка #5
А как же я задачку решу? Там нужно применить эту сортировку для сортировки пользовательского массива Map построенного на двоичном дереве?

Задача: "Используйте Map для выполнения топологической сортировки описано в Кнут..."
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
11.04.2013, 16:06     Топологическая сортировка #6
дерево - это граф...
ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:07  [ТС]     Топологическая сортировка #7
salam, Головняк да?
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
11.04.2013, 16:08     Топологическая сортировка #8
вам лучше начать с задач попроще.
ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:10  [ТС]     Топологическая сортировка #9
salam, а если я просто извлечу все элементы из дерева запишу их в массив, а затем заново загоню их в дерево токо уже из отсортированного массива, тоже дерево отсортируется. хз. Так зато понятней?

Добавлено через 52 секунды
salam, яж могу ее так решить вытянуть элементы запись в массив, а затем вставить и все сортированое дерево, но хотелось бы применить топологическую сортировку, так чтобы знать.

Попроще я нихо хо эту сделать тем более там уровень сложности *2.5 типо часа 4 работы.

А можно в вектор загнать узлы дерева, а затем уже из них новое дерево сформировать отсортированное, а старое удалить.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
11.04.2013, 16:12     Топологическая сортировка #10
да дело не в расположении элементов по возрастанию/убыванию... это совсем другая задача... читайте книги...
ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:14  [ТС]     Топологическая сортировка #11
salam, Это как раз мой уровень сложности сортировать, то я знаю как.

Добавлено через 49 секунд
salam, Да читал поля там подобавлять нада цвета им дать, головняк.

Добавлено через 51 секунду
Я просто от смотрю раз тут мало так людей в этой теме, то видимо в нее и углубляться не стоит, видимо не популярная и фиг кода пригодиться.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2013, 16:16     Топологическая сортировка #12
Цитата Сообщение от ninja2 Посмотреть сообщение
А как же я задачку решу? Там нужно применить эту сортировку для сортировки пользовательского массива Map построенного на двоичном дереве?
дерево тоже граф.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
11.04.2013, 16:18     Топологическая сортировка #13
это один из базовых графовых алгоритмов. он нужен в некоторых сложных и весьма полезных в определенной ситуации алгоритмах на графах. я считаю, что разработчик должен это уметь. за себя решайте сами.
ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:20  [ТС]     Топологическая сортировка #14
salam, А как же мне сделать? Там то того кода 20 строк, а я фиг разберусь. Вроде с виду и не сложно делать. Хо сделать, да не лень разбираться.
Наверно придется вникнуть, хоть хочется хоть не хочется, тем более что вроде мало там написано и небось простой раз популярный.
Хотя подумать хорошо яж не разработчик. Значит мне это уметь не обязательно. Наверно забью. Для успокоения совести сделаю просто сортировку вытянуть элементы закинуть в массив, а затем новое дерево сформировать отсортированное. Как буду разработчиком тада изучу
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2013, 16:21     Топологическая сортировка
Еще ссылки по теме:

Топологическая сортировка графа - Delphi
Здравствуйте! Помогите, пожалуйста. Пишу программу для поиска путей на графах между всеми парами вершин методом динамического...

Топологическая сортировка графа - Алгоритмы
Написал программу топологически сортирующую граф с помощью обхода в ширину. Сдал её на информатиксе...

Графы, топологическая сортировка - C#
Доброго времени суток. Помогите, пожалуйста, реализовать топологическую сортировку в задаче 1022 тимуса, к сожалению, времени мало,...

Неверно работает топологическая сортировка - Алгоритмы
Привет. Я написал топологическую сортировку, решил проверить на тестовом примере его, но оно не работает верно результат должен быть 1 4 2...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
11.04.2013, 16:21     Топологическая сортировка #15
попу прижмите к стулу и учитесь...
Yandex
Объявления
11.04.2013, 16:21     Топологическая сортировка
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru