LAB / _2017-ЛАБОРАТОРНЫЕ РАБОТЫ 2 КУРС / _6_GRAF

ЛАБОРАТОРНАЯ РАБОТА 6

Структуры данных типа "граф"

1.Общие понятия

По определению граф-зто структура, включающая в себя непустое множество

V, называемое множеством вершин(точек,узлов) графа, множество Е, представляю-

щее собой множество ребер графа, и отображение Ф мнжества ребер Е на множе-

ствопар элементов из V.

Графы являются удобной структурой для отображения связей в большом

классе реальных объктов и ,следовательно, для организации структур данных и

решения большщго класса разнообразных задач.

Элементами графа в структурах данных могут быть, в частности, записи,

организованные в многосвязанные списки

2.Цель работы

Целью работы является изучение и отработка приемов и навыков использования

графов в организации алгоритмических структур и структур хранения информа-

ции.Машинная реализация этих структур планируется на языке Турбо Паскаль

или С++ и занимает 6 часов.

3.Варианты заданий на выполнение работы

При выполнении заданий следует задействовать стандартные операции

работы с графами, каждая из которых должна быть оформлена в виде отдельной

функции или процедуры. Во всех заданиях, приведенных ниже, в качестве обяза-

тельных операций должны присутствовать: вывод любого элемента на экран и

удаленияе любого элемента из графа.

1. Разработать процедуру построения минимального остовного дерева, исполь-

зуя алгоритм Прима.

2. Разработать процедуру построения матрицы путей "n"-порядка.

3. Разработать процедуру построения транзитивного замыкания на основе

матриц путей.

4. Разработать процедуру построения транзитивного замыкания на основе

алгоритма Уоршела.

5. Использование графа для решения задачи о потоках (алгоритм Форда-Фул-

керсона).

6. Использование графа для решения первой задачи сетевого планирования.

7. Использование графа для решения второй задачи сетевого планирования.

8. Организовать хранение записей в виде графа на основе связанных спис-

ков и разрабоать процедуру исключения вершины вместе со смежными ребрами.

9. Организовать хранение записей в виде графа на основе связанных спис-

ков и разрабоать процедуру исключения подграфа записей.

10. Организовать хранение записей в виде графа на основе связанных спис-

ков и разрабоать процедуру включения подграфа записей.

11. Организовать хранение записей в виде графа на основе связанных спис-

ков и разрабоать процедуру исключения дублированных записей.

12. Организовать хранение записей в виде графа на основе связанных спис-

ков и разрабоать процедуру вывода данных из прафа, удовлетворяющих какому-

-либо критерию.

13 . Разработать простейшую базу данных на основе графа.

14. Из графовидной структуры хранения вывести список студентов, получивших

на экзамене одинаковые оценки.

15. Организовать хранение записей в виде двух графов на основе связанных

списков и разрабоать процедуру вычитания графов.

16. Организовать хранение записей в виде двух графов на основе связанных

списков и разработать процедуру объединения графов.

17. Написать программу обхода конем всего шахматного поля, посещая каждую

клетку только один раз.

18. Расставить на шахматной доске 8 ферзей таким образом, чтобы каждый из

них не находился под "боем" других.

19. Смоделировать случайным образом лабиринт и найти выход из него.

20. Во взвешанном графе найти остовное дерево, имеющее наибольшую "стои-

мость".

4. Пояснения к выполнению лабораторной работы

Графовидная структура как ни одна другая может служить основой для

решения разнообразного и широкого класса задач. Это накладывает свои осо-

бенности на применение этой структуры. В частности, описание графов для

различных задач может быть различным (графы могут быть описаны в одном

из матричных видов, либо в виде многосвязанных или двухсвязанных списков)

и поэтому прежде всего следует решить вопрос об оптимальном описании графа

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

литературу, курс лекций, знания и навыки полученные на практических за-

нятиях, произвести хорошую предварительную алгоритмическую проработку

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

практически на нерешаемые затруднения, тогда как удачное сочетание изучения

известных алгоритмов с преломлением на конкретные задания позволит су-

существенно упростить программную реализацию решения задачи.

Надо отметить также, что число стандартных операций как и для дерева дос-

таточно велико (их перечень является предметом изучения других видов заня-

тий: лекционных и практических). Однако следует помнить при их применении ,

что элементом графа является не только вершина (т.е. собственно элемент),

но и ребро или дуга (т.е. связь между элементами).

ПРИЛОЖЕНИЕ 1

Пример программы с использованием графовидной структуры

Построить остовное дерево, используя алгоритм Краскала. Самым сложным

элементом в указанном алгоритме является организация проверки цикла. В при-

веденной далее программе на Турбо Паскале эта проверка организована при по-

мощи гибко взаимодействующих между собой процедур.

program graft;

uses crt;

const

