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