Лабораторная работа 7

1. Реализуйте обход графа в ширину с помощью deque

Шаги работы алгоритма bfs(graph, start)

1️⃣ Создаём вспомогательные структуры:

• visited = set() — множество посещённых вершин.
• queue = [start] — очередь, куда помещаем стартовую вершину.
• result = [] — список для порядка обхода вершин.

2️⃣ Запускаем цикл, пока есть элементы в очереди:

• Достаем текущую вершину node = queue.pop(0).
• Если она ещё не посещена, добавляем её в visited и записываем в result.
• Добавляем всех её непосещённых соседей в queue.

3️⃣ Повторяем шаг 2, пока очередь не пуст.

4️⃣ Возвращаем result — список вершин в порядке их посещения.

2. Реализуйте обход графа в глубину с помощью stack

Шаги работы алгоритма dfs(graph, start)

1️⃣ Создаём вспомогательные структуры:

• visited = set() — множество посещённых вершин.
• stack = [start] — стек, куда помещаем стартовую вершину.
• result = [] — список для порядка обхода вершин.

2️⃣ Запускаем цикл, пока есть элементы в стеке:

• Достаем текущую вершину node = stack.pop().
• Если она ещё не посещена, добавляем её в visited и записываем в result.
• Добавляем всех соседей вершины в stack (в обратном порядке!), чтобы при pop() они обходились в нужном порядке.

3️⃣ Повторяем шаг 2, пока стек не пуст.

4️⃣ Возвращаем result — список вершин в порядке их посещения.

3. Реализуйте решение задачи коммивояжера без использования nx.approximations

Шаги алгоритма:

1️⃣ Представление графа

• Граф задан в виде списка смежности, где graph[i][j] – это расстояние от города i до города j.
• Например, graph[0][1] = 10 означает, что расстояние от города 0 до города 1 равно 10.

2️⃣ Функция path_length(path)

• Вычисляет суммарное расстояние маршрута.
• Проходится по всем городам в маршруте, суммируя длины рёбер.
• В конце прибавляет расстояние возвращения в начальный город.

3️⃣ Перебор всех возможных маршрутов

• Используется permutations(range(1, n)) для генерации всех возможных перестановок городов, кроме стартового.
• Например, если n = 4, возможные маршруты (без старта) будут:

  
  (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
  

• К каждому такому маршруту добавляется стартовый город 0 в начало.

4️⃣ Поиск кратчайшего маршрута

• Для каждого маршрута full_path = (0, ..., ..., ...) вычисляется его длина.
• Если маршрут короче предыдущего минимального, он обновляется.

5️⃣ Вывод результата

• Выводится оптимальный маршрут (min_path), включая возврат в стартовый город.
• Выводится его общая длина (min_length).