Форум программистов, компьютерный форум 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.?????
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
12.04.2013, 16:10     Топологическая сортировка #21
ninja2, я привёл пример универсальной топологической сортировки для произвольного ациклического графа. Т.е. работает всегда на любом графе. Дерево - ациклический граф. Если граф не ациклический, то это задача конденсации графа. Могу скинуть, если надо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
13.04.2013, 12:26  [ТС]     Топологическая сортировка #22
Цитата Сообщение от Ternsip Посмотреть сообщение
ninja2, я привёл пример универсальной топологической сортировки для произвольного ациклического графа. Т.е. работает всегда на любом графе. Дерево - ациклический граф. Если граф не ациклический, то это задача конденсации графа. Могу скинуть, если надо.
Нет спасибо.

А не знаешь можно ли с помощью нее отсортировать просто массив int?
Я от пытался не могу никак условие придумать
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
59
60
61
62
//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=10;//kolichectvo elementov vuvodit
int g[10];
int used[10];//massiv elementov kak bu metka
vector<int> res; //vector int как стек
 
 
void dfs(int idx)
{
    cout <<"idx= "<<idx<<endl;
    used[idx] = g[idx];//used[i]=true
    forn(x,n)//в цикле от x до n
        if(g[x]>used[x])//если g[idx][x]&& !used[x] (g[0][0]=false && !(used[x]=true))l;
        {
            cout <<"vvn g["<<x<<"]= "<<g[x]<<" used["<<x<<"]= "<<used[x]<<endl;
            dfs(x);//то снова вызов самой функции
        }
    //cout <<"izn g["<<idx<<"]["<<x<<"]= "<<g[idx][x]<<endl;
    cout <<"push_back_idx= "<<idx<<endl;
    res.push_back(idx);//добавить в конец вершину
}
 
int main()
{
       memset(used,0,sizeof(used));
    srand(time(0));
 
    //zapolnenie macciva
    forn(i,n)
    {
        int k=rand()%10;
        cout <<k<<' ';
        g[i]=k;
    }
    cout <<endl;
    
    
    //zapolnenie res
    forn(i,n)
    {
        cout <<"raz"<<endl;
        
        if(!used[i])
            dfs(i);
    }
 
    for(int i = n-1; i >= 0; --i)
        printf("%d ",res[i]);
 
return 0;   
}
Так же само по нулям сортирует. Надоело мучить, велосипед придумывать или хз.
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
14.04.2013, 05:09     Топологическая сортировка #23
Цитата Сообщение от ninja2 Посмотреть сообщение
А не знаешь можно ли с помощью нее отсортировать просто массив int?
Можно, но не нужно, т.к. она для этого не предназначена.

Чтобы все-таки сделать, нужно для массива построить граф, где вершины будут соответствовать числам, а ребра будут идти из вершин с меньшими числами к вершинам с большими числами. Но смысла в этом никакого нет, т.к. получится квадратичное число ребер, а отсортировать можно и более быстрыми алгоритмами.
AMV007
0 / 0 / 0
Регистрация: 06.06.2013
Сообщений: 2
06.06.2013, 10:20     Топологическая сортировка #24
правильно ли я понял, что топологическая сортировка просто позволяет определить порядок прохода дерева, какие узлы первые, а какие следуют за ними и исходя из этого бинарное дерево, в том числе красно черное топологически отсортировано изначально ?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2013, 10:38     Топологическая сортировка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
06.06.2013, 10:38     Топологическая сортировка #25
AMV007, да, при некоторых обходах этого дерева (например dfs), всегда будет топологически-отсортированная последовательность вершин графа.
Yandex
Объявления
06.06.2013, 10:38     Топологическая сортировка
Ответ Создать тему
Опции темы

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