Головна

Алгоритми обходу графа в ширину і глибину.

  1. А) Основні алгоритмічні конструкції. Базові алгоритми.
  2. Авторська позиція в «Анні Кареніній» Л. Толстого. Сенс епіграфа до роману.
  3. Алгоритм укладання графа на площині
  4. Алгоритмічні завдання пошуку в графах: завдання Прима-Краскала, Дейкстри, Форда-Фалкерсона.
  5. алгоритми
  6. Алгоритми вибору маршрутів для мобільних хостів.
  7. Алгоритми заміщення сторінок

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

опис алгоритму

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

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

Матриця суміжності і матриця інцидентності. | формальне пояснення


Поняття алгебраїчної операції і алгебраїчної структури. | Визначення та властивості груп. | Підгрупи. Перетин підгруп. Циклічні підгрупи. | Гомоморфізми і ізоморфізми груп. Ядро гомоморфізму. Ізоморфізм циклічних груп. | Визначення та властивості кілець. | Гомоморфізми кілець. | Ідеали, класи відрахувань, фактор-кільця. | Теорема про гомоморфізм кілець. | Просте поле. Теорема про ізоморфізмі простого поля. | Маршрути в графавах. |

© 2016-2022  um.co.ua - учбові матеріали та реферати