Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Тема заняття: Пошук в ширину на графах. Реалізація через множинний тип даних

Скачати 39.31 Kb.

Тема заняття: Пошук в ширину на графах. Реалізація через множинний тип даних




Скачати 39.31 Kb.
Дата конвертації02.05.2017
Розмір39.31 Kb.

ВІППО Школа олімпійського резерву 29.02.2008

Тема заняття: Пошук в ширину на графах. Реалізація через множинний тип даних.

Нам знадобиться список List вершин графа і безліч Old вже розглянутих (“відвіданих”) вершин. Алгоритм “починає свою роботу” з деякої довільної вершини.

Заняття - це форма організації навчального процесу. Заняття, як правило, триває одну академічну годину. Проте, вчителі й викладачі часто проводять по два заняття (пару).

Про́даж - це оплатна передача майна однією особою у власність іншій особі.

Алгоритм Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.

В нашому прикладі - це вершина 1. На початковому етапі (див.

Етап - багатозначне українське слово іншомовного походження

мал.а)) створюється список вершин і множина вже “відвіданих вершин”. В нашому випадку множина містить вершину 1 і ознака кінця, який можна розглядати як фіктивну вершину. Множина містить єдину вершину 1. Покажчик р встановлений (“дивиться”) на початкову вершину списку, а покажчик q - на фіктивну вершину.

На першому етапі (див. мал. б.)) до списку приєднуються вершини, суміжні вершині 1. Ці ж вершини додаються в множину Old.

На другому етапі (див. мал. в) покажчик р пересуваємо на один крок - тепер він “дивиться” на вершину 4, яка стає поточною.

Розглянемо вершини, суміжні вершині 4. Це вершини 1, 5, 6. Проте вершини 1 і 5 - “старі”, вони вже містяться в Old. Тому до списку List додається тільки вершина 6. Ця ж вершина додається в множину Old.

На третьому етапі (див. мал. г)) покажчик р пересувається на один крок - тепер поточною є вершина 5. Суміжні до неї - вершини 1, 3, 4, 2. Серед них нові (ще не розглянуті) лише вершини 3 і 2.

Стає (словен. Selnik) - поселення в общині Іг, Осреднєсловенський регіон, Словенія. Висота над рівнем моря: 307.5 м.

1 (оди́н) - найменше натуральне число, ціле число між 0 і 2.

Нов (фр. Noves) - муніципалітет у Франції, у регіоні Прованс-Альпи-Лазурний берег, департамент Буш-дю-Рон. Населення - 5238 осіб (2011).

Саме вони і додаються в List і поміщаються в Old.

На наступному етапі (див. мал. 70 д)) покажчик р переміщається на один крок - тепер він “дивиться” на вершину 6. Суміжних до неї нових вершин немає. Покажчик пересувається на один крок. І т.д., покажчик р пересувається управо до тих пір, поки не “дивитиметься” на фіктивну вершину - ознака кінця. На цьому процес завершується.

В результаті роботи описаного алгоритму в списку List в точності один раз міститься кожна вершина графа, яка належить тій же компоненті зв'язності, що і початкова вершина.

Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.

Всі ці вершини (і лише вони) містяться і в множині Old.

У випадку, якщо граф не є зв'язним, для перебору всіх вершин графа слід знайти вершину, не належить Old, і застосувати описаний вище алгоритм, рахуючи цю вершину початкової. І т.д., поки не будуть перебрані всі вершини графа.

program poisk_sh;

const n=6;

a:array[1..n,1..n] of integer=

((0,0,0,1,1,0),

(0,0,0,0,1,0),

(0,0,0,0,1,0),

(1,0,0,0,0,1),

(1,1,1,0,0,0),

(0,0,0,1,0,0));

var


m1,m2,m3:set of 1..n;

p,i:integer;

begin

p:=1;


m1:=[p];

m2:=[];


m3:=m1;

while m3<>[] do begin

for i:=1 to n do

if a[p,i]=1 then m1:=m1 [i];

m2:=m2 [p];

m3:=m1-m2;

for i:=1 to n do

if i in m3 then p:=i;

end;

for i:=1 to n do



if i in m1 then write(i,' ');

writeln;


end.


Тема заняття: Пошук в ширину на графах. Реалізація через множинний тип даних.

Нам знадобиться список List вершин графа і безліч Old вже розглянутих (“відвіданих”) вершин. Алгоритм “починає свою роботу” з деякої довільної вершини. В нашому прикладі - це вершина 1. На початковому етапі (див. мал.а)) створюється список вершин і множина вже “відвіданих вершин”. В нашому випадку множина містить вершину 1 і ознака кінця, який можна розглядати як фіктивну вершину. Множина містить єдину вершину 1. Покажчик р встановлений (“дивиться”) на початкову вершину списку, а покажчик q - на фіктивну вершину.

На першому етапі (див. мал. б.)) до списку приєднуються вершини, суміжні вершині 1. Ці ж вершини додаються в множину Old.

На другому етапі (див. мал. в) покажчик р пересуваємо на один крок - тепер він “дивиться” на вершину 4, яка стає поточною.

Розглянемо вершини, суміжні вершині 4. Це вершини 1, 5, 6. Проте вершини 1 і 5 - “старі”, вони вже містяться в Old. Тому до списку List додається тільки вершина 6. Ця ж вершина додається в множину Old.

На третьому етапі (див. мал. г)) покажчик р пересувається на один крок - тепер поточною є вершина 5. Суміжні до неї - вершини 1, 3, 4, 2. Серед них нові (ще не розглянуті) лише вершини 3 і 2. Саме вони і додаються в List і поміщаються в Old.

На наступному етапі (див. мал. 70 д)) покажчик р переміщається на один крок - тепер він “дивиться” на вершину 6. Суміжних до неї нових вершин немає. Покажчик пересувається на один крок. І т.д., покажчик р пересувається управо до тих пір, поки не “дивитиметься” на фіктивну вершину - ознака кінця. На цьому процес завершується.

В результаті роботи описаного алгоритму в списку List в точності один раз міститься кожна вершина графа, яка належить тій же компоненті зв'язності, що і початкова вершина. Всі ці вершини (і лише вони) містяться і в множині Old.

У випадку, якщо граф не є зв'язним, для перебору всіх вершин графа слід знайти вершину, не належить Old, і застосувати описаний вище алгоритм, рахуючи цю вершину початкової. І т.д., поки не будуть перебрані всі вершини графа.


program poisk_sh;

const n=6;

a:array[1..n,1..n] of integer=

((0,0,0,1,1,0),

(0,0,0,0,1,0),

(0,0,0,0,1,0),

(1,0,0,0,0,1),

(1,1,1,0,0,0),

(0,0,0,1,0,0));

var


m1,m2,m3:set of 1..n;

p,i:integer;

begin

p:=1;


m1:=[p];

m2:=[];


m3:=m1;

while m3<>[] do begin

for i:=1 to n do

if a[p,i]=1 then m1:=m1 [i];

m2:=m2 [p];

m3:=m1-m2;

for i:=1 to n do

if i in m3 then p:=i;

end;

for i:=1 to n do



if i in m1 then write(i,' ');

writeln;


end.


Скачати 39.31 Kb.