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

C++

Войти
Регистрация
Восстановить пароль
 
kalyashov
0 / 0 / 0
Регистрация: 19.10.2014
Сообщений: 40
#1

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

02.03.2015, 18:23. Просмотров 397. Ответов 0
Метки нет (Все метки)

Есть алгоритм, реализация с помощью обхода в глубину: http://rain.ifmo.ru/cat/view.php/vis...2007/algorithm
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   boolean topological_sort(){
       boolean Cycle;
       for(int i = 1;i <= N;i ++){
           Cycle = dfs(i);
           if(Cycle)return false;
       }
       for(int i = 1;i <= n;i ++){
           Numbers[Stack.pop()] = i;
       }
      return true;
  }
  boolean dfs(int v){
      if(Color[v] == 1)return true;
      if(Color[v] == 2)return false;
      Color[v] = 1;
      for(int i = 0;i < Edges[v].size();i ++){
          if(dfs(Edges[v].get(i)))return true;
      }
      Stack.push(v);
      Color[v] = 2;
      return false;
}
Процедура возвращает true, если граф был топологически отсортирован, иначе возвращается false.

Color — массив, в котором хранятся цвета вершин (0 — белый, 1 — серый, 2 — черный).
N — количество вершин.
Edges — массив списков смежных вершин.
Numbers — массив, в котором сохраняются новые номера вершин.
Stack — стек, в котором складываются вершины после их обработки.
Cycle — принимает значение true, если в графе найден цикл.

Описание:
3—6. Вызывается обход в глубину от всех вершин. Заканчиваем работу алгоритма, если обнаружен цикл.
7—9. Заносим в массив новые номера вершин.
13—14. Если вершина серая, то мы обнаружили цикл. Заканчиваем поиск в глубину.
14. Если вершина черная, то заканчиваем ее обработку.
15. Красим вершину в серый цвет.
16—18. Обрабатываем список смежных с ней вершин.
19. Кладем вершину в стек.
20. Красим вершину в черный цвет.

Не могу разобраться как это все работает, и как применить эту сортировку к ориентированному графу, который задан матрицей смежности, и вернуть результат сортировки? Кто-нибудь может показать на реальном примере?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.03.2015, 18:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Топологическая сортировка (C++):

Сортировка методом Шелла и быстрая сортировка - C++ Builder
Помогите найти код для функций в виде кусков кода сортировок...

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

Топологическая сортировка - C++
Здорова! Тут от вычитал новое понятие &quot;топологическая сортировка&quot;. Вообщем есть задачка нужно сделать топологическу сортировку описаную...

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

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется - C++
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком или сортировка Шелла. Вот она то и не...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include &lt;iostream&gt; ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.03.2015, 18:23
Привет! Вот еще темы с ответами:

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru