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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 05:36     Топологическая сортировка #1
Здорова!
Тут от вычитал новое понятие "топологическая сортировка".
Вообщем есть задачка нужно сделать топологическу сортировку описаную в Кнут т1 (второе издание) ст 262.?????
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UnsKneD
алкокодер
 Аватар для UnsKneD
153 / 149 / 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
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 11:41  [ТС]     Топологическая сортировка #3
Ничо не понял. Есть допустим ассоциативный массив map<string, int>, как мне его отсортировать по топологической сортировке????


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

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

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

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

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

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

Добавлено через 51 секунду
Я просто от смотрю раз тут мало так людей в этой теме, то видимо в нее и углубляться не стоит, видимо не популярная и фиг кода пригодиться.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2013, 16:16     Топологическая сортировка #12
Цитата Сообщение от ninja2 Посмотреть сообщение
А как же я задачку решу? Там нужно применить эту сортировку для сортировки пользовательского массива Map построенного на двоичном дереве?
дерево тоже граф.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.04.2013, 16:18     Топологическая сортировка #13
это один из базовых графовых алгоритмов. он нужен в некоторых сложных и весьма полезных в определенной ситуации алгоритмах на графах. я считаю, что разработчик должен это уметь. за себя решайте сами.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:20  [ТС]     Топологическая сортировка #14
salam, А как же мне сделать? Там то того кода 20 строк, а я фиг разберусь. Вроде с виду и не сложно делать. Хо сделать, да не лень разбираться.
Наверно придется вникнуть, хоть хочется хоть не хочется, тем более что вроде мало там написано и небось простой раз популярный.
Хотя подумать хорошо яж не разработчик. Значит мне это уметь не обязательно. Наверно забью. Для успокоения совести сделаю просто сортировку вытянуть элементы закинуть в массив, а затем новое дерево сформировать отсортированное. Как буду разработчиком тада изучу
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.04.2013, 16:21     Топологическая сортировка #15
попу прижмите к стулу и учитесь...
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
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

думаю понятна суть
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 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 минут
столько флуда, а код никто не смог написать
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
11.04.2013, 16:54     Топологическая сортировка #18
Цитата Сообщение от Ternsip Посмотреть сообщение
Добавлено через 7 минут
столько флуда, а код никто не смог написать
ваш код легко нагуглить - http://algorus.blogspot.ru/2012/12/t...ical-sort.html
Ctrl+C/Ctrl+V все умеют, тут речь шла о реализации в map вроде бы, если я верно понял суть вопроса
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 17:05     Топологическая сортировка #19
abit, Увидел. Но сути это не меняет. Просто, названия вершин - строки.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2013, 12:12     Топологическая сортировка
Еще ссылки по теме:

C++ Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Быстрая сортировка (сортировка методом Хоара) C++
Топологическая сортировка (содержание файла) C++

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

Или воспользуйтесь поиском по форуму:
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
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 минуты
Это ж тоже самое получается что эго тоже нужно переписать в стек, или массив. А потом походу заново загнать в дерево. Ну так это тоже самое получается, что вытянуть из дерева все элементы загнать их в массив, а затем отсортировать. Разница в том, что при топологической сортировке элементы будут в массив попадать отсортировано, ну короче массив потом не нуно будет сортировать, а сразу загнать в дерево. ????? Чото мне так как то кажется.
Yandex
Объявления
12.04.2013, 12:12     Топологическая сортировка
Ответ Создать тему
Опции темы

Текущее время: 02:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru