Алгоритми на графах та їх практичне застосування

ЗМІСТ ВСТУП

1. Загальний огляд проблеми та обґрунтування вибору програмних засобів

1.1 Значення алгоритмів на графах

1.2 Визначення та способи представлення графів

1.3 Огляд програмних засобів

2. Основні алгоритми на графах

2.1 Пошук завширшки

2.2 Пошук в глибину

2.3 Побудова мінімального остового дерева. Алгоритм Прима

2.4 Алгоритм Дейкстри

2.5 Модель Флойда-Уоршалла

3. Програмна реалізація алгоритмів

3.1 Огляд можливостей мови програмування

3.2 Опис функцій програмної моделі

3.3 Інтерфейс програми ВИСНОВКИ ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ

ВСТУП

Спробуйте намалювати «заклеєний конверт» одним розчерком пера, тобто не відриваючи ручки від паперу й не проводячи двічі один і той самий відрізок. Такого роду запитання з давніх-давен цікавили математиків.

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

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

В наш час теорія графів є дуже актуальною. Вона використовується у багатьох сферах людського життя для опису взаємозв'яків між об'єктами, процесами чи подіями. Граф — це досить чітка модель для вивчення окремих явищ навколишньої дійсності. Тому темою моєї роботи є «Алгоритми на графах та їх практичне застосування», адже теорія графів має не тільки наукову, а й практичну цінність. Останнім часом зв’язані з графами методи досліджень використовуються не тільки в математиці, але і у фізиці, хімії, біології, географії та інших науках.

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

Для досягнення поставленої мети в роботі вирішені наступні задачі:

— розглянуті і проаналізовані підходи до рішення задачі;

— обґрунтовано вибір технічних засобів для рішень завдань;

— визначені основні поняття теорії графів та засоби їх представлення у комп’ютерних програмах;

— визначена структура даних для вирішення поставленої задачі;

— розроблено програмний засіб побудови, відображення та використання графів за допомогою середовища Microsoft Visual Studio 2010 а також намічені шляхи його подальшого розвитку.

Об'єктом дослідження в даній дипломній роботі виступає теорія графів, основні алгоритми теорії графів та їх застосування при розв’язуванні задач.

Предметом дослідження є застосування теорії графів при розв’язанні завдань різних видів та вивчення елементів теорії графів.

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

У першому розділі розглянуто коло питань пов’язаних з формальним визначенням, способами подання графів та обґрунтовується вибір програмних засобів.

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

У третьому розділі наведено програмну реалізацію алгоритмів та можливості мови програмування Visual Basic .Net, які є вирішальними при програмуванні алгоритмів.

Отримані результати можуть бути впроваджені в практику Горлівського регіонального інституту під час вивчення змістовного модуля «Теорія графів».

1. Загальний огляд проблеми та обґрунтування вибору програмних засобів

1.1 Значення алгоритмів на графах Передусім, декілька слів про те, як виникає поняття графа з природних умов завдань. Наведемо декілька прикладів.

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

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

Мережа комп’ютерів, сполучених дротяними лініями зв’язку.

Набір слів, кожне з яких починається на певну букву і закінчується на цю ж або іншу букву.

Множина кісток доміно. Кожна кістка має 2 числа: ліву і праву половину кістки.

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

Генеалогічні дерева, що вказують споріднені стосунки між людьми.

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

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

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

Родоначальником теорії графів прийнято вважати Леонарда Ейлера, який у 1736 році розв’язавши життєву задачу про Кенігсберзькі мости, встановив властивості зв’язаного графа та зробив деякі загальні висновки.

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

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

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

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

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

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

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

Основні властивості алгоритму:

1. Масовість — алгоритм повинен бути застосований для цілого класу однотипних задач ;

2. Закінченість — алгоритм повинен складатися з кінцевого числа кроків, кожен з яких виконується за кінцевий проміжок часу.

3. Результативність — по закінченні роботи алгоритму повинен бути отриманий певний результат.

4. Однозначність — застосування алгоритму до одних і тих же вихідних даних завжди повинно давати один і той же результат.

