979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
1 | |
Топологическая сортировка11.04.2013, 05:36. Показов 10883. Ответов 24
Метки нет (Все метки)
Здорова!
Тут от вычитал новое понятие "топологическая сортировка". Вообщем есть задачка нужно сделать топологическу сортировку описаную в Кнут т1 (второе издание) ст 262.?????
0
|
11.04.2013, 05:36 | |
Ответы с готовыми решениями:
24
Топологическая сортировка Топологическая сортировка (содержание файла) топологическая сортировка Топологическая сортировка |
алкокодер
157 / 153 / 41
Регистрация: 27.12.2012
Сообщений: 550
|
|
11.04.2013, 05:48 | 2 |
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
11.04.2013, 11:41 [ТС] | 3 |
Ничо не понял. Есть допустим ассоциативный массив map<string, int>, как мне его отсортировать по топологической сортировке????
Для массива нужно сделать Map своего, но если для своего можно, то значит и для просто map можно. Пример кода в студию!
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
11.04.2013, 15:53 | 4 |
по-моему, вы не понимаете, что делает этот алгоритм... он должен расставить вершины орграфа таким образом, чтобы ребра шли из вершин с меньшим номером в вершины с большим...
то есть надо найти некую перестановку вершин, чтобы можно было строго сказать, что из данной вершины мы пойдем только вперед по ребрам и сворачивать никуда не будем... (последнее - от себя, вероятно, коряво)
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
11.04.2013, 16:06 [ТС] | 5 |
А как же я задачку решу? Там нужно применить эту сортировку для сортировки пользовательского массива Map построенного на двоичном дереве?
Задача: "Используйте Map для выполнения топологической сортировки описано в Кнут..."
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
11.04.2013, 16:06 | 6 |
дерево - это граф...
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
11.04.2013, 16:07 [ТС] | 7 |
salam, Головняк да?
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
11.04.2013, 16:08 | 8 |
вам лучше начать с задач попроще.
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
11.04.2013, 16:10 [ТС] | 9 |
salam, а если я просто извлечу все элементы из дерева запишу их в массив, а затем заново загоню их в дерево токо уже из отсортированного массива, тоже дерево отсортируется. хз. Так зато понятней?
Добавлено через 52 секунды salam, яж могу ее так решить вытянуть элементы запись в массив, а затем вставить и все сортированое дерево, но хотелось бы применить топологическую сортировку, так чтобы знать. Попроще я нихо хо эту сделать тем более там уровень сложности *2.5 типо часа 4 работы. А можно в вектор загнать узлы дерева, а затем уже из них новое дерево сформировать отсортированное, а старое удалить.
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
11.04.2013, 16:12 | 10 |
да дело не в расположении элементов по возрастанию/убыванию... это совсем другая задача... читайте книги...
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
11.04.2013, 16:14 [ТС] | 11 |
salam, Это как раз мой уровень сложности сортировать, то я знаю как.
Добавлено через 49 секунд salam, Да читал поля там подобавлять нада цвета им дать, головняк. Добавлено через 51 секунду Я просто от смотрю раз тут мало так людей в этой теме, то видимо в нее и углубляться не стоит, видимо не популярная и фиг кода пригодиться.
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
11.04.2013, 16:16 | 12 |
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
11.04.2013, 16:18 | 13 |
это один из базовых графовых алгоритмов. он нужен в некоторых сложных и весьма полезных в определенной ситуации алгоритмах на графах. я считаю, что разработчик должен это уметь. за себя решайте сами.
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
11.04.2013, 16:20 [ТС] | 14 |
salam, А как же мне сделать? Там то того кода 20 строк, а я фиг разберусь. Вроде с виду и не сложно делать. Хо сделать, да не лень разбираться.
Наверно придется вникнуть, хоть хочется хоть не хочется, тем более что вроде мало там написано и небось простой раз популярный. Хотя подумать хорошо яж не разработчик. Значит мне это уметь не обязательно. Наверно забью. Для успокоения совести сделаю просто сортировку вытянуть элементы закинуть в массив, а затем новое дерево сформировать отсортированное. Как буду разработчиком тада изучу
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
11.04.2013, 16:21 | 15 |
попу прижмите к стулу и учитесь...
0
|
396 / 371 / 111
Регистрация: 03.02.2013
Сообщений: 1,131
|
|
11.04.2013, 16:32 | 16 |
что-то я вас не понял как вы это изобразите ) map - это уже упорядоченный контейнер, другое дело какого рода порядок map делает порядок по ключу (first в паре)
я так понимаю в него вы загоняете пару как вектор (вершина А, вершина B), которая говорит что из вершины A идёт обход в сторону вершины, т.е. A->B насколько я помню топологически отсортированный граф на простом языке должен обладать следующим свойством каждая вершина в его представлении должна следовать из предыдущих или из ничего т.е. если заданы например A->B, B->D, С->D то порядок должен быть таким: A,C,B,D или A,B,C,D можно попробывать представить иначе, допустим есть формула x = (2+1)+((2+1)*2) вам её нужно выполнить, для этого нужно определить приорететы с каких действий надо начинать выполнять и каким закончить распишем так x = (A)B((C)D) на основании приорететов операций можно составить граф в map: C->D, D->B, A->B (здесь C->D читать как "если известен C, можно вычислить D") после тополгической сортировки должен быть список вида A,C,D,B или C,D,A,B думаю понятна суть
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
||||||
11.04.2013, 16:49 | 17 | |||||
столько флуда, а код никто не смог написать
2
|
396 / 371 / 111
Регистрация: 03.02.2013
Сообщений: 1,131
|
|
11.04.2013, 16:54 | 18 |
ваш код легко нагуглить - http://algorus.blogspot.ru/201... -sort.html
Ctrl+C/Ctrl+V все умеют, тут речь шла о реализации в map вроде бы, если я верно понял суть вопроса
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
11.04.2013, 17:05 | 19 |
abit, Увидел. Но сути это не меняет. Просто, названия вершин - строки.
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
||||||
12.04.2013, 12:12 [ТС] | 20 | |||||
хз. Примерно так чото понял местами. n- это количество сортируемых вершин
Да еще вычитал, что топологическая сортировка на предпоследнем месте по популярности, вообще зря потраченное время на разбор нигде она не понадобиться, ну и фиг с ним хоть бы с ней разобраться, морочная фигня. Добавлено через 7 минут А если дерево сортировать, то как быть? хз. Ничо не пойму. Добавлено через 3 минуты Это ж тоже самое получается что эго тоже нужно переписать в стек, или массив. А потом походу заново загнать в дерево. Ну так это тоже самое получается, что вытянуть из дерева все элементы загнать их в массив, а затем отсортировать. Разница в том, что при топологической сортировке элементы будут в массив попадать отсортировано, ну короче массив потом не нуно будет сортировать, а сразу загнать в дерево. ????? Чото мне так как то кажется.
0
|
12.04.2013, 12:12 | |
12.04.2013, 12:12 | |
Помогаю со студенческими работами здесь
20
Топологическая сортировка Топологическая сортировка на Си!!!! Топологическая сортировка графа Топологическая сортировка графа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |