Prog_2_4: Лабораторная работа 6. Графы

Открыто с: вторник, 11 марта 2025, 00:00

Срок сдачи: вторник, 18 марта 2025, 00:00

Основные определения

Граф — это структура, состоящая из вершин (nodes) и рёбер (edges), соединяющих вершины.
Ориентированный граф — рёбра имеют направление.
Неориентированный граф — рёбра не имеют направления.
Взвешенный граф — рёбра имеют веса.
Матрица смежности — квадратная матрица, в которой элемент A[i][j] показывает наличие ребра между iи j.
Список смежности — представление графа через список, где graph[i] — список соседей вершины i.

Матрица смежности:

INF = float('inf')

graph = [

[0, 1, INF, 1],

[1, 0, 1, INF],

[INF, 1, 0, 1],

[1, INF, 1, 0]

]

Список смежности:

graph = {

0: [1, 3],

1: [0, 2],

2: [1, 3],

3: [0, 2]

}

Задания

1. Постройте и отобразите неориентированный граф с помощью библиотек networkx и matplotlib

Для визуализации: plt.show()

2. Определите, является ли граф связным.

3. Найдите кратчайший путь между двумя вершинами в взвешенном графе.

4. Дан взвешенный граф, представляющий города и расстояния между ними. Нужно найти кратчайший маршрут, который проходит через все вершины ровно один раз и возвращается в начальную точку (задача коммивояжёра).

Попробуйте визуализировать через matplotlib

Визуализация:

import matplotlib.pyplot as plt

# Рисуем граф

pos = nx.spring_layout(G) # Расположение узлов

nx.draw(G, pos, with_labels=True, node_color="lightblue", node_size=2000, edge_color="gray")

# Подписываем веса рёбер

labels = nx.get_edge_attributes(G, "weight")

nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

# Выделяем оптимальный маршрут

edges_in_path = [(tsp_path[i], tsp_path[i+1]) for i in range(len(tsp_path) - 1)]

nx.draw_networkx_edges(G, pos, edgelist=edges_in_path, edge_color="red", width=2)

plt.show()