5. Правильність — застосування алгоритму до правильних вихідних даних або допустимих вихідних даних повинно приводити до отримання необхідних результатів. Доказ правильності алгоритму — один із найбільш складних етапів його створення. Найбільш поширена процедура правильності алгоритму — це обґрунтування правомірності і перевірка правильності виконання кожного з кроків на наборі тестів, підібраних так, щоб охопити всі допустимі вхідні дані і всі допустимі вихідні дані.

6. Ефективність — алгоритм повинен забезпечувати рішення завдання за мінімальний проміжок часу з мінімальними витратами пам’яті. Для оцінки алгоритмів існує багато критеріїв. Найчастіше оцінка алгоритму полягає в оцінці часових витрат на вирішення завдання в залежності від «розміру» вихідних даних. Використовується також термін, тимчасова здатність і «трудомісткість алгоритму». Фактично ця оцінка зводиться до оцінки кількості основних операцій, які виконуються алгоритмами, оскільки кожна конкретна операція виконується за кінцевий заздалегідь відомий час.

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

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

G = (V, Е) (1.1)

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

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

Таблиця 1.1 — Приклади неорієнтованих графів

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

а)б) в)

Рисунок 1.1 — Приклад зображення графів У графі важливий тільки факт наявності зв’язку між двома вершинами. Від способу зображення цього зв’язку структура графа не залежить. Наприклад, три графи на рис. 1.2 співпадають, а два графи на рис. 1.3 — різні.

Рисунок 1.2 — Три способу зображення одного графа Рисунок 1.3 — Приклад двох різних графів З приведеного вище визначення витікає, що в класичних графах не буває петель — ребер, що сполучають деяку вершину саму з собою (рис. 1.4). Крім того, в класичному графові не буває двох різних ребер, що сполучають одну і ту ж пару вершин.

Рисунок 1.4 -Псевдограф Ребро е і вершина v називаються інцидентними один одному, якщо вершина v є одним з кінців ребра е. тБудь-якому ребру інцидентно рівно дві вершини, а ось вершині може бути інцидентно довільна кількість ребер, це кількість і визначає міра вершини. Ізольована вершина взагалі не має інцидентних нею ребер (її міра дорівнює 0).

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

Шлях в графі це послідовність вершин (без повторень), в які будь-які дві сусідні вершини суміжні. Наприклад, в графові, зображеному на рисунку 1.2, є два різні шляхи з вершини a в вершину с: adbc та abc. Вершина v досяжна з вершини u, якщо існує шлях, що починається в u та що закінчується в v. Граф називається зв’язним, якщо усі його вершини взаємно досяжні.

Компонента зв’язності - це максимальний зв’язний підграф. У загальному випадку граф може складатися з довільної кількості компонент зв’язності. Помітимо, що будь-яка изолированнаявершина є окремою компонентою зв’язності. На рисунку 1.5 зображений граф, що складається з чотирьох компонент зв’язності: [abhk], [gd], [c]і [f].

Довжина шляху — кількість ребер, з яких цей шлях складається. Наприклад, довжина вже згаданих шляхів adbc і abc (див. рис. 1.2) — 3 і 2 відповідно.

Рисунок 1.5 — Незв’язний граф Говорять, що вершина v належить kму рівню відносно вершини u, якщо існує шлях з u в v довжиною рівно k ребер. Одна і та ж вершина може відноситися до різних рівнів. Наприклад, в графові, зображеному на рисунку 1.2, відносно вершини a існує 4 рівні:

0) a ;

1) b, d ;

2) b, d, c (шляхи adb, abd, abc);

3) c (шлях adbc).

Відстань між вершинами u і v — це довжина найкоротшого шляху від u до v. З цього визначення видно, що відстань між вершинами a і c в на рисунку 1.2 рівне 2.

Цикл — це замкнутий шлях. Усі вершини в циклі, окрім першої і останньої, мають бути різні. Наприклад, циклом є шлях abda в графі на рисунку 1.2.

Ейлеров граф — це граф, в якому існує шлях або цикл, що містить усі ребра графа (вершини можуть повторюватися). Наприклад, граф на рисунку 1.6 є Ейлеровым: шуканим шляхом в нім буде dbacfbcd.

