Зображення графів на площині

При зображенні графів найчастіше використовується наступна система позначень: кожна вершина зображується у вигляді точки на площині, і якщо між вершинами існує ребро, то відповідні точки з'єднуються відрізком. У разі орієнтованого графа відрізки замінюють стрілками або явно показують напрямок ребра. Розрізняють планарні і непланарні графи. Планарний граф – це граф, який можна зобразити на малюнку без пересікання ребер (найпростіші – трикутник або пара пов’язаних вершин), інакше – непланарний. У випадку коли граф не містить циклів ( шляхів однократного обходу ребер і вершин з поверненням у вихідну точку), його прийнято називати «деревом». Важливі види дерев в теорії графів – бінарні дерева, де кожна вершина має одне вхідне ребро і рівно два вихідних, або є кінцевою - не має вихідних ребер.

Не слід плутати зображення графа із власне графом (абстрактної структурою), оскільки одному графу можна співставити не одне графічне представлення. Зображення покликане лише показати, які пари вершин з'єднані ребрами, а які - ні. Часто на практиці буває важко відповісти на питання, чи є два зображення моделями одного і того ж графа чи ні. Залежно від завдання, одні зображення можуть давати більш наочну картину, ніж інші.

2. Методи обходу графів.

Основу багатьох алгоритмів обробки мережевої інформації складають алгоритми обходу (ітерації) графів, в процесі якого проводиться пошук необхідної інформації або визначення яких-небудь характеристик мережі. Якщо граф має N вершин і М дуг, то говорять, що алгоритм обходу індукує нумерацію вершин і дуг графа, присвоює їм номери від 1 до N і від 1 до М відповідно у порядку обходу. Ітератори графа можуть бути як зовнішніми, так і внутрішніми, при цьому зовнішній ітератор, як завжди, видає вершини або дуги графа у порядку обходу, а внутрішній ітератор, обходячи граф, відвідує його вершини і дуги і виконує в кожній з них процедуру відвідин.

В процесі обходу звичайно використовується інформація про зв'язки між вершинами, тобто алгоритми обходу, переглядаючи граф, переходять завжди від деякої вершини до однієї з сусідніми з нею вершин. Це необов’язково означає, що порядок обходу вершин також такий, що услід за однією вершиною неодмінно як наступна вершина слідує одна з сусідніх з нею. Більш того, в більшості випадків такий обхід побудувати просто неможливо. Обходи, описані вище, називаються гамільтоновими шляхам. Для існування гамільтонового шляху граф повинен задовольняти певні умови. Алгоритми обходу просто використовують зв'язки між вершинами для переходу від одних вершин до інших. Якщо дуги, що зв'язують вершини графа - напрямлені (з технічної точки зору це означає, що якщо від вершини А можна перейти до вершини В, то це не означає, що від вершини В можна обов'язково безпосередньо перейти до вершини А), то навіть для зв'язного графа не завжди вдається, вибравши деяку вершину як початкову, обійти його весь, проходячи тільки по напрямах дуг. В цьому випадку часто поступають таким чином. Вибирають деяку вершину графа. Обходять всі його вершини, досяжні з вибраної. Якщо в графі залишилися ще не пройдені вершини, то вибирають одну з таких вершин і знову обходять всі вершини, досяжні з вибраної (зрозуміло, якщо в процесі обходу попадеться одна з вже пройдених вершин, то не тільки її, але і всі, досяжні з неї вершини повторно розглядати не треба). Процес продовжується до того часу, поки в графі не залишиться жодної не пройденої вершини. Якщо дуги в графі не напрямлені, то описаний алгоритм приведе до того, що кожного разу після вибору початкової вершини буде пройдена одна компонента зв'язності графа. Якщо граф — зв’язний, то яку б вершину не вибрати як початкову, всі інші будуть з неї досяжні, так що ніколи не потрібно після обходу всієї компоненти зв'язності проводити ще один вибір вершини.

Разом з обходами, при яких відвідуються всі вершини графа. Можна також розглядати обходи, призначені для проходження всіх дуг (ребер) графа. Такі обходи індукують деяку нумерацію на безлічі ребер подібно до того, як обходи вершин індукують нумерацію на безлічі вершин. Для обходів дуг і вершин графа можна використовувати одні і ті ж алгоритми. Дійсно, практично всі алгоритми обходу графа хоч би по одному разу обов'язково досліджують як вершини, так і дуги графа. Для того, щоб зрозуміти, чи не знаходиться на кінці деякої дуги ще не пройдена вершина, потрібно досліджувати цю дугу. І навпаки, якщо проходяться всі дуги, це означає, що і всі вершини будуть пройдені, оскільки кожна вершина знаходиться на кінці деякої дуги. Ми розглядатимемо алгоритми обходу, що використовують представлення графа під назвою L-графа, в якому для кожної вершини є список дуг, що виходять з цієї вершини. Для алгоритмів обходу таке уявлення найбільш природне, оскільки саме в цьому випадку простіше всього переходити від вершини графа до сусідніх з нею вершин.

Знаючи номер деякої вершини, ми легко зможемо знайти всі суміжні з нею вершини, досліджуючи дуги, що виходять з цієї вершини. У описі алгоритмів ми вважатимемо, що послідовно нумеруються вершини графа, але фактично тими ж самими алгоритмами нумеруються і дуги графа. Уявлення у вигляді Z- графа описує орієнтований граф, в якому всі дуги мають напрям. Таким чином, якщо деяка дуга зв'язує вершину А з вершиною В, то з цього ще не виходить, що з вершини В можна пройти у вершину А. Може трапитися таке, що навіть для зв'язного графа не обов'язково вдасться пройти його, почавши обхід з довільно вибраної вершини. Якщо граф — неорієнтований, то його представлення разом з дугою, що веде з вершини А у вершину В, обов'язково є також і дуга, що веде з В в А. Це означає, що алгоритми проходитимуть кожне ребро графа двічі: один раз в напрямі від вершини A до B , а інший раз — у протилежному напрямі.

Як і у випадку обходу дерев, для графів існують два основні класи пошуку: пошук вглиб і пошук вшир.

Пошук вглиб

Пошук в глибину (DFS , depth - first search) представляє собою класичний гнучкий алгоритм, який використовується для вирішення задачі зв’язності і багато інших задач обробки графів. Можливі дві реалізації цього базового алгоритму: одна у вигляді рекурсивної процедури, друга – з використанням явно заданого стеку. Ми будемо використовувати стек магазинного типу. Використання правила LIFO (Last In First Out — останній прийшов, перший вийшов), який характеризує роботу стеку. Стратегія пошуку в глибину така: йти «в глибину», поки це можливо (існують не пройдені вихідні ребра), і повертатися і шукати інший шлях, коли таких ребер немає. Так робиться, поки не виявлені всі вершини, досяжні з вихідної.

Нехай G =( V , Е) — неорієнтований зв'язний граф, через Г( v ) позначимо список вершин, суміжних з вершиною v. У процесі пошуку вглиб вершинам графа G присвоюються номери ( dfnum ).

При обході графа G пошуком вглиб починаємо з довільної вершини v ₀. Присвоюємо dfnum ( v ₀ ): =1 і вибираємо довільну вершину w , суміжну з v ₀^: w  Г( v ₀ ). Вершина w отримує (із v ₀) номер dfnum ( w ):=2. Після цього переходимо у вершину w. Нехай у результаті виконання декількох кроків цього процесу досягнуто вершину х і нехай к – останній присвоєний номер dfnum . Далі діємо в залежності від ситуації. Таких ситуацій є декілька:

1. Існує вершина у, суміжна з вершиною х (тобто у  Г(х)) така, що у ще не має dfnum . Тоді вершина у отримує із вершини х номер dfnum ( y ):= k +1 і переходимо у вершину у.

2. Усі вершини, суміжні з вершиною х, мають dfnum . У такому випадку повертаємось до вершини, із якої вершина х отримала dfnum . Процес закінчиться коли відбудеться повернення у вершину v ₀(початкову). У разі обходу вершин неорієнтованого графа методом пошуку вглиб відбувається побудова глибинного дерева. Це кореневе дерево з коренем у початковій вершині v ₀. Множина Е всіх ребер графа G розбивається на дві підмножини:

1)множина Т ребер глибинного дерева;

2)множина В обернених ребер.

Якщо під час обходу графа досягнута вершина х, яка має інцидентне ребро {х,у}, то у випадку, коли вершина у ще не має dfnum і отримує його з вершини х, то {х,у} – ребро дерева; якщо ж вершина у уже має dfnum , то {х,у} – обернене ребро.

Псевдокод

 - початкова вершина;

Відвідати початкову вершину і помістити її в стек .

WHILE Стек  не є порожнім DO

BEGIN

Нехай potochna – вершин, яка знаходиться на вершині стеку ;

Поміщаємо її в чергу;

Булівській змінній b присвоїти false;

FOR DO

BEGIN

IF Із вершини potochna у вершину  існує шлях і вершина  не відвідана

THEN

BEGIN Відвідати вершину;

          Помістити її в стек ;

          Змінній b присвоїти true;

BREAK; END; END;

IF b

THEN Видалити вершину  зі стеку ;

END.

Пошук вглиб намагаються кожного разу після проходження деякої вершини А вибрати як наступну таку вершину В, в яку з вершини А веде дуга. Таким чином, алгоритми цього класу намагаються завжди рухатися углиб графа, знаходячи все ще не пройдені раніше вершини. Якщо таких не пройдених вершин немає, то алгоритм повертається до попередньої, раніше пройденої вершини, і намагається знайти чергову дугу, що веде з неї в яку-небудь іншу ще не пройдену вершину. Якщо і таких вершин немає, то знову відбувається відкіт назад, і так до тих пір, поки або всі вершини не будуть пройдені, або алгоритм повернеться назад у вершину, вибрану як початкову.

Пошук вшир

У процесі пошуку вшир вершини графа проглядають в іншій послідовності, ніж у методі пошуку вглиб, і їм надають BFS- номери (від англ..Breadth First Search). BFS - номер вершини x позначають BFS(x). Назва пояснюється тим, що під час пошуку ми йдемо вшир, а не вглиб: спочатку проглядають всі сусідні вершини, після цього сусіди сусідів і так далі.

Для реалізації алгоритму використовують структуру даних для збереження множин, яку називають чергою. Із черги можна вилучити той елемент, який перебував у ній довше за всіх: працює принцип « першим прийшов – першим вийшов». Елемент включають у хвіст черги, а виключають із голови черги. Пошук вшир, якщо казати загалом, відрізняється від пошуку вглиб заміною стека на чергу. Після такої модифікації що раніше відвідують вершину(включають до черги), то раніше її використовують(і виключають з черги). Використання вершини здійснюють за допомогою перегляду одразу всіх ще не відвіданих сусідів цієї вершини. Вся процедура подана нижче.

Алгоритм пошуку вшир.

Крок 1. Почати з довільної вершини v_s. Покласти BFS(v_s)=1. Включити вершину v_s у чергу.

Крок 2. Розглянути вершину, яка знаходиться на початку черги: нехай це буде вершина x . Якщо для всіх вершин, суміжних з вершиною x, вже визначені BFS-номери, то перейти до кроку 4, інакше до кроку 3.

Крок 3. Нехай {x , y} – ребро, в якому номер BFS(y) не визначений. Позначимо це ребро потовщеною суцільною лінією, визначити BFS(y) як черговий BFS-номер, включити вершину y до черги і перейти до кроку 2.

Крок 4. Виключити вершину x з черги. Якщо черга порожня, то зупинитись, інакше – перейти до кроку 2.

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

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

Алгоритми обходу графів (так само, як і дерев, і списків) можуть бути реалізовані як зовнішніми, так і внутрішніми ітераторами. Зовнішній ітератор у момент створення бере представлення графа як аргумент, а потім здійснює послідовну видачу номерів вершин графа, використовуючи для обходу локальні об'єкти, такі, як стек або черга. Внутрішній ітератор найчастіше реалізується у вигляді рекурсивної функції, яка, проходячи по черзі вершини графа, виконує для кожної з них деяку дію, задану як аргумент ітератора.

Приклад орієнтованого графа

Цей граф має 9 вершин і 12 дуг. Він складається з двох компонент зв'язності, так що не вдасться обійти його весь, вибравши деяку вершину як початкову і проходячи тільки по напрямах дуг. Проте якщо спочатку вибрати як початкову вершину вершину 1, то вся решта вершин однієї компоненти зв’язності з неї будуть досяжні, так що принаймні ця компонента зв'язності буде пройдена до того, як потрібно буде знов вибирати початкову вершину. Тією ж властивістю володіє і вся решта вершин графа, окрім вершини 7. Якщо вибрати її як початкову вершину для обходу, то буде пройдена тільки вона сама, а потім потрібно буде знов вибирати деяку вершину як початкової для обходу інших.

Якщо за алгоритм обходу взяти алгоритм обходу в глибину, причому домовитися, що зі всіх можливих альтернатив він завжди вибирає прохід до вершини з найменшим номером, то вийде наступний порядок обходу вершин графа: 0;   1; 4; 6; 3; 7; 2; 8; 5

Порядок обходу завширшки в даному випадку відрізняється від порядку обходу в глибину трохи: 0; 1; 4; би; 7; 3; 2; 8; 5

Але це, звичайно, виходить просто тому, що граф, вибраний нами для прикладу, дуже невеликий. Звичайно у разі великих графів порядки обходу відрізняються вельми істотно.

Студент повинен

знати :

v Означення теорії графів.

v Означення графа.

v Види графів.

v Зображення графів на площині.

v Методи обходу графів.

вміти :

v Зображати графи.

v Здійснювати обхід графа різними методами.

Питання для самоконтролю

1. Дайте означення теорії графів.

2. Дайте означення графа.

3. Перелічіть види графів. Дайте їх означення.

4. Назвіть методи зображення графів на площині.

5. Назвіть методи обходу графів. Назвіть їх алгоритм.

 Література

[11] c. 88-100, [12] c. 348-362.

1.12. Порядок виведення графічної інформації за допомогою засобів мови С++

Питання для опрацювання

1. Порядок переходу у графічний режим виводу інформації.

2. Функції для побудов геометричних фігур.

Методичні рекомендації

Під час освоєння даної теми студенти мають в ивчити порядок виконання графічних побудов за допомогою засобів С++, навчитись використовувати графічні побудови у власних програмах .

1. Порядок переходу у графічний режим виводу інформації.

Для забезпечення можливості виводу інформації у графічному форматі у мові Сі була розроблена спеціальна бібліотека graphics . h, яка дозволяє проводити найпростіші геометричні побудови (коло, квадрат, лінію тощо). Але вона працює лише в середовищі MS-DOS, оскільки в середовищі Windows графічну інформацію можна виводити безпосередньо через вікна. Крім того, середовище Microsoft Visual Studio передбачає виведення в консольному режимі, який в принципі не передбачає використання графіки. Тому тут така бібліотека відсутня взагалі (так само як і функції для роботи з екраном, зокрема clrscr ( ) бібліотеки stdlib . h).

2. Функції для побудов геометричних фігур.

Виведення графічної інформації можна проводити безпосередньо у віконному режимі з використанням функцій Windows.API (application programming interfaces) , тобто стандартних бібліотек для взаємодії програм користувача із ресурсами ОС Windows. Але зважаючи на різноманітність і велику кількість опцій у таких функціях вибрати прості і доступні засоби виведення графів на екран є досить складно. Тому для нашого прикладу більш доцільно використовувати засоби псевдографіки, тобто імітувати графічні побудови виводом звичайного тексту. Зокрема коло у вершині можна не відображати, достатньо вивести лише номер вершини. Крім того, ребра між вершинами можна зображати у вигляді вертикальних і горизонтальних ліній. В такому випадку виникає потреба у переміщенні курсору у потрібну нам позицію. Цю проблему також можна вирішити за допомогою функцій Windows.API. Для цього складемо функцію переміщення курсора у потрібну нам позицію GotoXY ( ), яка буде базуватись на використанні стандартної функції SetConsoleCursorPosition бібліотеки Windows.API:

