Перевірка орієнтованого графа на наявність циклів

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

Отже, розглянемо деякий орієнтований граф . Для того, щоб перевірити даний граф на наявність циклів, виконуємо глибинний обхід всіх його вершин. В результаті, отримаємо дерево обходу в глибину. Якщо в побудованому дереві зустрінеться хоча б одне зворотне ребро, то ясно, що орієнтований граф має цикл. Справедливе і обернене твердження, тобто, якщо в орієнтованому графі є цикл, тоді зворотне ребро обов'язково зустрінеться при його обході методом пошуку в глибину. Щоб довести це, припустимо, що орієнтований граф  має цикл.

Перевірка орієнтованого графа на наявність циклів

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

Читати повністю

Відображення та редагування даних булевого типу використовуючи компонент TDBCheckBox

Компонент TDBCheckBox — пов'язаний з даними аналог звичайного індикатора TCheckBox. Він дозволяє відображати і редагувати дані поля булевого, а також символьного та числового типу. Якщо при виведенні даних булеве поле приймає значення True, то пов'язаний з ним індикатор являється включеним. Якщо ж в процесі редагування користувач включить або вимкне індикатор, то відповідно значення True або False запишеться у відповідному полі таблиці бази даних. Це один із способів забезпечити користувачеві безпомилкове введення значень в поле таблиці бази даних.

Зв'язок компонента типу TDBCheckBox з полем набору даних здійснюється за допомогою його властивостей DataSource типу TDataSource і DataField типу TDataField. Перше з властивостей вказує на ім'я компонента джерела даних, через який здійснюється зв'язок з набором даних. І властивість DataField для пов'язаного набору даних вказує ім'я поля.

Якщо ж delphi-компонент TDBCheckBox пов'язаний з полем символьного або числового типу, то у властивості ValueChecked типу String даного компонента заноситься рядок, який перераховує значення поля, при яких індикатор включається, а у властивості ValueUnchecked (також типу String) перераховуються значення, при яких індикатор вимикається (окремі значення розділяються крапкою з комою). При значеннях, що не перераховані ні у ValueChecked, ні у ValueUnchecked, індикатор TDBCheckBox переходить у невизначений стан, відображаючи сірий прапорець (навіть у тому випадку коли властивість AllowGrayed (відповідає за заборону переводу індикатора в невизначений стан) приймає значення False).

Читати повністю

Відображення та редагування багаторядкових текстових даних використовуючи компонент TDBMemo

Delphi-компонент TDBMemo являє собою багаторядковий текстовий редактор, який, зазвичай, зв'язується з текстовими полями великих розмірів або з BLOB-полями, що спеціалізуються на збереженні текстових даних. Такі поля іноді називають MEMO-полями і вони реалізовані в таблицях формату dBase і Paradox. Нагадаємо, що при проектуванні таблиці за допомогою утиліти Database Desktop поле такого типу позначається символом «M».

Зауваження: у компоненті можна використовувати буфер обміну за допомогою стандартних засобів операційної системи або успадкованими від предка TCustomMemo методами CopyToClipBoard, CutToClipBoard і PasteFromClipBoard.

Як уже зазначалося, при розгляді основних характеристик візуальних компонентів призначених для роботи з базами даних, серед властивостей компонентів такого типу, і зокрема компонента TDBMemo, виділяють дві, що забезпечують зв'язок з даними. Це властивість DataSource типу TDataSource (вказує на джерело даних, з яким пов'язаний компонент TDBMemo) і властивість DataField типу TDataField (вказує на поле набору даних, з яким пов'язаний компонент TDBMemo). Скориставшись даними властивостями пов'яжемо компонент TDBMemo з полем description таблиці cars («Автомобілі») бази даних autobazar («Автобазар»). Для цього, відкриємо delphi-проект, який ми створювали при розгляді однорядкового текстового редактора TDBEdit та доповнимо головну форму одним компонентом DBMemo1 типу TDBMemo та ще одним компонентом типу TLabel (містяться на закладках Data Controls та Standard палітри компонентів Delphi відповідно).

Читати повністю

Виведення записів набору даних в табличному вигляді використовуючи компонент TDBGrid

Для виведення записів набору даних в табличному вигляді зручно використовувати сітку, представлену delphi-компонентом типу TDBGrid. Зовнішній вигляд сітки відповідає внутрішній структурі таблиці бази даних і набору даних. При цьому, рядкам сітки відповідають записи, а стовпцям — поля.

Об'єкт TDBGrid зв'язується з джерелом даних через свою властивість DataSource, яке, в свою чергу, посилається на набір даних. Тобто, якщо на форму, де вже відповідним чином налаштовані невізуальні компоненти, наприклад, Table1 та DataSource1 помістити таблицю DBGrid1, і у властивості DataSource даної таблиці вказати значення DataSource1, то ми відразу ж побачимо вміст таблиці бази даних, що пов'язується з набором даних Table1. В нашому випадку це таблиця cars («Автомобілі») бази даних dbautobazar («Автобазар»).

tdbgrid_komponent1

Вивід вмісту таблиці cars в компоненті DBGrid1

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

Читати повністю

Побудова дерева обходу в глибину для орієнтованого графа в середовищі програмування delphi

Розглядуваний в даному параграфі delphi-проект реалізує процес побудови дерева обходу в глибину для орієнтованого графа. Головна форма проекту, як і у випадку з глибинним обходом неорієнтованого графа, ділиться на дві частини і складається з панелі інструментів та графічного редактора.

Головне вікно проекту "Побудова дерева обходу в глибину для орієнтованого графа"

  1. Панель інструментів (компонент типу TPanel): містить чотири кнопки: «Додати вершину» (типу TSpeedButton), «Додати ребро» (типу TSpeedButton), «Видалити граф» (типу TButton) та «Побудувати дерево обходу в гибину» (типу TButton). Відмітимо, що три кнопки з даного списук призначенні для побудови та видалення орієнтованого графа і четверта — реалізує його глибинний обхід.
  2. Графічний редактор (компонент типу TImage): призначений для побудови і візуалізації орієнтованого графа, а також візуалізації відповідного йому дерева обходу в глибину. Для того, щоб намалювати вершини графа потрібно, на першому кроці, активізувати кнопку панелі задач «Додати вершину». На наступному кроці, з допомогою лівої кнопки мишки, розставити їх у відповідній області форми. Після того, як вершини створено потрібно пов'язати їх відповідним орієнтованим ребром. Орієнтоване ребро в даній програмі створюється наступним чином: активізувавши кнопоку «Додати ребро» лівою кнопокою миші поєднюємо необхідні вершини. Для видалення графа чи побудови його дерева обходу в глибину необхідно скористатися однойменними кнопками що містяться на панелі задач.

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

Читати повністю

Обхід орієнтованого графа в глибину

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

Обхід в глибину орієнтованого графа

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

Читати повністю

Пошук точок сполучення в неорієнтованому графі засобами delphi

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

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

tochka_spoluchennja_grafa_delphi11

Головне вікно проекту "Пошук точок сполучення в зв'язному неорієнтованому графі"

Як видно з малюнку, головне вікно delphi-проекту складається з наступних елементів: панель інструментів (компонент типу TPanel — служить контейнером для чотирьох кнопок «Додати вершину», «Додати ребро», «Видалити граф», «Знайти точки сполучення»), графічний редактор (компонент типу TImage) та область виводу результатів (компонент типу TMemo). Перші два з них призначені для побудови та графічного представлення зв'язного неорієнтованого графа і третій — виводить номера вершин, які для заданого графа являються точками сполучення.

Читати повністю

« Попередня сторінкаНаступна сторінка »