Условие задачи
Дан граф G
1. Обойти граф методом поиска в глубину, взяв произвольную вершину в качестве начальной. Требуется:
• построить матрицу смежностей графа G;
• разместить вершины графа G по уровням;
• сформировать массив отцов графа G;
• формировать последовательность раскрываемых вершин;
• сформировать массивы прямых и обратных ребер графа G;
• показать состояния стека при обходе графа G.
2. Обойти граф методом поиска в ширину, взяв произвольную вершину в качестве начальной. Требуется:
• построить матрицу смежностей графа G;
• разместить вершины графа G по уровням;
• сформировать последовательность раскрываемых вершин;
• показать состояния очереди при обходе графа G.
Рисунок 7.1 – Заданный граф
Ответ
Строим матрицу смежности графа:
Обойдем граф методом поиска в глубину. Обход начнем с вершины 2, которую включаем в список вершин: V = {2}. Потомками вершины 2 являются вершины 3, 5 и 6, которые помещаем в стек: S = {3,5,6}.
Извлекаем из стека последнюю добавленную вершину вершину 6 (S = {3,5}), так как ее нет в списке посещенных вершин, добавляем ее в список вершин: V = {2,6}.
Потомками вершины 6 я...