Рисунок 1.6 — Граф Эйлера Гамільтоновий граф — це граф, в якому існує шлях або цикл (без повторень ребер), що містить усі вершини графа. Наприклад, на рисунку 1.6 шуканий цикл: abdfca.

Існує досить велике число різноманітних способів представлення графів. Проте ми викладемо тут тільки найкорисніші з точки зору програмування.

Матриця суміжності Sm — це квадратна матриця розміром NxN (N — кількість вершин в графі), заповнена одиницями і нулями за наступним правилом: якщо в графі є ребро, що сполучає вершини u і v, то Sm[u, v] = 1, інакше Sm[u, v] = 0.

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

Задати зважений граф за допомогою матриці суміжності теж можливо. Необхідно лише внести невелику зміну до визначення: якщо в графі є ребро e, що сполучає вершини u і v, то Sm[u, v] = ves (e), інакше Sm[u, v] = 0. Таким чином, незважений граф можна інтерпретувати як зважений, усі ребра якого мають однакову вагу 1. Невелике утруднення виникне у тому випадку, якщо в графі дозволяються ребра з вагою 0. Тоді доведеться зберігати два масиви: один з нулями і одиницями, які служать показником наявності ребер, а другий — з вагами цих ребер.

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

Інший спосіб завдання графів полягає у використанні списку ребер. Цей спосіб завдання графів найбільш зручний для зовнішнього представлення вхідних даних. Зазвичай його представляють у вигляді: <�номер_початкової_вершини> <�номер_кінцевої_вершини> [<�вага_ребра>]. Якщо задається орієнтований граф, то номери вершин розуміються як впорядкована пара, а якщо граф неорієнтований — як неврегульована.

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

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

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

Блок-схеми можна розглядати як графічну альтернативу псевдокоду. На відміну від стандартизації синтаксису мов програмування, на синтаксис псевдокоду зазвичай не встановлюється стандартів, так як останній безпосередньо не компілюють у виконувану програму. Тому можна сказати, що зазвичай кожен варіант використання псевдокоду може бути відмінним від попередньо відомих, однак щоб бути максимально зрозумілим, намагаються використовувати більш-менш сталі форми його запису, як правило, запозичені з будь-якої мови програмування. Найчастіше джерелом псевдокоду служать кілька мов, і таким чином псевдокод часто не містить специфічних ознак кожної мови програмування. Крім того, математичні вирази часто включаються в псевдокод в тому вигляді, як їх прийнято записувати в математиці, а не в мовах програмування, а деякі фрагменти псевдокоду можуть записуються фразами природної мови (російської, англійської і т.д.). Однак при цьому конструкції деяких мов програмування частіше використовуються для псевдокоду. Так, наприклад, дуже часто використовується синтаксис, схожий на синтаксис мови Pascal. Це пояснюється тим, що Pascal створювався як мова, орієнтована на задачі навчання програмування, і тому синтаксис цієї мови особливо пристосований для сприйняття людиною. Часто використовуються і інші мови: C, Algol, Fortran та інші.

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

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

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

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

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

Приклади: C++, Visual Basic, Java, Python, Ruby, Perl, Delphi (Pascal), PHP. Мовам високого рівня властиве вміння працювати з комплексними структурами даних. У більшість із них інтегрована підтримка рядкових типів, об'єктів, операцій файлового вводу-виводу і т. п.

Першою мовою програмування високого рівня вважається комп’ютерна мова Plankalkьl розроблена німецьким інженером Конрадом Цузе ще в період 1942;1946 рр. Однак, широке застосування високорівневих мов почалося з виникненням ФОРТРАН і створенням компілятора для цієї мови (1957).

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

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

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

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

Іноді в програмах використовуються цикли, вихід з яких не передбачено логікою програми. Такі цикли називаються безумовними, або нескінченними. Спеціальних синтаксичних засобів для створення нескінченних циклів, з урахуванням їх нетиповості, мови програмування не передбачають, тому такі цикли створюються за допомогою конструкцій, призначених для створення звичайних (або умовних) циклів. Для забезпечення нескінченного повторення перевірка умови в такому циклі або відсутня (якщо дозволяє синтаксис, як, наприклад, у циклі LOOP… END LOOP мови Ада), або замінюється константним значенням (while true do… в Паскаль).

