Skip to content

Latest commit

 

History

History
52 lines (34 loc) · 2.42 KB

README.md

File metadata and controls

52 lines (34 loc) · 2.42 KB

Лабораторная работа №1 — способы представления графа

Цель работы — представить один ориентированный взвешенный граф тремя способами и сравнить затраты памяти и время выполнения типовых операций.

Что реализовано

Граф из 12 вершин с названиями месяцев хранится в виде:

  1. матрицы смежности;
  2. списка рёбер;
  3. массива записей с предками, потомками и весами входящих и исходящих рёбер.

Для каждого представления реализованы одинаковые операции:

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

Программа также выводит размеры структур данных через 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.