аф. Розглянемо список полів:
· tn - посилання на транспортну мережу в яку входить вершина, необхідна для доступу до інших об'єктів входять до транспортну мережу;
· X - координата центру вершини в рамках транспортної мережі;
· Y - координата центру вершини в рамках транспортної мережі;
· IsStart - ознака того, що ця вершина є стартовою для задачі пошуку оптимального шляху в транспортній мережі;
· IsFinish - ознака того, що ця вершина є кінцевою для задачі пошуку оптимального шляху в транспортній мережі;
· IsPartOfPath - ознака того, що ця вершина є частиною оптимального шляху;
· iGraph - індекс графа, в який входить вершина;
· iEdge - масив, що містить номери ребер, що виходять їх поточної вершини.
Розглянемо список методів:
· конструктор Vertex (TransportNetwork tn, int iGraph, int X, int Y) здійснює ініціалізацію вершини, при цьому вершина відразу отримує координати свого розташування;
· деструктор ~ Vertex () здійснює видалення вершини.
Перейдемо до розгляду класу Edge, який містить в собі опис ребер, що входять до граф. Розглянемо список полів:
· SrcVertex - номер вершини з якої виходить це ребро;
· DestVertex - номер вершини в яку входить це ребро;
· IsPartOfPath - ознака того, що це ребро є частиною знайденого оптимального маршруту;
· Weight - вага ребра, буде інтерпретуватися як ціле беззнаковое число.
Розглянемо список методів:
· конструктор Edge (int srcVertex, int destVertex, int Weight) здійснює ініціалізацію ребра, при цьому вказується стартова і кінцева вершина, а так само вага додається ребра;
· деструктор ~ Edge () здійснює видалення ребра.
2.9 Алгоритми пошуку маршрутів в графі
Базовою операцією в будь-якому графову алгоритмі є повний і систематичний обхід графа. Метою обходу - відвідати кожну вершину і кожне ребро рівно один раз у суворо визначеному порядку. Існує два основних алгоритму обходу:
· пошук в ширину (breadth-first search - BFS);
· пошук в глибину (depth-first search - DFS).
Для певних завдань немає ніякої різниці, який з них ви будете використовувати, але в деяких випадках вибір стає життєво важливим.
Обидві процедури обходу графа використовують одну фундаментальну ідею, а саме: ми повинні позначати вершини, які вже бачили, щоб не намагатися відвідати їх знову. Інакше ми можемо зациклитися і ніколи не вийти з алгоритму. BFS і DFS розрізняються тільки порядком, в якому вони розглядають вершини.
2.10 Пошук в ширину
Пошук в ширину слід використовувати в тому випадку, якщо
. нам не важливий порядок, в якому ми обходимо вершини і ребра графа, тобто нас влаштує будь,
. нам потрібно знайти найкоротший шлях в незважених графі.
Пошук в ширину виконується в наступному порядку: початку обходу s приписується мітка 0, суміжним з нею вершин - мітка 1. Потім по черзі розглядається оточення всіх вершин з мітками 1, і кожної з вхідних в ці оточення вершин приписуємо мітку 2 і т.д.
Якщо вихідний граф зв'язний, то пошук в ширину позначить всі його вершини. Дуги виду (i, i + 1) породжують остовно бесконтурний орграф, що містить в якості своєї частини остовное ордерево, зване пошуковим деревом.
Легко побачити, що за допомогою пошуку в ширину можна також занумерувати вершини, нумеруя спочатку вершини з міткою 1, потім з міткою 2 і т.д.
Цей алгоритм має кілька великі вимоги щодо використання пам'яті т.к. всі шляхи шукаються паралельно. Крім того, як уже було сказано вище, він не кращим чином підходить для роботи з взешеннимі графами. До того ж, цей алгоритм не дає можливостей використання евристик, які можуть значним чином скоротити перебір.
2.11 Пошук в глибину
В основі пошуку в глибину лежить та ж ідея, що і в переборі з поверненням. Обидва алгоритми виробляють повний перебір всіх можливостей, просуваючись, поки це можливо, і повертаючись, коли не залишається недосліджених варіантів подальшого просування. Обидва алгоритми простіше розглядати як рекурсивні алгоритми.
Пошук в глибину можна розглядати як пошук в ширину з чергою, заміненої стеком. Витонченість реалізації по...
