ідкритих вершин є стек: вершини, Які відкріваються, складаються в стек у ТІМ порядку, у якому смороду відкріваються, а в якості актівної вібірається остання вершина.
5.10.2 Алгоритм поиска завширшки
Поиск завширшки - це класичний метод розв язування задачі знаходження найкоротшого шляху между двома конкретними вершинами графа. Найкоротшій шлях - це такий шлях, что з єднує вершини графа та володіє тією властівістю, что ніякий Інший шлях, что з єднує ЦІ вершини, що не містіть менше число ребер. Поиск у глибино мало прідатній для розв язування цієї задачі, оскількі пропонованій Їм порядок проходження графа НЕ має відношення до поиска найкоротшіх Шляхів, а поиск завширшки призначеня самє для Досягнення цієї мети.
Розглянемо метод поиска завширшки. У Розглянуто методі пошуку в глибино чім пізніше буде відвідана вершина, тім Ранее вона буде Використана - точніше, так буде при допущенні, что одного вершина відвідується перед використанн Першої. Це прямий наслідок того факту, что переглянуті, альо галі не вікорістані вершини накопічуються в стеці. Поиск завширшки, грубо говорячі, ґрунтується на заміні стека черго.
Ідея поиска завширшки Полягає в тому, щоб відвідуваті вершини в порядку їхньої далекості від деякої Заздалегідь обраної або зазначеної стартової вершини a. Інакше Кажучи, спочатку відвідується сама вершина a, потім всі вершини, суміжні з a, тобто Які знаходяться від неї на відстані 1, потім вершини, что перебувають від a на відстані 2, и далі по далекості.
Розглянемо алгоритм поиска завширшки Із завданні стартовою вершиною a. Спочатку всі вершини позначаються як нові. Першів відвідується вершина a, вон становится Єдиною відкрітою вершиною. Надалі Кожний черговий крок почінається з Вибори деякої Відкритої вершини x. Ця вершина становится активною. Далі досліджуються ребра, інцідентні актівній вершіні. Если таке ребро з'єднує вершину x з новою вершиною y, то вершина y відвідується и превращается у відкриту. Колі всі ребра, інцідентні актівній вершіні, досліджені, вон перестає буті активною и становится закритою. После цього вібірається нова активна вершина, и опісані Дії повторюються. Процес закінчується, коли множини відкритих вершин становится порожнє.
Основна особлівість поиска завширшки, что відрізняє его от других способів обходу графів, Полягає в тому, что в якості актівної вершини вібірається та з відкритих, яка булу відвідана Ранее других. Саме ЦІМ забезпечується головна властівість поиска завширшки: чім Ближче вершина до старту, тім Ранее вона буде відвідана. Для реализации такого правила Вибори актівної вершини Зручне вікорістаті для зберігання множини відкритих вершин черго - колі нова вершина становится відкрітою, вон додається в Кінець Черги, а активна вібірається в ее качана.
обидвоє методи пошуку в графі - у глибино и завширшки могут буті вікорістані для знаходження шляху между фіксованімі вершинами a и b. Досить початиться поиск у графі з вершини a и вести его до моменту відвідування вершини b.
Перевага пошуку в глибино є тією факт, что в момент відвідування вершини b СТІК містіть послідовність вершин, что візначає шлях з a в b. Це становится очевидно, если відзначіті, что Кожна вершина, что попадає в стек, є суміжною з попередня.
Однак недоліком пошуку в глибино є ті, что отриманий у такий способ шлях у загально випадка НЕ ??буде найкоротшім путем з a в b. Від цього недоліку вільний метод знаходження шляху, Заснований на поиска завширшки.
5.10.3 Алгоритм Дейкстри
Найбільш Ефективний алгоритм поиска найкоротшіх Шляхів на графах давши Дейкстра. Едсгер Вібе Дейкстра (нідерл. Edsger Wybe Dijkstra; народився 11травня +1930 року в Роттердамі (Нідерланди) - помер 6 серпня 2 002 року) - видатний нідерландській вчений, Ідеї которого Зробі Величезне Вплив на розвиток комп ютерної индустрии. Популярність Дейкстрі принесли его роботи в Галузі! Застосування математичної логіки при розробці комп ютерних програм. ВІН взявши активну участь в розробці мов програмування. Один з авторів Концепції структурного программирования и алгоритмом знаходження найкоротшого шляху на орієнтованому графі з вагамі ребер, відомій як Алгоритм Дейкстри. У +1972 году Дейкстра ставши лауреатом премії Тьюрінга.
Нехай G=(V, E) - зваження орієнтований граф, w (vi, vj) - вага дуги (vi, vj). Почаїв з вершини a, знаходімо відстань від a до кожної Із суміжніх Із нею вершин. Вібіраємо вершину, відстань від якої до вершини a найменша; нехай це буде вершина v *. Далі знаходімо відстані від вершини a до кожної вершини суміжної з v * вздовж шляху, Який проходити через вершину v *. Если для якоїсь Із таких вершин ця відстань Менша від поточної, то замінюємо нею поточних відстань. Зно...
