|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
Топологическая сортировка11.04.2013, 05:36. Показов 11724. Ответов 24
Метки нет (Все метки)
Здорова!
Тут от вычитал новое понятие "топологическая сортировка". Вообщем есть задачка нужно сделать топологическу сортировку описаную в Кнут т1 (второе издание) ст 262.?????
0
|
|
| 11.04.2013, 05:36 | |
|
Ответы с готовыми решениями:
24
Топологическая сортировка Топологическая сортировка (содержание файла) топологическая сортировка |
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
| 12.04.2013, 16:10 | |
|
ninja2, я привёл пример универсальной топологической сортировки для произвольного ациклического графа. Т.е. работает всегда на любом графе. Дерево - ациклический граф. Если граф не ациклический, то это задача конденсации графа. Могу скинуть, если надо.
1
|
|
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|||||||
| 13.04.2013, 12:26 [ТС] | |||||||
|
А не знаешь можно ли с помощью нее отсортировать просто массив int? Я от пытался не могу никак условие придумать
0
|
|||||||
|
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
|
||
| 14.04.2013, 05:09 | ||
|
Чтобы все-таки сделать, нужно для массива построить граф, где вершины будут соответствовать числам, а ребра будут идти из вершин с меньшими числами к вершинам с большими числами. Но смысла в этом никакого нет, т.к. получится квадратичное число ребер, а отсортировать можно и более быстрыми алгоритмами.
1
|
||
|
0 / 0 / 0
Регистрация: 06.06.2013
Сообщений: 2
|
|
| 06.06.2013, 10:20 | |
|
правильно ли я понял, что топологическая сортировка просто позволяет определить порядок прохода дерева, какие узлы первые, а какие следуют за ними и исходя из этого бинарное дерево, в том числе красно черное топологически отсортировано изначально ?
0
|
|
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
| 06.06.2013, 10:38 | |
|
AMV007, да, при некоторых обходах этого дерева (например dfs), всегда будет топологически-отсортированная последовательность вершин графа.
0
|
|
| 06.06.2013, 10:38 | |
|
Топологическая сортировка Топологическая сортировка Топологическая сортировка на Си!!!! Топологическая сортировка графа Топологическая сортировка графа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Альцгеймер и колоссальный объем вычислений
Programma_Boinc 08.08.2026
Альцгеймер и колоссальный объем вычислений
Сейчас по направлению болезни Альцгеймера идет колоссальный объем вычислений.
Это один из главных приоритетов проекта.
Такой массовый наплыв задач. . .
|
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства.
Родственных связей существует 8 ступеней, такие как:
p - отец
P - мать
q - муж
Q - жена
b - брат
B - сестра
s - сын
S - дочь
|
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире.
Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
|
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С.
Задача:
Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
|
|
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
|
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
|
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701
Купил два термопринтера QR701.
На сэлф-тесте написано:
Language: PC936 (GB18030).
Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
|
Создание формы заимствованного документа
Maks 03.08.2026
Задача:
Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также
табличная часть со следующими реквизитами:
- Расчетный счет покупателя. . .
|