Цикл з передумовою — цикл, що виконується поки істинна деяка умова, зазначена перед його початком. Ця умова перевіряється до виконання тіла циклу, тому тіло може бути не виконано жодного разу (якщо умова з самого початку хибна). У більшості процедурних мов програмування реалізується оператором while, звідси його друга назва — while-цикл.

Цикл з післяумовою — цикл, в якому умова перевіряється після виконання тіла циклу. Звідси випливає, що тіло завжди виконується хоча б один раз. У мові Паскаль цей цикл реалізує оператор repeat. until, у Сі - do… while.

У трактуванні умови циклу з післяумовою в різних мовах є деякі розбіжності. У Паскаль і мовах, що пішли від нього, умова такого циклу трактується як умова виходу (цикл завершується, коли умова істинна, «цикл до»), а в Сі і його нащадках — як умова продовження (цикл завершується, коли умова хибна, такі цикли іноді називають «цикл поки»).

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

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

Легко побачити, що за допомогою циклу з виходом із середини можна легко змоделювати і цикл із передумовою (розмістивши команду виходу в самому початку циклу), і цикл з післяумовою (розмістивши команду виходу в кінці тіла циклу).

Частина мов програмування містять спеціальні конструкції для організації циклу з виходом із середини. Так, в мові VB.Net для цього використовується конструкція Do… LOOP і команда виходу EXIT DO:

Do While условие

[ Частина тіла циклу ]

Частина тіла циклу<�умова вихода> [ Exit Do ]

[ Частина тіла циклу ]

Loop

Тут всередині циклу може бути будь-яка кількість команд виходу.

У тих мовах, де подібних конструкцій не передбачено, цикл з виходом із середини може бути змодельовано за допомогою будь-якого умовного циклу і оператора дострокового виходу з циклу (такого, як break в Сі), або оператора безумовного переходу goto.

Цикл з лічильником — цикл, в якому деяка змінна змінює своє значення від заданого початкового значення до кінцевого значення з деяким кроком, і для кожного значення цієї змінної тіло циклу виконується один раз. У більшості процедурних мов програмування реалізується оператором for, в якому вказується лічильник (так звана «змінна циклу»), необхідна кількість проходів (або граничне значення лічильника) і, можливо, крок, з яким змінюється лічильник.

Цикл з лічильником завжди можна записати як умовний цикл, перед початком якого лічильнику присвоюється початкове значення, а умовою виходу є досягнення лічильником кінцевого значення; до тіла циклу при цьому додається оператор зміни лічильника на заданий крок. Однак спеціальні оператори циклу з лічильником можуть ефективніше транслюватися, так як формалізований вигляд такого циклу дозволяє використовувати спеціальні процесорні команди організації циклів.

У деяких мовах, наприклад, Сі та інших, що пішли від неї, цикл for, незважаючи на синтаксичну форму циклу з лічильником, насправді є циклом з передумовою. Тобто в конструкції for спочатку пишеться довільна ініціалізація циклу, а потім — умова продовження і, нарешті, деяка операція, яка виконується після кожного тіла циклу (це не обов’язково має бути зміна лічильника; це може бути правка покажчика або яка-небудь зовсім стороння операція). Для мов такого виду вищеописана проблема вирішується дуже просто: змінна-лічильник поводиться абсолютно передбачувано і по завершенні циклу зберігає своє останнє значення.

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

Повне число виконань тіла внутрішнього циклу не перевищує добутку числа ітерацій внутрішнього і всіх зовнішніх циклів. Наприклад взявши три вкладених один в одного цикли, кожен по 10 ітерацій, отримаємо 10 виконань тіла для зовнішнього циклу, 100 для циклу другого рівня і 1000 в самому внутрішньому циклі.

Одна з проблем, пов’язаних з вкладеними циклами — організація дострокового виходу з них. У багатьох мовах програмування є оператор дострокового завершення циклу (break в Сі, exit в VB.Net, last в Perl і т. п.), але він, як правило, забезпечує вихід тільки з циклу того рівня, звідки викликаний. Виклик його з вкладеного циклу призведе до завершення тільки цього внутрішнього циклу, зовнішній же цикл продовжить виконуватися. Проблема може здатися надуманою, але вона дійсно іноді виникає при програмуванні складної обробки даних, коли алгоритм вимагає негайного переривання в певних умовах, наявність яких можна перевірити тільки в глибоко вкладеному циклі.

Рішень проблеми виходу з вкладених циклів кілька.

? Найпростіший — використовувати оператор безумовного переходу goto для виходу в точку програми, безпосередньо наступної за вкладеним циклом. Цей варіант критикується прихильниками структурного програмування, як і всі конструкції, що вимагають використання goto. Деякі мови програмування, наприклад Modula-2, просто не мають оператора безумовного переходу, і в них подібна конструкція неможлива.

? Альтернатива — використовувати штатні засоби завершення циклів, у разі необхідності встановлюючи спеціальні прапори, які потребують негайного завершення обробки. Недолік — ускладнення коду, зниження продуктивності без будь-яких переваг, крім теоретичної «правильності» із-за відмови від goto.

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

? Скористатися механізмом генерації та обробки виключень (виняткових ситуацій), який є зараз у більшості мов високого рівня. У цьому випадку в нештатній ситуації код у вкладеному циклі генерує виняток, а блок обробки виключень, в який поміщений весь вкладений цикл, перехоплює і обробляє його. Недолік — реалізація механізму обробки винятків у більшості випадків така, що швидкість роботи програми зменшується. Правда, в сучасних умовах це не особливо важливо: практично втрата продуктивності настільки мала, що має значення лише для дуже небагатьох додатків.

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

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

