Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal ABC
Войти
Регистрация
Восстановить пароль
 
HkEnot
0 / 0 / 0
Регистрация: 19.11.2017
Сообщений: 8
1

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

09.02.2019, 20:02. Просмотров 170. Ответов 1
Метки нет (Все метки)

Задали задание, неделю пытаюсь сделать и все никак не выходит, топологическая сортировка из книгу Кнута.
Код вроде бы работает до момента вывода ответа, а та стопорится на этой строчке if a[p^.suc] then Push(p^.suc);
Я понимаю, что нельзя сравнивать разные типы данных, но начальный код мне дал научрук.


Pascal
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
Program topolog;
 
uses StQu;
 
type PEL = ^EL;
     EL = record
       suc:Byte;
       lnk:PEL;
     end;
     
const ter = 50;
 
var a:array[1..ter] of record
      cnt:byte; // счетчик предшествиников
      top:PEL;  // список последующих //top:PEL;  
    end;
    n,i,j,k,r,z:Byte; // колиичество вершин;
    p,q:PEL;
        
begin    
// инициализация
  for i:= 1 to ter do begin // от 1 до последней вершины 
    a[i].cnt:=0;
    a[i].top:=nil;
  end;
  n:=0; // счетчик вершин   
  
// ввод значений в запись
  Read(j,k); // записываем пары чисел 
  While k<>0 do begin // условием завершения ввода является чило 0 
    Inc(a[k].cnt);
    new(p);
    p^.suc:=k;
    p^.lnk:=a[j].top;
    a[j].top:=p;
    Read(j,k);
    Inc(n); //считаем вершины
  end;
  
// создания списка нулей
  //stk.ini; // обнуляем стек
  Ini;
  for i:= 1 to n do begin // пробеггаем по всем вершинам
    if (a[i].cnt=0) then Push(i); // если находим 0, то записываем эту вершину с стек
  end;
      
// вывод в нужном порядке на эуран
 
  while not Emp do begin // пока сстеке есть вершины выполнять
    r:=Pop;
    write(r); // выводим на экран
    p:=a[r].top; //p:=a[r]^.top; 
    while p<>nil do begin
      Dec(a[p^.suc].cnt);
      if a[p^.suc] then Push(p^.suc);
      p:=p^.lnk;
    end;
  end; //проходим по списку всех приемников r и каждого из них
       //лишаем предществиника в лице r 
end.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.02.2019, 20:02
Ответы с готовыми решениями:

Выполнить обход в ширину неориентрованного графа, начиная с заданной вершины. Способ представления графа – матрица инциденций
Буду очень благодарен, если поможете Выполнить обход в ширину неориентированного графа, начиная с...

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

Топологическая сортировка графа
Написал программу топологически сортирующую граф с помощью обхода в ширину. Сдал её на информатиксе...

Топологическая сортировка графа
Здравствуйте! Помогите, пожалуйста. Пишу программу для поиска путей на графах между всеми парами...

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

1
HkEnot
0 / 0 / 0
Регистрация: 19.11.2017
Сообщений: 8
09.02.2019, 20:15  [ТС] 2
Граф должен отсортироваться примерно так, на первом фото то что дано, на втором ответ
0
Миниатюры
Топологическая сортировка графа   Топологическая сортировка графа  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2019, 20:15

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

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

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


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

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

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