Алгоритми на графах
Алгоритми обходу графів у глибину та за рівнями
Працюючи з графами часто доводиться виконувати будь-яку дію по одному з кожної з вершин графа. Наприклад, деяку порцію інформації слід передати кожному комп'ютеру в мережі. Подібний обхід можна здійснювати двома різними способами. При обході в глибину прохід вибраним шляхом здійснюється настільки глибоко, наскільки це можливо, а при обході за рівнями ми рівномірно рухаємося вздовж усіх можливих напрямків
Обхід углиб
При обході в глибину відвідується перший вузол, а потім відбувається переміщення вздовж ребер графа доти, доки не зустрінеться глухий кут. Вузол неорієнтованого графа є глухим кутом, якщо всі вузли, що примикають до нього, вже були відвідані. В орграфі глухим кутом також називається вузол, з якого немає ребер, що виходять. Після потрапляння в глухий кут необхідно пересуватися назад вздовж пройденого шляху доти, доки не буде виявлена вершина, у якої є ще не відвіданий сусід, і потім рухатися в цьому новому напрямку. Процес виявляється завершеним, коли відбулося повернення у відправну точку, і всі вершини, що примикали до неї, вже були відвідані.
Рекурсивний алгоритм обходу в глибину наведено нижче:
v – поточний вузол
for кожногоребраvwграфаG do
Цей рекурсивний алгоритм використовує системний стек для відстеження поточної вершини графа, що дозволяє правильно здійснити повернення, натрапивши на глухий кут. Можна побудувати нерекурсивний алгоритм, скориставшись стеком для збереження та видалення інформації про пройдені вершини.
Обхід за рівнями
При обході рівнями після відвідування першого вузла відвідуються всі сусідні з ним вершини. При другому проході відвідуються всі вершини, що знаходяться на відстані двох ребер відПочатковий. При кожному новому проході обходяться всі вершини, відстань яких до початкової на одиницю більше попереднього. Для запобігання повторному відвідуванню необхідно або вести список відвіданих вершин, або зберігати інформацію про відвідування у відповідній структурі даних вузла. Нижче наведено приклад реалізації алгоритму обходу за рівнями:
while черга непуста do
для кожного ребра xw у графі G do
Алгоритми пошуку мінімального остовного дерева
Мінімальним кістяковим деревом (МОД) зв'язкового зваженого графа називається його зв'язковий подграф, що складається з усіх вершин вихідного графа і деяких його ребер, причому сума ваг ребер є мінімально можливою. Таке дерево може знадобитися, наприклад, для комп'ютерної мережі.