a=20;

c=200;

type

ver =record {ребро графа}

inp: byte;

out: byte;

isv: byte;

osv: byte;

dl: real;

end;

gro=record

n: byte;

x:real;

y:real;

end;

graf=array[1..a] of gro;

dlgraf=array[1..c] of ver;

var

ch:char;

n,m,mm,n0,ll,kk,i,j,m0:byte;

matr: array[1..a,1..a] of byte;

gr:graf;

dlgr:dlgraf;

{*****************************************************************

Ввод числа вершин и их координат

******************************************************************}

procedure inpgraf(var n:byte;var gr:graf);

var

i: integer;

xx,yy:real;

begin

writeln('Введите число вершин');

read(n);

writeln('Введите попарно координаты вершин');

for i:=1 to n do

begin

write('Вершина : ',i:2,' ');

readln(xx,yy);

gr[i].n:=i;

gr[i].x:=xx;

gr[i].y:=yy;

end;

end;

{*****************************************************************

Определение длин ребер полного графа и форми-

рование полей записи dlgr

******************************************************************}

procedure dlingraf(gr:graf;n:byte;var dlgr:dlgraf;var m:byte);

var

g,v : integer;

begin

m:=0;

for g:=1 to n do

for v:=1+g to n do

begin

if g<>v then

begin

m:=m+1;

dlgr[m].inp:=g;

dlgr[m].out:=v;

dlgr[m].dl:=sqrt(sqr(gr[v].x-gr[g].x)+sqr(gr[v].y-gr[g].y));

dlgr[m].isv:=0;

dlgr[m].osv:=0;

end;

end;

end;

{*****************************************************************

Сортировка длин ребер в порядке возрастания

******************************************************************}

procedure sortgraf(m:byte;var dlgr:dlgraf);

var

i,j,ii,oo : byte;

dd:real;

begin

for i:=1 to m-1 do

for j:=1 to m-i do

begin

if dlgr[j].dl>dlgr[j+1].dl then

begin

dd:=dlgr[j+1].dl;

ii:=dlgr[j+1].inp;

oo:=dlgr[j+1].out ;

dlgr[j+1].dl:=dlgr[j].dl;

dlgr[j+1].inp:=dlgr[j].inp;

dlgr[j+1].out:=dlgr[j].out ;

dlgr[j].dl:=dd;

dlgr[j].inp:=ii;

dlgr[j].out:=oo;

end;

end;

end;

{****************************************************************

Проверка принадлежности текущего ребра соответствующему подграфу

****************************************************************}

procedure svgraf(m0:byte;var dlgr:dlgraf);

var

i : integer;

begin

i:=0;

while((i<m0-1)and((dlgr[m0].isv=0)or(dlgr[m0].osv=0))) do

begin

i:=i+1;

if(dlgr[i].inp<>0)and(dlgr[m0].inp=dlgr[i].inp)

then

begin

dlgr[m0].isv:=dlgr[i].isv;

end;

if(dlgr[i].inp<>0)and(dlgr[m0].inp=dlgr[i].out)

then

begin

dlgr[m0].isv:=dlgr[i].osv;

end;

if(dlgr[i].out<>0)and (dlgr[m0].out=dlgr[i].out)

then

begin

dlgr[m0].osv:=dlgr[i].osv;

end;

if(dlgr[i].out<>0)and(dlgr[m0].out=dlgr[i].inp)

then

begin

dlgr[m0].osv:=dlgr[i].isv;

end;

end;

end;

{*********************************************************

Проверка на наличие цикла

*********************************************************}

function nocycle(m0:byte;dlgr:dlgraf):boolean;

begin

if (dlgr[m0].isv=dlgr[m0].osv) then nocycle:=false

else nocycle:=true;

end;

{****************************************************************

Объединение подграфов

****************************************************************}

procedure ungraf(m0:byte;var dlgr:dlgraf);

var

i,ji,jo,jsv : integer;

begin

ji:=dlgr[m0].isv; jo:=dlgr[m0].osv;

for i:=1 to m0-1 do

begin

if(dlgr[i].osv=dlgr[m0].osv) then

dlgr[m0].isv:=dlgr[i].isv;

if(dlgr[i].isv=dlgr[m0].isv) then

dlgr[m0].osv:=dlgr[i].osv;

end;

if ji<>dlgr[m0].isv then jsv:=ji;

if jo<>dlgr[m0].osv then jsv:=jo;

for i:=1 to m0-1 do

begin

if dlgr[i].osv=jsv then

begin

dlgr[i].osv:=dlgr[m0].osv;

dlgr[i].isv:=dlgr[m0].osv;

end;

end;

end;

{**** программа ******}

BEGIN

clrscr;

repeat

inpgraf(n,gr); {ввод вершин и их координат}

{ подготовка матрицы смежности }