Спільні цикли є в деяких мовах програмування (VB.Net, C #, Java, JavaScript, Perl, Python, PHP, LISP, Tcl та ін) — вони дозволяють виконувати цикл по всім елементам заданої колекції об'єктів. У визначенні такого циклу потрібно вказати тільки колекцію об'єктів та змінну, якій в тілі циклу буде присвоєно значення об'єкту, який в даний момент обробляється (або посилання на нього). Синтаксис в різних мовах програмування синтаксис оператора різний, але в мові VB.Net мае наступний синтаксис:

For Each element [ As datatype ] In group

[ statements ]

[ Exit For ]

[ statements ]

Next [ element ]

Часто при написанні складних програм виникає необхідність змінити напрямок виконання послідовності операцій, в залежності від певної умови.

Оператори, які виконують роль розгалуження програми на підставі якої-небудь умови, називаються операторами умовного переходу.

Найпростішими операторами умовного переходу є оператори If

If умова Then [ Оператори 1 ] [ Else [ Оператори 2 ] ]

Умовою завжди має бути логічний вираз (тобто результат якого або true або false). Після ключового слова Then пишуться оператори, які виконуються, якщо умова істинна, після ключового слова Else пишуться оператори, які виконуються, якщо умова хибна. Частина else є необов’язковою, якщо вона відсутня, то якщо умова хибна, буде виконуватися наступний за if оператор.

Виходячи з поставлених вимог для розробки модуля реалізації алгоритмів на графах з візуалізацією етапів розробки доцільно для розробки використати Object-технологію — інтерфейс користувача розробити в середовищі програмування Visual Studio 2010, використовуючи мову програмування Visual Basic .Net.

Платформа Microsoft. NET надає:

? Стійке середовище виконання CLR (Common Language Runtime), яке входить до складу даної платформи;

? Засоби розробки додатків на будь-якій з багатьох мов програмування, що підтримуються платформою.NET;

? Величезну бібліотеку класів NET Framework, що лежить в основі відкритої моделі програмування. Вони доступні в будь-якій мові програмування, що підтримується платформою.NET;

? Підтримку мережевої інфраструктури, побудованої на верхньому рівні стандартів Internet, внаслідок чого забезпечується високий рівень взаємодії між додатками;

? Підтримку нового промислового стандарту, а саме технології Web-служб. Технологія Web-служб надає новий механізм створення розподілених додатків. По суті, вона є поширенням технології створення додатків на базі компонентів і на сферу Internet;

? Модель безпеки, що програмісти можуть легко використовувати у своїх програмах;

? Потужні інструментальні засоби розробки.

2. Основні алгоритми на графах

2.1 Пошук завширшки Пошук завширшки (breadth-first search)є одним з простих алгоритмів для обходу графа і є основою для багатьох важливих алгоритмів для роботи з графами. Наприклад, алгоритм Прима (Prim) пошуку мінімального остовного дерева або алгоритм Дейкстры (Dijkstra) пошуку найкоротшого шляху з однієї вершини використовують ідеї, схожі з ідеями, використовуваними при пошуку завширшки.

Пошук завширшки був формально запропонований Э. Ф. Муром в контексті пошуку шляху в лабіринті. Лі незалежно відкрив той же алгоритм в контексті розводки провідників на друкованих платах.

Пошук завширшки може застосовуватися для вирішення завдань, пов’язаних з теорією графів, :

— хвилевий алгоритм пошуку шляху в лабіринті (алгоритм Лі);

— хвилеве трасування друкованих плат;

— пошук компонент зв’язності в графі;

— пошук найкоротшого шляху між двома вузлами незваженого графа;

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

— знаходження найкоротшого циклу в орієнтованому незваженому графові;

— знаходження усіх вершин і ребер, що лежать на якому-небудь найкоротшому шляху між двома вершинами a і b;

— пошук збільшуючого шляху в алгоритмі Форда-Фалкерсона (алгоритм Едмондса-Карпа).

Нехай заданий граф G = (V, Е) і виділена початкова (source) вершина s. Алгоритм пошуку завширшки систематично обходить усі ребра G для «відкриття» усіх вершин, досяжних з s, обчислюючи при цьому відстань (мінімальну кількість ребер) від s до кожної досяжної з s вершини. Крім того, в процесі обходу будується «дерево пошуку завширшки» з коренем s, що містить усі досяжні вершини. Для кожної досяжної з s вершини v шлях в дереві пошуку завширшки відповідає найкоротшому (тобто що містить найменшу кількість ребер) шляху від s до v в G. Алгоритм працює як для орієнтованих, так і для неорієнтованих графів.

Пошук завширшки має таку назву тому, що в процесі обходу ми йдемо вшир, тобто перш ніж приступити до пошуку вершин на відстані k +1, виконується обхід усіх вершин на відстані k.

Для відстежування роботи алгоритму пошук завширшки розфарбовує вершини графа в білий, сірий і чорний кольори. Спочатку усі вершини білі, і пізніше вони можуть стати сірими, а потім чорними. Коли вершина відкривається (discovered) в процесі пошуку, вона забарвлюється. Таким чином, сірі і чорні вершини — це вершини, які вже були відкриті, але алгоритм пошуку завширшки по-різному працює з ними, щоб забезпечити оголошений порядок обходу. Якщо і вершина u чорного кольору, то вершина v або сіра, або чорна, тобто усі вершини, суміжні з чорною, вже відкриті. Сірі вершини можуть мати білих сусідів, будучи межею між відкритими і невідкритими вершинами.

Пошук завширшки будує дерево пошуку завширшки, яке спочатку складається з одного кореня, яким є початкова вершина s. Якщо в процесі сканування списку суміжності вже відкритої вершини і відкривається біла вершина v, то вершина v і ребро (u, v) додаються в дерево. Ми говоримо, що і є попередником (predecessor), або батьком (parent), v в дереві пошуку вшир. Оскільки вершина може бути відкрита не більше одного разу, вона має не більш одного батька. Взаємини предків і нащадків визначаються в дереві пошуку завширшки як завжди — якщо і знаходиться на шляху від кореня s до вершини v, то u є предком v, a v — нащадком u.

Приведена нижче процедура пошуку завширшки BFS припускає, що вхідний граф G = (V, Е) представлений за допомогою списків суміжності. Крім того, підтримуються додаткові структури даних в кожній вершині графа. Колір кожної вершини u і v зберігається в змінній color [u], а попередник — в змінній р [u]. Якщо попередника у і немає (наприклад, якщо u = s або u не відкрита), то р [u]= NIL. Відстань від s до вершини u, що обчислюється алгоритмом, зберігається в полі d[u]. Алгоритм використовує чергу Q типу FIFO для роботи з множиною сірих вершин Взагалі черга в програмуванні це динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній «базарній» черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена) Основні операції з чергою:

enqueue — «поставити в чергу». Операція додавання елемента в «хвіст» черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення

dequeue — «отримання з черги». Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація «незаповнення» .

Псевдокод алгоритму пошуку завширшки має наступний вигляд:

Процедура BFS працює таким чином. У рядках 1−4 усіх вершини, за винятком початкової вершини s, забарвлюються в білий колір, для кожної вершини u полю d [u] привласнюється значення ?, а як батько для кожної вершини встановлюється nil. У рядку 5 початкова вершина s забарвлюється в сірий колір, оскільки вона розглядається як відкрита на початку процедури. У рядку 6 її полю привласнюється значення 0, а в рядку 7 її батьком стає nil. У рядках 8−9 створюється порожня черга Q, в яку поміщається один елемент s.

Цикл while в рядках 10−18 виконується до тих пір, поки залишаються сірі вершини (тобто відкриті, але списки суміжності яких ще не проглянуті). Інваріант цього циклу виглядає таким чином: При виконанні перевірки в рядку 10 черга Q складається з множини сірих вершин.

Легко побачити, що він виконується перед першою ітерацією і що кожна ітерація циклу зберігає інваріант. Перед першою ітерацією єдиною сірою вершиною і єдиною вершиною в черзі Q, являється початкова вершина s. У рядку 11 визначається сіра вершина u в голові черги Q, яка потім віддаляється з черги. Цикл for в рядках 12−17 переглядає усі вершини v в списку суміжності u. Якщо вершина v біла, значить, вона ще не відкрита, і алгоритм відкриває її, виконуючи рядки 14−17. Вершині призначається сірий колір, дистанція d [v] встановлюється рівною d[u] + 1, а як її батько вказується вершина u. Після цього вершина поміщається в хвіст черги Q. Після того, як усі вершини із списку суміжності u проглянуті, вершині u привласнюється чорний колір. Інваріант циклу зберігається, оскільки усі вершини, які забарвлюються в сірий колір (рядок 14), вносяться до черги (рядок 17), а вершина, яка віддаляється з черги (рядок 11), забарвлюється в чорний колір (рядок 18).

Результат пошуку завширшки може залежати від порядку перегляду вершин, суміжних з цією вершиною, в рядку 12. Дерево пошуку завширшки може змінюватись, але відстані d, вичислені алгоритмом, не залежать від порядку перегляду.

Оцінимо час роботи алгоритму для вхідного графа G = (V, E). Після ініціалізації жодна вершина не забарвлюється в білий колір, тому перевірка в рядку 13 гарантує, що кожна вершина вноситься до черги не більше одного разу, а отже, і віддаляється з черги вона не більше одного разу. Операції внесення до черги і видалень з неї вимагають O (1) часу, так що загальний час операцій з чергою складає О (V). Оскільки кожен список суміжності сканується тільки при видаленні відповідної вершини з черги, кожен список сканується не більше одного разу. Оскільки сума довжин усіх списків суміжності рівна И (Е), загальний час, необхідний для сканування списків, рівний О (Е). Накладні витрати на ініціалізацію рівні О (V), так що загальний час роботи процедури BFS складає Про (V + Е). Таким чином, час пошуку завширшки лінійно залежить від розміру представлення графа G з використанням списків суміжності.

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

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

Як і у разі пошуку завширшки, коли вершина V відкривається в процесі сканування списку суміжності вже відкритої вершини u, процедура пошуку записує цю подію, встановлюючи поле попередника v р[v] рівним u. На відміну від пошуку завширшки, де підграф передування утворює дерево, при пошуку в глибину підграф передування може складатися з декількох дерев, оскільки пошук може виконуватися з декількох початкових вершин.

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

Пошук в глибину також проставляє у вершинах мітки часу (timestamp). Кожна вершина має дві такі мітки — першу d [v], у якій вказується, коли вершина v відкривається (і зафарбовується в сірий колір), і друга — f[v], яка фіксує момент, коли пошук завершує сканування списку суміжності вершини v і вона стає чорною. Ці мітки використовуються багатьма алгоритмами і корисні при розгляді поведінки пошуку в глибину.

Приведена нижче процедура DFS записує в полі d [u момент, коли вершина u відкривається, а в полі f [u] - момент завершення роботи з вершиною u. Ці мітки часу є цілими числами в діапазоні від 1 до 2 |V|, оскільки для кожної з |V| вершин є тільки одна подія відкриття і одне — завершення. Для кожної вершини u виконується співвідношення:

До моменту часу d [u] вершина має колір WHITE, між d[u] і f[u] - колір GRAY, а потім f [u] - колір BLACK.

Далі представлений псевдокод алгоритму пошуку в глибину. Вхідний граф G може бути як орієнтованим, так і неорієнтованим. Змінна time — глобальна і використовується нами для міток часу.

Процедура DFS працює таким чином. У рядках 1−3 усіх вершини забарвлюються в білий колір, а їх поля р ініціалізувалися значенням nil. У рядку 4 виконується скидання глобального лічильника часу. У рядках 5−7 по черзі перевіряються усі вершини з V, і коли виявляється біла вершина, вона оброблюється за допомогою процедури DFS_VISIT. Кожного разу при виклику процедури DFS_Visit (u) в рядку 7, вершина u стає коренем нового дерева лісу пошуку в глибину. При поверненні з процедури DFS кожній вершині u зіставляються два моменти часу — час відкриття (discovery time) d [u] і час завершення (finishing time) f[u].

При кожному виклику DFS_visit (u) вершина u спочатку має білий колір. У рядку 1 вона забарвлюється в сірий колір, в рядку 2 збільшується глобальна змінна time, а в рядку 3 виконується запис нового значення змінній time в полі часу відкриття d[u]. У рядках 4−7 досліджуються усі вершини, суміжні з u, і виконується рекурсивне відвідування білих вершин. При розгляданні в рядку 4 вершини v, суміжною з u, ми говоримо, що ребро (u, v) досліджується (explored) пошуком в глибину. І нарешті, після того, як будуть досліджені усі ребра, що покидають u, в рядках 8−9 вершина і забарвлюється в чорний колір, а в полі f [u] записується час завершення роботи з нею.

Зауважимо, що результат пошуку в глибину може залежати від порядку, в якому виконується розгляд вершин в рядку 5 процедур DFS, а також від порядку відвідування суміжних вершин в рядку 4 процедури DFS_visit. На практиці це зазвичай не викликає яких-небудь проблем, оскільки зазвичай ефективно використаний може бути будь-який результат пошуку в глибину, призводячи по суті до однакових результатів роботи алгоритму, що спирається на пошук в глибину.

Чому дорівнює час роботи процедури DFS? Цикли в рядках 1−3 і 5−7 процедури DFS виконуються за час И (V), виключаючи час, необхідний для виклику процедури DFS_visit. Процедура DFS_visit викликається рівно по одному разу для кожної вершини, оскільки вона викликається тільки для білих вершин, і перше, що вона робить, — це забарвлює передану як параметр вершину в сірий колір. В процесі виконання DFS_Visit (v) цикл в рядках 4−7 виконується раз. Оскільки, загальна вартість виконання рядків 4−7 процедур DFS_VlSlT рівна И (Е). Час роботи процедури DFS, таким чином, рівний И (V + Е).

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

Опишемо процедуру виконання цього алгоритму. Позначимо через N={1,2,…, n}множина вузлів мережі і введемо нові позначення:

Ck — множина вузлів мережі, з'єднаних алгоритмом після виконання k-й ітерації цього алгоритму,

— множина вузлів мережі, з'єднаних з вузлами безлічі Ck після виконання k-й ітерації цього алгоритму.

Крок 0. Думаємо C0 = і = N.

Крок1. Вибираємо будь-який вузол і з множини визначаємо C1 = {i}, тоді = N-{i}. Думаємо k = 2.