я. Если існує орієнтований шлях з вершини у вершину, то вершина назівається предком вершини, а вершина - Нащадки вершини.
Приклад. Візначіті батьків и Синів, братів, предків и нащадків Коренєва орієнтованого дерева, збережений на на Наступний малюнку.
розв язання: є батьком і;- Батьком і;- Батьком, і;- Батьком і;- Батьком;- Батьком і. І навпаки: і - сині; і - сині; , І - сині; і - сині;- Сін; і - сині.
Груп нащадків и предків можна віділіті Дуже багато, пріведемо лишь деякі приклада: - нащадки, отже, - предок для; є Нащадки, отже, - предок.
5.10 Алгоритми поиска найкоротшіх Шляхів
Розглянемо орієнтований граф G=(V, E), дугам которого пріпісані ваги. Це означає, что Кожній дузі (u, v) поставлено у відповідність деяке дійсне число a (u, v), Пожалуйста назівається вагою даної дуги. Вважаємо a (u, v)=?, если дуга (u, v) НЕ існує.
Під довжина шляху будемо розуміті торбу ваг дуг, з якіх складається шлях. Довжину найкоротшого шляху будемо позначаті d (s, t) i назіваті відстанню від s до t. Якщо не існує жодних шляху з s в t, то Вважаємо d (s, t)=?.
Введемо ще одне обмеження. Нехай ваги дуг будут только додатного значення. Тому що при існуванні дуг з від ємнімі вагамі довжина найкоротшого шляху между парою вершин становится невизначенності, віходячі з возможности кількаразового включення таких дуг у шлях.
Если відома відстань между парою вершин, можна легко візначіті найкоротшій шлях. Тому що для двох довільніх вершин s и t (s? T) існує така вершина v, что d (s, t)=d (s, v) + d (v, t). Цією властівістю володіє и передостання вершина в найкоротшому шляху від s до t. Отже, визначаючи в такий способ передостанню вершину, можна пройти від кінця найкоротшого шляху до его качана.
Більшість відоміх алгоритмів знаходження відстані между двома вершинами s и t можна описати Наступний послідовністю Дій:
) При заданій матриці ваг дуг A [u, v], обчіслюємо деякі Верхні обмеження D [v] на відстані від s до всіх вершин v.
) Щораз, коли з'ясовується, что D [u] + A [u, v] lt; D [v], поліпшуємо оцінку D [v]=D [u] + A [u , v].
) Процес закінчується, коли подалі Поліпшення Жодний с ограниченной Неможливо. Значення кожної D [u] дорівнює відстані d (s, u). Вершину s у Цьом випадка назівають Джерелом.
5.10.1 Алгоритм поиска у глибино
Робота всякого алгоритмом обходу складається в послідовному відвідуванні вершин и дослідженні ребер. Які самє Дії віконуються при відвідуванні вершини и дослідженні ребра - поклади від конкретної задачі, для розв язування якої віконується обхід. У шкірному разі факт відвідування вершини запам'ятовується, так что з моменту відвідування и до кінця роботи алгоритму вона вважається відвідуваною. Вершину, что щє не відвідана, назівають новою. У результате відвідування вершина становится відкрітою и залішається такою, поки НЕ БУДУТЬ досліджені всі інцідентні Їй ребра. После цього вона превращается в Закритого.
Існує много алгоритмів на графах, в Основі якіх лежить систематичний перебір вершин, такий, что Кожна вершина проглядається в точності один раз. Тому Важлива задачею є знаходження гарних методів пошуку в графі. Метод поиска гарний,если ВІН дозволяє алгоритмом розв язання задачі, что цікавить нас, легко використовуват цею метод, и Кожне ребро графа аналізується НЕ более одного разу (або Кількість таких ДОСЛІДЖЕНЬ обмежена зверху).
Поиск у глибино - це найбільш Важлива Завдяк чісленності Додатків стратегія обходу графа. Ідея цього методу - шлях вперед у недосліджену область, поки це можливо, если ж вокруг все досліджено, відступіті на крок назад і шукати Нові возможности для продвижения вперед. Метод пошуку в глибино відомій під різнімі Назв: бектрекінг raquo ;, поиск з поверненням .
Обхід почінається з відвідування заданої стартової вершини a, что становится активною и Єдиною відкрітою вершиною. Потім вібірається інцідентне вершіні a ребро (a, y) i відвідується вершина y. Вона становится відкрітою и активною. Надалі, як и при поиска завширшки, шкірні черговий крок почінається з Вибори актівної вершини з множини відкритих вершин. Если всі ребра, Які інцідентні актівній вершіні x, вже досліджені, вон превращается в Закритого. У протилежних випадка вібірається Одне з недослідженіх ребер (x, y), це ребро досліджується. Если вершина y нова, то вона відвідується и превращается у відкриту.
При пошуку в глибино в якості актівної вібірається та з відкритих вершин, что булу відвідана последнего. Для реализации такого правила Вибори найбільш ЗРУЧНИЙ структурою зберігання множини в...
