# Теория конечных графов: Лабораторные работы 1-5

Проект представляет собой библиотеку на C++17 для работы с графами, реализующую фундаментальные алгоритмы.

## Содержание
1. [ЛР1: Структуры данных](#лр1)
2. [ЛР2: MST](#лр2)
3. [ЛР3: Эйлеровы циклы/пути](#лр3)
4. [ЛР4: Паросочетания](#лр4)
5. [ЛР5: Потоки в сетях](#лр5)

<a name="лр1"></a>
## ЛР1: Разработка класса Graph
Реализованы три представления графа:
- **C**: Матрица смежности
- **L**: Списки смежности (`std::set`)
- **E**: Список рёбер

<a name="лр2"></a>
## ЛР2: Остовное дерево минимального веса (MST)
- **Прим** (на базе `std::priority_queue`)
- **Краскал** (DSU)
- **Борувка** (DSU)

<a name="лр3"></a>
## ЛР3: Эйлеровы пути и циклы
- **Алгоритм Флери** (поиск мостов)
- **Алгоритм Иерхольцера** (эффективный O(M) обход)

<a name="лр4"></a>
## ЛР4: Паросочетания
- **Алгоритм Куна** для поиска максимального паросочетания в двудольных графах.

<a name="лр5"></a>
## ЛР5: Потоки в сетях
- **Эдмондс-Карп** (BFS)
- **Диниц** (слоистая сеть)

## Сборка и запуск
### Сборка:
```bash
g++ -std=c++17 -O2 *.cpp -o graph
```
### Запуск:
```bash
./graph [input_file] [output_file]
```

## Формат входных данных
- Первая строка: Тип (C, L, E) и количество вершин (N).
- Вторая строка: Ориентированность (0/1) и Взвешенность (0/1).
- Далее данные согласно выбранному формату.