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

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

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

Студворк — интернет-сервис помощи студентам
Здорова!
Тут от вычитал новое понятие "топологическая сортировка".
Вообщем есть задачка нужно сделать топологическу сортировку описаную в Кнут т1 (второе издание) ст 262.?????
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
11.04.2013, 05:36
Ответы с готовыми решениями:

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

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

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

24
 Аватар для Ternsip
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
12.04.2013, 16:10
Студворк — интернет-сервис помощи студентам
ninja2, я привёл пример универсальной топологической сортировки для произвольного ациклического графа. Т.е. работает всегда на любом графе. Дерево - ациклический граф. Если граф не ациклический, то это задача конденсации графа. Могу скинуть, если надо.
1
 Аватар для ninja2
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
13.04.2013, 12:26  [ТС]
Цитата Сообщение от 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;   
}
Так же само по нулям сортирует. Надоело мучить, велосипед придумывать или хз.
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
14.04.2013, 05:09
Цитата Сообщение от ninja2 Посмотреть сообщение
А не знаешь можно ли с помощью нее отсортировать просто массив int?
Можно, но не нужно, т.к. она для этого не предназначена.

Чтобы все-таки сделать, нужно для массива построить граф, где вершины будут соответствовать числам, а ребра будут идти из вершин с меньшими числами к вершинам с большими числами. Но смысла в этом никакого нет, т.к. получится квадратичное число ребер, а отсортировать можно и более быстрыми алгоритмами.
1
0 / 0 / 0
Регистрация: 06.06.2013
Сообщений: 2
06.06.2013, 10:20
правильно ли я понял, что топологическая сортировка просто позволяет определить порядок прохода дерева, какие узлы первые, а какие следуют за ними и исходя из этого бинарное дерево, в том числе красно черное топологически отсортировано изначально ?
0
 Аватар для Ternsip
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
06.06.2013, 10:38
AMV007, да, при некоторых обходах этого дерева (например dfs), всегда будет топологически-отсортированная последовательность вершин графа.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
06.06.2013, 10:38

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

Топологическая сортировка
Требуется организовать топологическую сортировку на примере списка изучаемых дисциплин.Список берётся из эксель-файла.Все предложения(в том...

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

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

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


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

Или воспользуйтесь поиском по форуму:
25
Ответ Создать тему
Новые блоги и статьи
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался)))
anaschu 30.06.2026
Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .
сукцессия 16. Общий обзор, в основном что бы другие ии поняли
anaschu 29.06.2026
# Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru