Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.01.2017, 23:08   #1
tako_superuser
Пользователь
 
Регистрация: 13.03.2015
Сообщений: 11
Восклицание !Графы Pascal!

Здравствуйте ув. Форумчане, имеется задача -

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

есть примерный код -

Код:
Program SIAOD_LAB_7;
uses crt;
type list=^S;
S=record
inf:word;
adr1:list;
adr2:list;
end;
var graf:array[1..10] of list;
i,j,k,k1,o,os:integer;
kolver:integer;
PrSpis,PrSpisInc:list;
NeSpis:list;
ObSpis,NeObSpis:List;
 
procedure Spisok1(inf:Word);
var Spis:list;
begin
New(Spis);
Spis^.inf:=inf;
Spis^.Adr1:=Nil;
Spis^.Adr2:=Nil;
PrSpis^.Adr1:=Spis;
PrSpis:=Spis;
If k=0 Then NeSpis:=Spis;
Inc(k);
end;
 
procedure Spisok2(inf:Word);
var Spis:list;
begin
New(Spis);
Spis^.inf:=inf;
Spis^.Adr1:=Nil;
Spis^.Adr2:=Nil;
PrSpisInc^.Adr2:=Spis;
PrSpisInc:=Spis;
Inc(k1);
end;
 
 
procedure SpisokInc;
var ve,re:Integer; Spis:list;
begin
k:=0;
NeSpis:=Nil;
Spis:=NeSpis;
Write('Vvedite kol-vo vershin: ');
Read(kolver);
for i:=1 to kolver do
begin
Spisok1(i);
Write('Vvedite kol-vo reber dla vershini ', i,'= ');
Readln(re);
PrSpisInc:=PrSpis;
k1:=0;
for j:=1 to re do
begin
Write('Vvedite vershiny, v = ');
Readln(ve);
Spisok2(ve);
end;
end;
end;
 
procedure obhod;
var f:boolean; Spis, Spp:list; ve:integer;
begin
f:=false;
Spis:=NeSpis;
ve:=Spis^.inf;
Spp:=NeSpis;
for i:=1 to kolver do
begin
собственно начиная от сюда
if Spis^.inf=0 then
begin
writeln ('Y vershini net dug')
end
else
begin
writeln ('Dygi est');
end;
{while (Spis<>Nil) do
begin
ve:=Spis^.inf;
if not obhod(ve) then writeln('Vvvvvv');
Spis:=Spis^.Adr2;
end;
Spis:=Spp^.Adr1;
Spp:=Spis;}
 И заканчивая тут я делаю что то не то....
end;
end;
 
begin
clrscr;
spisokinc;
if kolver<>0 then
begin
 
obhod;
end
else
Writeln('Versin net');
writeln('Nagmite klavishu');
repeat until keypressed;
END.
Вопрос - в чём тут ошибка, почему он не компилируется?

Последний раз редактировалось tako_superuser; 07.01.2017 в 23:41. Причина: ер
tako_superuser вне форума Ответить с цитированием
Старый 08.01.2017, 10:29   #2
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

Как я понимаю, вам нужно выполнить поиск компонент связности.
http://www.e-maxx-ru.1gb.ru/algo/connected_components
И по результатам обхода вывести сообщение о принадлежности некоей вершины некоему подграфу (компоненту связности).

Т.к. у вас орграф, то алгоритм будет несколько сложнее - возможно объединение компонент связности (когда из текущей исследуемой компоненты обнаружилась односторонняя связь на уже просмотренную и нумерованную компоненту).

По поводу программы - это кошмар, т.к. отсутствует форматирование и используются только глобальные переменные. Тут может быть что угодно.

В программе видны строки "собственно начиная от сюда", которые не будут компилироваться.

По алгоритму.
Создаёте массив по числу вершин
Код:
ConnectedComponents: array[1..kolver] of integer
При обходе в глубину, всем вершины в компоненте назначаете один номер.
Потом начинаете искать следующую компоненту связности тем же обходом.
Возможен случай, когда очередная исследуемая вершина уже принадлежит какой-то компоненте - берёте и переименовываете на этот номер текущую компоненту и продолжаете исследование.

Последний раз редактировалось FPaul; 08.01.2017 в 10:36.
FPaul вне форума Ответить с цитированием
Старый 08.01.2017, 20:11   #3
tako_superuser
Пользователь
 
Регистрация: 13.03.2015
Сообщений: 11
По умолчанию

Цитата:
Сообщение от FPaul Посмотреть сообщение
Как я понимаю, вам нужно выполнить поиск компонент связности.
http://www.e-maxx-ru.1gb.ru/algo/connected_components
И по результатам обхода вывести сообщение о принадлежности некоей вершины некоему подграфу (компоненту связности).

Т.к. у вас орграф, то алгоритм будет несколько сложнее - возможно объединение компонент связности (когда из текущей исследуемой компоненты обнаружилась односторонняя связь на уже просмотренную и нумерованную компоненту).

По поводу программы - это кошмар, т.к. отсутствует форматирование и используются только глобальные переменные. Тут может быть что угодно.

В программе видны строки "собственно начиная от сюда", которые не будут компилироваться.

По алгоритму.
Создаёте массив по числу вершин
Код:
ConnectedComponents: array[1..kolver] of integer
При обходе в глубину, всем вершины в компоненте назначаете один номер.
Потом начинаете искать следующую компоненту связности тем же обходом.
Возможен случай, когда очередная исследуемая вершина уже принадлежит какой-то компоненте - берёте и переименовываете на этот номер текущую компоненту и продолжаете исследование.
Здравствуйте, огромное спасибо за подробный комментарий, Вы можете сделать данные исправления в моём коде?
tako_superuser вне форума Ответить с цитированием
Старый 08.01.2017, 20:16   #4
tako_superuser
Пользователь
 
Регистрация: 13.03.2015
Сообщений: 11
По умолчанию

Вот собственно эта ошибочка -
Снимок.JPG
tako_superuser вне форума Ответить с цитированием
Старый 09.01.2017, 00:38   #5
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

По-узловая наладка - наше всё. Начните с форматирования (легче будет выполнять анализ кода), потом выполните наладку ввода (с контролем по выводу на экран списков), после этого приступайте к наладке узла обработки.
FPaul вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Pascal | Графы SadBrick Помощь студентам 0 26.11.2013 00:41
Задача.Pascal. Графы. GrukhvinEV Помощь студентам 0 19.12.2011 08:13
Гамильтонов и Эйлеров графы(Pascal) swillrocker Помощь студентам 1 12.12.2011 00:03
Неориентированные графы [Delphi/Pascal] HoLToFF Помощь студентам 2 11.05.2009 21:16