void gotoxy(int k_x, int k_y)

{

COORD coord;

coord.X = k_x;

coord.Y = k_y;

 SetConsoleCursorPosition(GetStdHandle( STD_OUTPUT_HANDLE ), coord);

}

Як видно з фрагмента, ця функція переводить курсор на позицію з координатами k_x та k_y. Але для коректної її роботи слід підключити бібліотеку windows.h.

Крім того, для наочного і правильного відображення дерева потрібно його вершини розміщувати симметрично одна відносно одної. Тому у структуру, що описує вершини дерева варто ввести додаткові змінні, що будуть визначати його координати. Як відомо, у текстовому режимі консольний екран виводу інформації містить 80х25 символів, тому для початкової вершини можна задати координати x=40 та y=2. Далі для кожного лівого сина рухатись на 3 позиції вниз і вліво, а для кожного правого – на 3 позиції вниз і вправо. Але тут виникає проблема пошуку батьківської вершини для певного вузла дерева, яка вирішується шляхом використання вкладених циклів:

vershyna[0].k_x=40;

vershyna[0].k_y=2;

 int i, j;

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

 {

for (j=0; j<10; j++)

{

if (vershyna[j].left==&vershyna[i])

{

vershyna[i].k_x=vershyna[j].k_x-3;

vershyna[i].k_y=vershyna[j].k_y+3 ; //зміщуємось на 3 позиції вліво і вниз відносно батька

virt_line(vershyna[j].k_x,vershyna[j].k_y,vershyna[i].k_x,vershyna[i].k_y);

} //будуємо віртуальну лінію у між вершинами

 // робимо аналогічні дії, якщо вершина є правим сином

}

 }

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

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

 {

gotoxy(vershyna[i].k_x,vershyna[i].k_y);

puts(itoa(vershyna[i].nomer,str_tmp,10));

 }

Також в кінці процедури виводу для того, щоб наступна інформація, яка може виводитись не пошкодила сам граф, потрібно перейти на кінець екрану.

 gotoxy(70, 24);

 puts(" ");

   Як видно з фрагментів, під час виводу інформації на екран використовується функція puts ( ) бібліотеки stdio . h, а не функція cout, яка не пристосована до виводу символів на екран у потрібній нам точці. Тому для перетворення числової інформації про номер вершини у символьний рядок використовується стандартна функція itoa ( ) бібліотеки stdlib . h .

   Розглянемо детальніше процес побудови лінії у вигляді прямих. Схема такої лінії зображена на наступному малюнку:

Як видно з малюнку, якщо x 2> x 1, то спочатку потрібно провести дві горизонтальні лінії від позиції x 1 +1 до позиції x 2  (у вигляді символа «-»)

x_tmp=x1+1;

while (x_tmp<=x2)

{

gotoxy(x_tmp,y1);

puts("-");

x_tmp++;

}

 }

 Після цього проводяться дві вертикальні лінії від координати y 1+1 до y 2-1:

y_tmp=y1+1;

 while (y_tmp<y2)

 {

gotoxy(x2,y_tmp);

puts("|");

y_tmp++;

 }

Очевидно, що якщо x 2> x 1 (лівий син), то будуючи горизонтальну лінію, координату х ми зменшуємо, а вертикальна лінія будується аналогічно.

Таким чином, сформоване нами дерево буде відображено так:

Студент повинен

знати :

v Порядок переходу у графічний режим виводу інформації.

v Функції для побудов геометричних фігур.

вміти :

1. Здійснювати перехід у графічний режим виводу інформації.

2. Використовувати функції для побудов геометричних фігур у власних програмах.

Питання для самоконтролю

1. Назвіть орядок переходу у графічний режим виводу інформації.

2. Перелічіть функції для побудов геометричних фігур.

 Література

[1] c. 105-111

Тема 2. Середовище візуального програмування С++ Builder

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: