"> Введіть кількість вершин (від 2 до 50): <число вершин>
. Введіть ребра графа (кінець ): <перелік ребер>
. Матриця суміжності: <матриця>
. Введіть вершини A і B
. Знайдені вершини: <перелік знайдених вершин>
. шуканий вершин у графі не знайдено.
2.5.2 Повідомлення про помилки
7. Помилка! Кількість вершин має бути від 2 до 50.
. Помилка! Введено неприпустиме значення.
. Помилка! Вершини A і B не повинні збігатися.
. Помилка! Вершина A введена неправильно, спробуйте ще раз.
. Помилка! Вершина B введена неправильно, спробуйте ще раз.
. Увага! Виявлені повторювані ребра, програма буде ігнорувати повтори.
3. ОПИС ПРОГРАМИ
.1 Метод рішення задачі
Для вирішення поставленого завдання найбільш підходить метод обходу графа в глибину, який полягає в наступному: при обході в глибину ми відвідуємо перший вузол, а потім йдемо вздовж ребер графа, поки не зайдемо в глухий кут. Вузол неорієнтованого графа є глухим кутом, якщо ми вже відвідали всі примикають до нього вузли. У орієнтованому графі тупиком також виявляється вузол, з якого немає виходять ребер. Після попадання в глухий кут ми повертаємося назад уздовж пройденого шляху, поки не виявимо вершину, у якої є ще відвіданий сусід, а потім рухаємося в цьому новому напрямку. Процес виявляється завершеним, коли ми повернулися в відправну точку, а всі примикають до неї вершини вже виявилися відвідини. При виборі однієї з двох вершин ми завжди будемо вибирати вершину з меншою (в числовому або лексикографічному порядку) міткою. p align="justify"> Покажемо шматок програми, який містить алгоритм обходу графа в глибину:
Алгоритм 3.1. Обхід графа в глибину
do
{i = st [uk]; = jp; (j
{uk + +; [uk] = j; = 0; [j] = 1; (j == B)
{for (l = 0; l <= uk; l + +) [st [l]] + +; + +; = st [uk]; vp [jp] = 0; + +; -;
}
}
{jp = st [uk]; vp [jp] = 0;
jp + +; -;
}
} (uk> = 0);
3.2 Структура програми
Структур...