for i:=1 to n do

for j:=1 to n do

matr[i,j]:=0;

dlingraf(gr,n,dlgr,m0);{расчет длин ребер}

sortgraf(m0,dlgr); {сортировка по возрастанию длин ребер}

matr[dlgr[1].inp,dlgr[1].out]:=1;

matr[dlgr[1].out,dlgr[1].inp]:=1;

dlgr[1].isv:=1;

dlgr[1].osv:=1;

mm:=1;

n0:=1;

while(n0<n-1) do

begin

mm:=mm+1;

svgraf(mm,dlgr); {проверка на принадлежность к подграфу}

{обработка текущего ребра}

if (dlgr[mm].isv<>0)or(dlgr[mm].osv<>0) then

begin

if (dlgr[mm].isv<>dlgr[mm].osv) then

begin

matr[dlgr[mm].inp,dlgr[mm].out]:=1;

matr[dlgr[mm].out,dlgr[mm].inp]:=1;

ungraf(mm,dlgr);

n0:=n0+1;

end

else

if nocycle(mm,dlgr)=true then

begin

matr[dlgr[mm].inp,dlgr[mm].out]:=1;

matr[dlgr[mm].out,dlgr[mm].inp]:=1;

n0:=n0+1;

end

end

else

begin

matr[dlgr[mm].inp,dlgr[mm].out]:=1;

matr[dlgr[mm].out,dlgr[mm].inp]:=1;

n0:=n0+1;

dlgr[mm].isv:=n0;

dlgr[mm].osv:=n0;

end

end;

writeln('Матрица смежности');

write(' !');

for j:=1 to n do

write(j:4);

writeln;

write(' !');

for j:=1 to n do

write('____');

writeln;

for i:=1 to n do

begin

write(i:4,' !');

for j:=1 to n do

write(matr[i,j]:4);

writeln;

end;

writeln('Для окончания работы нажмите - ESC');

until readkey=#27;

END.

ПРИЛОЖЕНИЕ 2

Пример программы с использованием графовидной структуры

на языке С++

Ниже приведен текст программы на С++ для задачи, указанной в Приложении 1.

/* !!=============================!!

!! Алгоритм Краскала !!

!!=============================!! */

#include <dos.h>

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <mem.h>

#include <math.h>

typedef

struct reb{ /* ребро графа */

int inp;

int out;

int isv;

int osv;

float dl;

};

typedef

struct ver{ /* вершины графа */

int n;

float x;

float y;

};

void inpgraf(int *n,struct ver *dlg);

void dlingraf(struct ver *gg,int n,struct reb *dlg,int *m);

void sortgraf(int m,struct reb *dlgr);

void svgraf(int m0,struct reb *g);

char nocycle(int m0,struct reb *dlg);

void ungraf(int m0,struct reb *dlg);

/* {**** программа ******} */

void main()

{

struct ver gr[20],*g;

struct reb dlgr[100],*dlg;

char ch;

int n,m,mm,n0,i,j,m0;

int matr[20][20],*pma,*pmabeg;

pma=&matr[0][0];

g=&gr[0];

dlg=&dlgr[0];

n=0;

inpgraf(&n,g); /* {ввод вершин и их координат}*/

/* подготовка матрицы смежности */

for(i=0;i<n;i++)

{ for (j=0;j<n;j++,pma++)

*pma=0;

pma=pma+20-n;

}

pma=&matr[0][0];

dlingraf(&*g,n,&*dlg,&m0); /* расчет длин ребер */

sortgraf(m0,&*dlg); /* сортировка по возрастанию длин ребер */

matr[dlg->inp][dlg->out]=1;

matr[dlg->out][dlg->inp]=1;

dlg->isv=0;

dlg->osv=0;

mm=0;

n0=1;

/* matr[dlgr[1].inp,dlgr[1].out]:=1;

matr[dlgr[1].out,dlgr[1].inp]:=1;

dlgr[1].isv:=0;

dlgr[1].osv:=0;

mm:=1

n0:=1;*/

dlg=&dlgr[0];

while(n0<n-1)

{ mm++; dlg++;

svgraf(mm,dlgr); /*проверка на принадлежность к подграфу*/

/* {обработка текущего ребра} */

if ((dlg->isv!=-1)||(dlg->osv!=-1))

{ if (dlg->isv!=dlg->osv)

{ matr[dlg->inp][dlg->out]=1;

matr[dlg->out][dlg->inp]=1;

ungraf(mm,dlgr);

n0=n0+1;

}

else

if (nocycle(mm,dlgr)==1)

{ matr[dlg->inp][dlg->out]=1;

matr[dlg->out][dlg->inp]=1;

n0=n0+1;

}

}

else

{ matr[dlg->inp][dlg->out]=1;

matr[dlg->out][dlg->inp]=1;

n0=n0+1;

dlg->isv=n0;

dlg->osv=n0;

}

}

printf("Матрица смежности\n");

printf(" !");

for(j=1;j<n+1;j++)

printf("%i ",j);

printf("\n");

printf(" !");

for(j=1;j<n+1;j++)

printf("____");

printf("\n");

for(i=1;i<n+1;i++)

{ printf(" %i !",i);

for(j=1;j<n+1;j++)

printf("%i ",matr[i-1][j-1]);

printf("\n");

}

}

/* *****************************************************************

Ввод числа вершин и их координат

***************************************************************** */

void inpgraf(int *n,struct ver *gg)

{

struct ver *g;

float xx,yy;

int i;

g=gg;

printf("Введите число вершин\n");

scanf("%d",&*n);

printf("Введите попарно координаты вершин\n");

printf("\n");

for(i=1; i<*n+1;i++,g++)

{

printf("Вершина : %d\n",i);

scanf("%f %f",&xx,&yy);

g->n=i-1;

g->x=xx;

g->y=yy;

}

}

/* *****************************************************************

Определение длин ребер полного графа и форми-

рование полей записи dlgr

****************************************************************** */

void dlingraf(struct ver *gg,int n,struct reb *dlg,int *m)

{

struct ver *gr,*ggr;

struct reb *dlgr;

float a,s;

int g,v ;

dlgr=dlg;

*m=0;

for(g=0,gr=gg;g<n;g++,gr++)

for(v=g,ggr=gg+g; v<n;v++,ggr++)

{

if (g!=v)

{ *m=*m+1;

dlgr->inp=g;

dlgr->out=v;

a=((gr->x)-(ggr->x))*((gr->x)-(ggr->x));

s=((gr->y)-(ggr->y))*((gr->y)-(ggr->y));

a=sqrt(a+s);

dlgr->dl=a;

dlgr->isv=-1;

dlgr->osv=-1;

dlgr++;

}

}

}

/* *****************************************************************

Сортировка длин ребер в порядке возрастания

****************************************************************** */

void sortgraf(int m,struct reb *dlg)

{

int i,j,ii,oo ;

float dd;

struct reb *dlgr;

dlgr=dlg;

for (i=0 ;i< m-2 ;i++)

for(j=0,dlgr=dlg;j<m-1-i;j++,dlgr++)

{if (dlgr->dl>(dlgr+1)->dl)

{dd=(dlgr+1)->dl;

ii=(dlgr+1)->inp;

oo=(dlgr+1)->out ;

(dlgr+1)->dl=dlgr->dl;

(dlgr+1)->inp=dlgr->inp;

(dlgr+1)->out=dlgr->out ;

dlgr->dl=dd;

dlgr->inp=ii;

dlgr->out=oo;

}

}

}

/* ****************************************************************

Проверка принадлежности текущего ребра соответствующему подграфу

**************************************************************** */

void svgraf(int m0,struct reb *g)

{

int i ;

i=-1;

while((i<m0-1)&&(((g+m0)->isv==-1)||((g+m0)->osv==-1)))

{ i++;

if(((g+i)->inp!=-1)&&((g+m0)->inp==(g+i)->inp))

(g+m0)->isv=(g+i)->isv;

if(((g+i)->inp!=-1)&&((g+m0)->inp==(g+i)->out))

(g+m0)->isv=(g+i)->osv;

if(((g+i)->out!=-1)&&((g+m0)->out==(g+i)->out))

(g+m0)->osv=(g+i)->osv;

if(((g+i)->out!=-1)&&((g+m0)->out==(g+i)->inp))

(g+m0)->osv=(g+i)->isv;

}

}

/* *********************************************************

Проверка на наличие цикла

********************************************************* */

char nocycle(int m0,struct reb *dlg)

{ struct reb *dlgr;

dlgr=dlg+m0;

if(dlgr->isv==dlgr->osv) return(0);

else return(1);

}

/* *********************************************************

Объединение подграфов

********************************************************* */

void ungraf(int m0,struct reb *dlg)

{ int i,ji,jo,jsv;

ji=(dlg+m0)->isv; jo=(dlg+m0)->osv;

for (i=0;i<m0;i++)

{ if((dlg+i)->osv==(dlg+m0)->osv)

(dlg+m0)->isv=(dlg+i)->isv;

if((dlg+i)->isv==(dlg+m0)->isv)

(dlg+m0)->osv=(dlg+i)->osv;

}

if(ji!=(dlg+m0)->isv) jsv=ji;

if(jo!=(dlg+m0)->osv) jsv=jo;

for(i=0;i<m0;i++)

if((dlg+i)->osv==jsv)

{ (dlg+i)->osv=(dlg+m0)->osv;

(dlg+i)->isv=(dlg+m0)->isv;

}

}