Графы их использование

11

16

Содержание

1. Задание

2. Основные сведения о графах

3. Использование модулей в программе

4. Структура данных

5. Функциональная схема

6. Описание программы и подпрограмм

7. Листинг программы

8. Результат работы программы

Задание.

Вариант №23

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

2. Основные сведения о графах

Графом называется конечное множество вершин, соединенных ребрами. Если ребра являются направленными, то граф называется ориентированным (орграфом). Направленные ребра часто называют дугами. Каждое ребро соединяет две вершины, причем, в графе две вершины соединяются только одним ребром. В противоположном случае используется понятие мультиграфа (графа с кратными или параллельными ребрами).

Две вершины графа называются смежными, если они соединены ребром. Вершина инцидентна ребру, если ребро соединяет ее с другой какой-то вершиной. Петля - ребро, соединяющее вершину саму с собой. Степень вершины - это число инцидентных ей ребер. Цепью называется последовательность неповторяющихся ребер, соединяющих какие-либо две вершины графа. Замкнутая цепь в графе называется циклом.

Каждая дуга орграфа имеет начало и конец, соответственно, дуга (ребро) выходит из вершины или входит в вершину, и понятие смежности для орграфа не является симметричным. Для каждой вершины определяют полустепень исхода (число выходящих ребер). Для орграфа вместо понятий цикл и цепь используются понятия контур и путь.

Ребра графа могут иметь вес, который может интерпретироваться, например, как длинна ребра.

Графы являются одной из наиболее часто используемых математических структур, так как они удобны для задания связи между объектами.

3. Использование модулей в программе

Модуль Crt содержит процедуры и функции управления тестовым выводом на экран дисплея, и чтения клавиатуры.

Стандартные процедуры (модуля crt)

clrscr - очищает экран и помещает курсор в левый верхний угол.

gotoxy - перемещает курсор по заданным координатам.

textcolor - задает цвет выводимого на экран текста.

readkey- читает символ из буфера клавиатуры.

4. Структура данных

type

ukaz=^uzel;

point=^duga;

t_ukaz=^temp;

uzel=record {структура узла графа}

ishod, konec, name: string[20];

x, y: byte;

pr: char;

next: ukaz; {следующий}

svd: point; {связь с дугой}

pred: ukaz; {предыдущий}

end;

duga=record {структура дуги графа}

name: string[25];

next: point;

svv: ukaz;

{связь с вершиной}

pred_v: ukaz;

end;

temp=record

{структура временных указателей}

s_duga: point;

{связь с дугой}

next: t_ukaz;

end;

var

str, fname, st: string;

top, p, pp, p_p, out_p, in_p: ukaz;

{указатели на узлы графа}

d_p, d_pp: point;

{указатели на дуги графа}

t_top, t_p, t_pp, t_t, t_tt, t_v, t_end: t_ukaz;

{временные указатели}

ch: char;

j, i, k, l, c, y, min, x, shag, kol_cikl: word;

cikl, povtor, ex, exit_s: boolean;

f: text;

spisok: array[1..100] of string;

{файл-список всевозможных обменов}

5. Функциональная схема

11

16

6. Описание программы

Программа написана на языке Borland Pascal 7.1. Программа состоит из главной программы и подпрограмм.

Peshat-

Clear-

Menu-

Zapros-

CreateGraph-

Poisk-

7. Листинг программы

uses crt;

type

ukaz=^uzel;

point=^duga;

t_ukaz=^temp;

uzel=record

{структура узла графа}

ishod, konec, name: string[20];

x, y: byte;

pr: char;

next: ukaz; {следующий}

svd: point; {связь с дугой}

pred: ukaz; {предыдущий}

end;

duga=record {структура дуги графа}

name: string[25];

next: point;

svv: ukaz; {связь с вершиной}

pred_v: ukaz;

end;

temp=record {структура временных указателей}

s_duga: point; {связь с дугой}

next: t_ukaz;

end;

var

str, fname, st: string;

top, p, pp, p_p, out_p, in_p: ukaz; {указатели на узлы графа}

d_p, d_pp: point; {указатели на дуги графа}

