Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Пример программы с использованием матрицы смежности




Читайте также:
  1. C2 Покажите на трех примерах наличие многопартийной политической системы в современной России.
  2. C2 Раскройте на трех примерах научный вывод о том, что социальные условия влияют на характер и форму удовлетворения первичных (биологических, витальных) потребностей.
  3. I. ПОНЯТИЕ МАТРИЦЫ.
  4. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  5. II. Примеры проективных методик
  6. III. Примеры решения задач.
  7. III. Примеры решения задач.
  8. III. Примеры решения задач.
  9. IV. Примеры решения задач.
  10. IV. Примеры решения задач.

 

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

· новый граф содержал все пути, соединяющие начало с концом и имеющие длины, не превышающие макимально допустимую длину;

· исключение любой вершины или дуги нового графа вело к нарушению первого условия.

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

1. Ввод данных. Задание для каждого I-го узла

L1[I]:=1000 и L2[I]:= 1000 .

В массивы L1 и L2 будут занесены впоследствии минимальные длины от начала и до конца.

2. Занесение номера начального узла B в стек.

3. L1[B]:=0.

4. Если стек пуст, переход к 11.

5. Выбор узла i из вершины стека.

6. Если L1[I]=L, то исключить вершину стека и перейти к 4. Здесь L - максимально допустимая длина.

7. M:= L1[I] + 1 – текущая минимальная длина для последователей узла I.

8. Выбор очередного последователя (с номером J) узла I.

9. Если M < L1[J], то

· L1[J]:=M;

· занесение узла J в стек.

10. Если рассмотрены не все последователи узла I, переход к 8; иначе переход к 4.

11. Повторение шагов, аналогичных шагам 2-10, но в направлении от конца к началу с использованием массива L2.

12. В цикле по номерам узлов I простановка признаков запрета тем узлам, для которых

L1[I] + L2[I] > L .

13. Исключение из графа запрещенных узлов вместе с инцидентными им дугами.

14. Исключение из графа всех дуг из I-го узла в J-й по условию

L1[I] + L2[J] +1 >L .

15. Конец.

Для хранения узлов можно было использовать очередь, а не стек, что обеспечивает расстановку длин по возрастанию. В целях удобства прохода по графу в прямом и обратном направлениях выбрана форма представления графа на основе матрицы смежности. Приведем текст программы на ПАСКАЛЕ.

Program MinGraph;

{ Выделение минимального графа по началу, концу и длине }

{ Используется стек, расстановка пометок - в глубину }

Uses Crt;

Type



prizn=0..1;

uzel=record

Zapr: prizn; { 1-вершина запрещена, 0-нет }

L: array[1..2] of integer { длины вперед и назад }

end;

Var

M, N, I, J, K, Nb, Nk, Top, Len: integer;

Matr: array[1..20,1..20] of prizn; { матрица смежности }

Stek: array[1..20] of integer;

{ стек вершин, для сыновей которых расставляем длины }

Ver: array[1..20] of uzel; { индекс-номер вершины }

Procedure Rasstan(Napr: integer);

{ расстановка длин в массивах L1 или L2 }

{ Napr=1 - расстановка от начальной вершины к конечной }

{ Napr=2 - расстановка от конечной вершины к начальной }

Begin

Top:=1; { вершина стека }

if Napr=1 then Stek[1]:=Nb { Nb-начальная вершина }

else Stek[1]:=Nk; { Nk-конечная вершина }

Ver[Stek[1]].L[Napr]:=0;

While Top>0 do

begin

I:=Stek[Top];

Top:=Top-1;

if Ver[i].L[napr]<Len then

{ не достигли максимальной длины }

For J:=1 to N do

begin

if Napr=1 then K:=Matr[I,J]

else K:=Matr[J,I];

if K=1 then { есть связь }

begin

M:=Ver[i].L[Napr]+1;

if M<Ver[j].L[Napr] then

{ вершина впервые или на меньшем расстоянии }

begin

Ver[J].L[Napr]:=M;

Top:=Top+1;

Stek[Top]:=J { занесение в стек }



end

end

end

end

End;

Procedure Pech; { распечатка матрицы смежности }

Begin

For I:=1 to N do

begin

WriteLn;

For J:=1 to N do

Write(Matr[I, J],' ')

end

End;

Begin { основная программа }

ClrScr; { очистка экрана }

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

ReadLn(n);

For I:=1 to N do

For j:=1 to n do

Matr[I,J]:=0;

For I:=1 to N do

begin

WriteLn('Занимаемся вершиной ', I, ':');

K:=1000;

While K>0 do

begin

Write('Введите номер очередного последователя вершины ', I,

' (-1 – признак конца) ');

ReadLn(K); { K<0-признак конца списка последователей }

if (K>0) and (K<=N) then

begin

Matr[I,K]:=1;

Ver[I].L[1]:=1000; { для будущего поиска минимума }

Ver[I].L[2]:=1000;

Ver[I].Zapr:=0 { запрета нет }

end

end

end;

Write('Введите номер начальной вершины ');

ReadLn(Nb);

Write('Введите номер конечной вершины ');

ReadLn(Nk);

Write('Введите максимальную длину ');

Readln(Len);

WriteLn;

WriteLn('Старая матрица смежности:');

Pech;

ReadLn; { пауза }

Rasstan(1); { расстановка длин вперед }

if Ver[Nk].L[1]>Len then

{ вершина Nk не встречалась или дальше, чем на Len звеньев }

begin

WriteLn(' Граф пуст !!!');

Exit

end;

Rasstan(2); { расстановка длин назад }

For I:=1 to N do { расстановка запретов на вершины }

if Ver[i].L[1]+Ver[i].L[2]>Len then Ver[i].Zapr:=1;

For I:=1 to N do { исправление матрицы смежности }

if Ver[i].Zapr=1 then { i-я вершина запрещена }

For J:=1 to N do

begin

Matr[I, J]:=0;

Matr[J, I]:=0

end;

For I:=1 to N do { анализ дуг матрицы смежности }

For J:=1 to N do

if Matr[I, J]=1 then



if Ver[i].L[1]+1+Ver[j].L[2]>Len then

Matr[I, J]:=0;

WriteLn;

WriteLn('Новая матрица смежности:');

Pech;

ReadLn

End.

 


Дата добавления: 2015-01-29; просмотров: 10; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.028 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты