Дан граф G 1. Обойти граф методом поиска в глубину, взяв произвольную вершину в качестве начальной. Требуется: • построить матрицу смежностей графа G;

22 января 2025
Высшая математика

Условие:

Дан граф 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 я...