t_top, t_p, t_pp, t_t, t_tt, t_v, t_end: t_ukaz; {временные указатели}

ch: char;

j, i, k, l, c, y, min, x, shag, kol_cikl: word;

cikl, povtor, ex, exit_s: boolean;

f: text;

spisok: array[1..100] of string;

procedure clear; {очистка памяти}

begin

if t_top<>nil then

begin

repeat

t_p:=t_top;

if t_top^.next<>nil then t_top:=t_top^.next

else

begin

t_top^.s_duga:=nil;

t_top:=nil;

end;

t_p^.s_duga:=nil;

dispose(t_p);

t_p:=nil;

until t_p=nil;

end;

if top<>nil then

begin

repeat

p:=top;

if p^.svd<>nil then

begin

d_pp:=p^.svd;

repeat

d_p:=d_pp;

if d_p^.next<>nil then d_pp:=d_p^.next;

dispose(d_p);

if d_p=d_pp then d_pp:=nil;

d_p:=nil;

until d_pp=nil;

end;

if p^.next<>nil then

begin

pp:=p^.next;

top:=pp;

end;

dispose(p);

if p=pp then pp:=nil;

until pp=nil;

end;

end;

procedure createGraph; {создание графа из файла}

begin

assign(f,'c:\Spisok.dat');

reset(f);

while not eof(f) do

begin

readln(f,st);

while length(st)=0 do readln(st);

i:=0;

repeat i:=i+1; until (st[i]='(') or (i>length(st));

if st[i]='(' then

begin

new(p);

p^.svd:=nil; p^.next:=nil;

p^.ishod:=''; p^.konec:=''; p^.name:='';

p^.pr:=#0;

if top=nil then top:=p

else pp^.next:=p;

pp:=p;

i:=i+1;

repeat

p^.name:=p^.name+st[i];

i:=i+1;

until st[i]=')';

repeat i:=i+1; until (st[i]='(') or (i>length(st));

repeat

p^.ishod:=p^.ishod+st[i];

i:=i+1;

until st[i-1]=')';

end;

repeat i:=i+1; until (st[i]='(') or (i>length(st));

if st[i]='(' then

begin

repeat

p^.konec:=p^.konec+st[i];

i:=i+1;

until st[i-1]=')';

end;

end;

pp:=top;

while pp<>nil do

begin

p:=top;

while p<>nil do

begin

if p^.ishod=pp^.konec then

begin

new(d_p);

d_p^.pred_v:=pp;

if pp^.svd=nil then pp^.svd:=d_p

else d_pp^.next:=d_p;

d_pp:=d_p;

d_p^.svv:=p;

d_p^.next:=nil;

end;

p:=p^.next;

end;

pp:=pp^.next;

end;

end;

procedure poisk(kvar1, kvar2: string); {поиск циклов}

begin

p:=top;

pp:=top;

kol_cikl:=1;

repeat

cikl:=true;

p_p:=top;

while p_p<>nil do

begin

p_p^.pr:=#0;

p_p:=p_p^.next;

end;

while (pp^.ishod<>kvar2) and (pp^.next<>nil) do pp:=pp^.next;

if pp^.ishod=kvar2 then

begin

p_p:=pp;

if pp^.konec=kvar1 then

begin

spisok[kol_cikl]:=pp^.name;

kol_cikl:=kol_cikl+1;

end;

repeat

repeat

d_pp:=pp^.svd;

p:=pp;

while (d_pp^.svv^.pr='z') and (d_pp<>nil) do d_pp:=d_pp^.next;

if d_pp<>nil then

begin

pp^.pr:='z';

new(t_p);

t_p^.s_duga:=nil; t_p^.next:=nil;

if t_top=nil then t_top:=t_p

else t_pp^.next:=t_p;

t_pp:=t_p;

t_p^.s_duga:=d_pp;

t_p^.s_duga^.pred_v:=pp;

end

else

repeat

cikl:=true;

while t_pp^.s_duga^.next=nil do

begin

if t_pp<>t_top then

begin

t_p:=t_top;

while t_p^.next<>t_pp do t_p:=t_p^.next;

dispose(t_pp);

t_p^.next:=nil;

t_pp:=t_p;

t_p^.s_duga^.svv^.pr:=#0;

end

else

begin

cikl:=false;

break;

end;

end;

if (not cikl) or (t_top=nil) then break;

t_pp^.s_duga:=t_pp^.s_duga^.next;

d_pp:=t_pp^.s_duga;

while (d_pp^.svv^.pr='z') and (d_pp<>nil) do d_pp:=d_pp^.next;

until d_pp<>nil;

if (not cikl) or (t_top=nil) then break;

pp:=d_pp^.svv;

cikl:=true;

until (pp^.konec=kvar1);

if (not cikl) or (t_top=nil) then break;

if pp^.konec=kvar1 then

begin

cikl:=true;

t_p:=t_top;

writeln;

spisok[kol_cikl]:='';

repeat

spisok[kol_cikl]:=spisok[kol_cikl]+t_p^.s_duga^.pred_v^.name+' -> ';

t_pp:=t_p;

t_p:=t_p^.next;

until t_p=nil;

spisok[kol_cikl]:=spisok[kol_cikl]+pp^.name;

writeln(spisok[kol_cikl]);

kol_cikl:=kol_cikl+1;

repeat

while t_pp^.s_duga^.next=nil do

begin

if t_pp<>t_top then

begin

t_p:=t_top;

while t_p^.next<>t_pp do t_p:=t_p^.next;

dispose(t_pp);

t_p^.next:=nil;

t_pp:=t_p;

t_p^.s_duga^.svv^.pr:=#0;

cikl:=true;

end

else

begin

cikl:=false;

break;

end;

end;

if not cikl then break;

t_pp^.s_duga:=t_pp^.s_duga^.next;

d_pp:=t_pp^.s_duga;

while (d_pp^.svv^.pr='z') and (d_pp<>nil) do d_pp:=d_pp^.next;

until d_pp<>nil;

if not cikl then break;

end;

pp:=d_pp^.svv;

until not cikl;

if not cikl then

begin

dispose(t_pp);

t_top:=nil;

end;

pp:=p_p^.next;

end

else break;

until pp=nil;

end;

procedure zapros; {ввод запроса}

var

zap, kvar1, kvar2, text: string;

ok: boolean;

i, temp, pos: byte;

cod: integer;

begin

writeln('ВНИМАНИЕ: исходный файл должен быть: C:\SPISOK.DAT',#10);

pos:=0;

repeat

pos:=pos+1;

if pos=1 then writeln('МЕНЯЕМ: ');

if pos=2 then writeln(#10,'HA: ');

repeat

write (' Количество квартир: ');

readln(zap);

val(zap, temp, cod);

until cod=0;

kvar2:='('+zap+'/{';

for i:=1 to temp do

begin

repeat

write(' Количество комнат в ',i,'-й квартире: ');

readln(zap);

val(zap, temp, cod);

until cod=0;

kvar2:=kvar2+zap+' ';

end;

kvar2[length(kvar2)]:='}';

kvar2:=kvar2+')';

if pos=1 then kvar1:=kvar2;

until pos=2;

poisk(kvar1,kvar2);

end;

procedure menu;

begin

clrscr;

createGraph;

zapros;

end;

procedure pechat; {печать результатов}

begin

repeat

exit_s:=true;

for i:=1 to kol_cikl-1 do

if length(spisok[i])>length(spisok[i+1]) then

begin

st:=spisok[i];

spisok[i]:=spisok[i+1];

spisok[i+1]:=st;

exit_s:=false;

end;

until exit_s;

clrscr;

assign(f,'c:\out.dat');

rewrite(f);

for i:=1 to kol_cikl do writeln(f,spisok[i]);

close(f);

writeln('По запросу найдено ',kol_cikl-1,' вариантов обмена');

writeln(#10,'Результат смотрите в файле: OUT.DAT');

end;

BEGIN

menu;

clear;

if kol_cikl>1 then pechat

else writeln(#10,'ПО ДАННОМУ ЗАПРОСУ НИЧЕГО НЕ НАЙДЕНО');

readln;

END.

8. Результат работы программы

Обход вершин графа, строящегося при работе программы, имеет вид: