1. Постановка задачи
2. Использование динамических структур при работе с графами
2.1. Способы представления графов
2.2. Операции над графами
2.3. Описание программной реализации
2.3.1. Описание процедур и функций языка
2.3.2. Описание функций работы с динамической памятью, графами
Выводы
Приложение А Экранные формы
Приложение Б Листинг программы
1 ПОСТАНОВКА ЗАДАЧИ
Задача.
Найти все источники ориентированного графа.
Исходные данные:
- номер вершины (цел типа), вводимый пользователем;
- дуга графа, задается двумя вершинами источником и стоком, вводимая пользователем.
Промежуточные данные:
Head:TUk – указатель на голову списка смежности графа;
n,m:цел – номера вершин;
c:сим – клавиша события.
Результаты:
V:массив байт – массив вершин источников;
Ограничения:
max=10 – максимальное количество вершин;
V:массив [1..max*max].
2. Использование динамических структур при работе с графами
2.1 Способы представления графов
Способы задания графов:
- матрица смежности;
- матрица инцидентности;
- список смежности;
- список дуг (ребер);
- и др.
Список смежности – для вершины v
есть список концов дуг, исходящих из вершины v,
в случае орграфа, или список смежных с v
вершин, в случае неориентированного графа.
Список дуг – это список, в котом каждой дуге ставится в соответствие пара <x,y>
, где x
– начало дуги, а y
– ее конец. Для нагруженных графов – тройка <x,y,z>
,где x
– начало дуги, y
– конец дуги, z
– вес дуги.
Матрица смежности – это квадратная матрица, строки и столбцы которой соответствуют вершинам графа. Элемент матрицы (i,j) равен 1, если вершина i связана с вершиной j ребром, иначе элемент матрицы равен 0.
Для неориентированных графов матрица смежности является симметричной относительно главной диагонали. Т.е. для получения информации о графе достаточно знать верхнюю или нижнюю треугольную матрицу смежности. Для ориентированных графов матрица смежности не является симметричной.
Матрица инцидентности – это матрица, строки которой – список вершин, а столбцы – список ребер. Элемент матрицы инциденций (i,j) равен 1, если вершина i
инцидентна соответствующему ребру.
Для неориентированных графов:
Для ориентированных графов:
Например, дан граф G (см.рис. .1)
Рисунок 2.1 – Граф G
Представление графа списком смежности отображено на рисунке 2.2
Рисунок 2.2 – Список смежности графа G
Представление графа с помощью списка дуг имеет вид отображено на рисунке .3
Рисунок 2.3 – Список дуг графа G
Представление графа с помощью матрицы смежности показано в таблице 2.1
Таблица 2.1 – Матрица смежности
| x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
|
| x1
|
0 | 1 | 1 | 0 | 0 | 0 |
| x2
|
0 | 0 | 0 | 0 | 0 | 0 |
| x3
|
0 | 1 | 0 | 1 | 1 | 0 |
| x4
|
0 | 0 | 0 | 0 | 1 | 0 |
| x5
|
0 | 0 | 0 | 0 | 0 | 1 |
| x6
|
0 | 0 | 0 | 1 | 0 | 0 |
Представление графа с помощью матрицы инцидентности показано в таблице 2.2
Таблица 2.2 – Матрица инцидентности
| x
1 x 2 |
x
1 x 3 |
x
3 x 2 |
x
3 x 4 |
x
3 x 5 |
x
4 x 5 |
x
5 x 6 |
x
6 x 4 |
|
| x
1 |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| x
2 |
-1 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
| x
3 |
0 | -1 | 1 | 1 | 1 | 0 | 0 | 0 |
| x
4 |
0 | 0 | 0 | -1 | 0 | 1 | 0 | -1 |
| x5
|
0 | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
| x6
|
0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 |
2.2 Операции над графами
При решении поставленной задачи для представления графа был выбран список смежности.
typeTUk1=^TEl1; //элемент списка вершин
TEl1=record
Next:TUk1;
Inf:integer;
end;
TUk=^TEl;
TEl=record //элементспискасмежности
Left:TUk1;
Inf:integer;
Down:TUk;
end;
Head:TUk; //указатель на начало списка
Схематичное представление списка смежности ориентированного графа представлено на рисунке 2.1
Рисунок 2.3 – Схема списка смежности
Алгоритм нахождения источников ориентированного графа представлен на рисунке 2.4.
Рисунок 2.4 - Алгоритм нахождения источников орграфа
2.3 Описание программной реализации
2.3.1 Описание процедур и функций языка
Процедура New –
резервирует фрагмент кучи для размещения переменной; формат обращения
New(TP)
TP – типизированный указатель. За одно обращение к процедуре можно зарезервировать не более 65521 байт динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.
Процедура Dispose – возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за типизированным указателем; формат обращения
Dispose (TP)
TP – типизированный указатель. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения.
2.3.2 Описание функций работы с динамической памятью, графами
Для решения поставленной задачи были разработаны следующие процедуры и функции:
1) procedureAddVer(n:integer); - добавление в список смежности вершины с номером n;
2) procedureAddDug(n,m:integer); - добавление в список дуги (n,m). n и m номера вершин источника дуги и стока соответственно;
3) procedureDelList(p:TUk1); - удаление списка смежных вершин. p – указатель на начало списка;
4) procedureDelVer(n:integer); - удаление вершины с номером n;
5) procedureDelDug(n,m:integer); - удаление дуги (n,m). n и m номера вершин источника дуги и стока соответственно;
6) procedurePrintGraph; - вывод списка смежности на экран в виде матрицы смежности;
7) procedureFindIstok; - поиск и вывод на экран всех источников орграфа.
ВЫВОДЫ
Задание, выданное на летнюю практику, поставило определенные задачи:
1) научится создавать связные структуры данных, используя указатели;
2) научится создавать и манипулировать динамическими структурами данных, такими как связные списки, очереди и стеки;
3) понять работу различных приложений со связными структурами данных.
Решение выданного задания было реализовано с помощью языка программирования Паскаль.
Во время прохождения учебной практики был закреплен теоретический материал по разработке д
Приложение А
ЭКРАННЫЕ ФОРМЫ
Рисунок А.1 – Главное меню программы
Рисунок А.2 – Добавление дуги орграфа
Рисунок А.3 – Матрица смежности орграфа
Рисунок А.4 – Список вершин источников орграфа
Приложение Б
ЛИСТИНГ ПРОГРАММЫ
programOrGraph;
usesCrt;
typeTUk1=^TEl1;
TEl1=record
Next:TUk1;
Inf:integer;
end;
TUk=^TEl;
TEl=record
Left:TUk1;
Inf:integer;
Down:TUk;
end;
const
max=10;
var
Head:TUk;
c:char;
n,m:integer;
V:array[1..max] of byte;
{---------добавляемвершинувграф-------------}
procedure AddVer(n:integer);
var
p:TUk;
begin
if (Head=Nil) then
begin
New(Head);
Head^.Inf:=n;
Head^.Left:=Nil;
Head^.Down:=Nil;
end else begin
p:=Head;
while ((p^.Down<>Nil)and(p^.Inf<>n)) do p:=p^.Down;
if (p^.Inf=n) then WriteLn('Такая вершина уже есть!!!')
else begin
New(p^.Down);
p^.Down^.Inf:=n;
p^.Down^.Left:=Nil;
p^.Down^.Down:=Nil;
end;
end;
end;
{-------добавляем дугу в граф----------------------}
procedure AddDug(n,m:integer);
var
p,p1:TUk;
p2:TUk1;
begin
if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')
else begin
p:=Head;
while ((p<>Nil)and(p^.Inf<>n)) do p:=p^.Down;
if (p=Nil) then WriteLn('В графе отсутствует указанная вершина источник!!!')
else begin
p1:=Head;
while ((p1<>Nil)and(p1^.Inf<>m)) do p1:=p1^.Down;
if (p1=Nil) then WriteLn('В графе отсутствует указанная вершина сток!!!')
else begin
if (p^.Left=Nil) then
begin
New(p^.Left);
p^.Left^.Inf:=m;
p^.Left^.Next:=Nil;
end else begin
p2:=p^.Left;
while ((p2^.Next<>Nil)and(p2^.Inf<>m)) do p2:=p2^.Next;
if (p2^.Inf=m) then WriteLn('Указанная дуга уже существует!!!')
else begin
New(p2^.Next);
p2^.Next^.Inf:=m;
p2^.Next^.Next:=Nil;
WriteLn('Дуга добавлена!!!');
end;
end;
end;
end;
end
end;
{--удаляемсписокдуг--}
procedure DelList(p:TUk1);
var p1:TUk1;
begin
while (p<>Nil) do
begin
p1:=p;
p:=p^.Next;
Dispose(p1);
end;
end;
{---------удаляем вершину из графа---------}
procedure DelVer(n:integer);
var
p,p1:TUk;
p2,p3:TUk1;
begin
if (Head=Nil) then WriteLn('Вграфенетниоднойвершины!!!')
else begin
p:=Head;
if (p^.Inf=n) then
begin
Head:=Head^.Down;
DelList(p^.Left);
Dispose(p);
end else begin
while ((p^.Down^.Inf<>n)and(p^.Down<>Nil)) do p:=p^.Down;
if (p^.Down=Nil) then WriteLn('В графе нет указанной вершины!!!')
else begin
DelList(p^.Down^.Left);
p1:=p^.Down;
p^.Down:=p^.Down^.Down;
Dispose(p1);
end;
end;
p:=Head;
while (p<>Nil) do
begin
if (p^.Left^.Inf=n) then
begin
p2:=p^.Left;
p^.Left:=p^.Left^.Next;
Dispose(p2);
end else begin
p2:=p^.Left;
while ((p2^.Next<>Nil)and(p2^.Next^.Inf=n)) do p2:=p2^.Next;
if(p2^.Next^.Inf=n) then
begin
p3:=p2^.Next;
p2^.Next:=p2^.Next^.Next;
Dispose(p3);
end;
end;
p:=p^.Down;
end;
end;
end;
{------удаляемдугуграфа--------}
procedure DelDug(n,m:integer);
var
p,p1:TUk;
p2,p3:TUk1;
begin
if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')
else begin
p:=Head;
while ((p^.Inf<>n)and(p<>Nil)) do p:=p^.Down;
if (p=Nil) then WriteLn('В графе отсутствует указанная вершина источник')
else begin
p1:=Head;
while ((p1<>Nil)and(p1^.Inf<>m)) do p1:=p1^.Down;
if (p1=Nil) then WriteLn('В графе отсутствует указанная вершина сток!!!')
else begin
p2:=p^.Left;
if (p^.Left^.Inf=m) then
begin
p3:=p^.Left;
p^.Left:=p^.Left^.Next;
Dispose(p3);
end else begin
while ((p2^.Next^.Inf<>m)and(p2^.Next<>Nil)) do p2:=p2^.Next;
if (p2=Nil) then WriteLn('Указанного ребра нет в графе!!!')
else begin
p3:=p2^.Next;
p2^.Next:=p2^.Next^.Next;
Dispose(p3);
end;
end;
end;
end;
end;
end;
{---Вывод графа в виде матрицы смежности------}
procedure PrintGraph;
var
i,j,n:integer;
M:array [1..max,1..max] of byte;
p:TUk;
p2:TUk1;
begin
for i:=1 to max do
for j:=1 to max do M[i,j]:=0;
n:=0;
if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')
else begin
p:=Head;
while (p<>Nil) do
begin
inc(n);
p2:=p^.Left;
while (p2<>Nil) do
begin
M[p^.Inf,p2^.Inf]:=1;
p2:=p2^.Next;
end;
p:=p^.Down;
end;
end;
for i:=1 to n do
begin
for j:=1 to n do Write(M[i,j]:2);
WriteLn;
end;
end;
{-----находим все источники орграфа----}
procedure FindIstok;
var
f:boolean;
i,k:integer;
Is:array[1..max*max] of byte;
p,p1:TUk;
p2:TUk1;
begin
for i:=1 to max*max do Is[i]:=0;
if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')
else begin
k:=0;
p:=Head;
while (p<>Nil) do
begin
if (p^.Left<>Nil) then
begin
f:=true;
p1:=Head;
while (p1<>Nil) do
begin
p2:=p1^.Left;
while ((f)and(p2<>Nil)) do
begin
if p2^.Inf=p^.Inf then f:=false;
p2:=p2^.Next;
end;
p1:=p1^.Down;
end;
if (f=true) then
begin
inc(k);
Is[k]:=p^.Inf;
end;
end;
p:=p^.Down;
end;
end;
for i:=1 to k do Write(Is[i]:2);
end;
procedure Menu;
begin
WriteLn('1-Показатьматрицусмежностиграфа');
WriteLn('2-Добавитьвершинувграф');
WriteLn('3-Добавить дугу в граф');
WriteLn('4-Удалить вершину графа');
WriteLn('5-Удалить дугу графа');
WriteLn('6-Найти источники орграфа');
WriteLn('7-Выход');
end;
{--------основная программа--------}
begin
ClrScr;
repeat
clrscr;
Menu;
c:=ReadKey;
case c of
'1': begin
ClrScr; PrintGraph; ReadKey;
end;
'2': begin
ClrScr;
Write('Введите добавляемую вершину : ');
ReadLn(n); AddVer(n);
end;
'3': begin
ClrScr;
Write('Введите вершину источник дуги : ');
ReadLn(n);
Write('Введите вершину сток дуги : ');
ReadLn(m); AddDug(n,m);
end;
'4': begin
ClrScr;
Write('Введитеудаляемуювершину : ');
ReadLn(n); DelVer(n);
end;
'5': begin
ClrScr;
Write('Введите вершину источник удаляемой дуги : ');
ReadLn(n);
Write('Введите вершину сток удаляемой дуги : ');
ReadLn(m); DelDug(n,m);
end;
'6': begin
ClrScr; FindIstok; ReadKey;
end;
'7': begin
halt;
end;
end;
until ord(c)=27;
end.