Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.98/55: Рейтинг темы: голосов - 55, средняя оценка - 4.98
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
1

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

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

Author24 — интернет-сервис помощи студентам
Здорова!
Тут от вычитал новое понятие "топологическая сортировка".
Вообщем есть задачка нужно сделать топологическу сортировку описаную в Кнут т1 (второе издание) ст 262.?????
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.04.2013, 05:36
Ответы с готовыми решениями:

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

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

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

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

24
алкокодер
157 / 153 / 41
Регистрация: 27.12.2012
Сообщений: 550
11.04.2013, 05:48 2
ninja2, http://rain.ifmo.ru/cat/view.p... /algorithm
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
Цитата Сообщение от ninja2 Посмотреть сообщение
А как же я задачку решу? Там нужно применить эту сортировку для сортировки пользовательского массива Map построенного на двоичном дереве?
дерево тоже граф.
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
Цитата Сообщение от ninja2 Посмотреть сообщение
salam, а если я просто извлечу все элементы из дерева запишу их в массив, а затем заново загоню их в дерево токо уже из отсортированного массива, тоже дерево отсортируется. хз. Так зато понятней?

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

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

А можно в вектор загнать узлы дерева, а затем уже из них новое дерево сформировать отсортированное, а старое удалить.
что-то я вас не понял как вы это изобразите ) 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
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<vector>
 
using namespace std;
 
#define forn(i,n) for(int i = 0; i < int(n); ++i)
 
int n;
bool g[100][100];
bool used[100];
vector<int> res;    
 
 
void dfs(int idx){
    used[idx] = true;
    forn(x,n)
        if(g[idx][x] && !used[x])
            dfs(x);
    res.push_back(idx);
}
 
int main(){    
    cin>>n;
 
    memset(used,0,sizeof(used));
 
    forn(i,n)
        forn(j,n)
            scanf("%d",&g[i][j]);
 
    forn(i,n)
        if(!used[i])
            dfs(i);
 
    for(int i = n-1; i >= 0; --i)
        printf("%d ",res[i]+1);
 
    return 0;
}
Добавлено через 7 минут
столько флуда, а код никто не смог написать
2
396 / 371 / 111
Регистрация: 03.02.2013
Сообщений: 1,131
11.04.2013, 16:54 18
Цитата Сообщение от Ternsip Посмотреть сообщение
Добавлено через 7 минут
столько флуда, а код никто не смог написать
ваш код легко нагуглить - 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- это количество сортируемых вершин
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//topologichecka9 cortirovka
#include<iostream>
#include<vector>
#include<stdio.h>
#include <string.h>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
#define forn(i,n) for(int i = 0; i < int(n); ++i)
 
int n;//kolichectvo elementov vuvodit
bool g[10][10];
bool used[10];
vector<int> res; //vector int как стек
 
 
void dfs(int idx)
{
cout <<"idx= "<<idx<<endl;
    used[idx] = true;//used[i]=true
    forn(x,n)//в цикле от x до n
        if(g[idx][x] && !used[x])//если g[idx][x]&& !used[x] (g[0][0]=false && !(used[x]=true))
            dfs(x);//то снова вызов самой функции
    cout <<"push_back_idx= "<<idx<<endl;
    res.push_back(idx);//добавить в конец вершину
}
 
int main(){    
    cin>>n;
 
    memset(used,0,sizeof(used));
    srand(time(0));
 
//zapolnenie macciva
    forn(i,n)
        forn(j,n)
            //scanf("%d",&g[i][j]);//читает данные из стандартного потока stdin
        {
            int k=rand()%2;
            cout <<k<<' ';
        g[i][j]=k;
        //cout <<g[i][j]<<' ';
    }
    cout <<endl;
    
    
//zapolnenie res
    forn(i,n)
        if(!used[i])
            dfs(i);
 
    for(int i = n-1; i >= 0; --i)
        printf("%d ",res[i]);
 
    return 0;
}
Код примерно расписал, но еще не понял как он сортирует, да и реальный массив ахота отсортировать, а не просто из нулей и единиц, но в принципе главное смысл понять, а там уже любой отсортируеться.
Да еще вычитал, что топологическая сортировка на предпоследнем месте по популярности, вообще зря потраченное время на разбор нигде она не понадобиться, ну и фиг с ним хоть бы с ней разобраться, морочная фигня.

Добавлено через 7 минут
А если дерево сортировать, то как быть? хз. Ничо не пойму.

Добавлено через 3 минуты
Это ж тоже самое получается что эго тоже нужно переписать в стек, или массив. А потом походу заново загнать в дерево. Ну так это тоже самое получается, что вытянуть из дерева все элементы загнать их в массив, а затем отсортировать. Разница в том, что при топологической сортировке элементы будут в массив попадать отсортировано, ну короче массив потом не нуно будет сортировать, а сразу загнать в дерево. ????? Чото мне так как то кажется.
0
12.04.2013, 12:12
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.04.2013, 12:12
Помогаю со студенческими работами здесь

Топологическая сортировка
Требуется организовать топологическую сортировку на примере списка изучаемых дисциплин.Список...

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

Топологическая сортировка графа
Задали задание, неделю пытаюсь сделать и все никак не выходит, топологическая сортировка из книгу...

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru