Цель работы — представить один ориентированный взвешенный граф тремя способами и сравнить затраты памяти и время выполнения типовых операций.
Граф из 12 вершин с названиями месяцев хранится в виде:
- матрицы смежности;
- списка рёбер;
- массива записей с предками, потомками и весами входящих и исходящих рёбер.
Для каждого представления реализованы одинаковые операции:
- поиск соседей заданной вершины;
- проверка, образует ли последовательность вершин ориентированную цепь;
- поиск вершин, сумма весов инцидентных рёбер которых превышает порог;
- подсчёт количества рёбер.
Программа также выводит размеры структур данных через sys.getsizeof и измеряет среднее время выполнения операций на серии повторений.
python -m venv .venv
# Windows PowerShell
.venv\Scripts\Activate.ps1
pip install -r requirements.txt
python Lab1.pyПосле запуска в консоль выводятся все представления графа, их размеры и результаты замеров. Изображение графа сохраняется в файл graph.png.
Lab1.py— построение графа, операции над структурами, измерения и визуализация;requirements.txt— зафиксированные версии зависимостей;graph.png— результат визуализации.
- Python;
- NetworkX;
- Matplotlib;
- SciPy и NumPy как зависимости для работы с матрицей смежности;
- стандартные модули
sysиtime.
