KruskalHamiltonPrimal 0.0.1

Библиотека для работы с графами и алгоритмами, включая алгоритмы Крускала, Гамильтона и минимального остовного дерева

Минимальное Остовное Дерево и Гамильтонов Цикл

Этот проект реализует алгоритмы для нахождения минимального остовного дерева (MST) Рё Гамильтонова цикла РІ графах. РћРЅ включает РІ себя три основных класса: Kruskal, Hamilton Рё Primal_min, каждый РёР· которых предоставляет различные методы для работы СЃ графами.

Установка

Для работы с проектом необходимо установить следующие библиотеки:

pip install networkx matplotlib

Описание классов

1. Kruskal

Класс Kruskal реализует алгоритм Краскала для нахождения минимального остовного дерева.

Конструктор

Kruskal(points, edges)

• points: РЎРїРёСЃРѕРє координат вершин графа.
• edges: РЎРїРёСЃРѕРє рёбер графа, РіРґРµ каждое ребро представлено РІ РІРёРґРµ кортежа (u, v, weight).

Методы

• draw_only(k): Отображает граф Рё его рёбра.
• view(min_edges, max_edges, k): Отображает граф СЃ минимальным Рё максимальным покрывающим деревом.
• kruskals_algorithm(edges): Реализует алгоритм Краскала для нахождения MST.
• sort_edges_min(): Сортирует рёбра РїРѕ возрастанию веса.
• sort_edges_max(): Сортирует рёбра РїРѕ убыванию веса.
• result_weight(edges): Вычисляет Рё выводит суммарный вес дерева.

2. Hamilton

Класс Hamilton реализует алгоритм для нахождения Гамильтонова цикла.

Конструктор

Hamilton(points, edges)

• points: РЎРїРёСЃРѕРє координат вершин графа.
• edges: РЎРїРёСЃРѕРє рёбер графа РІ РІРёРґРµ пар индексов вершин.

Методы

• cycle_exist(cycle): Проверяет наличие Гамильтонова цикла Рё выводит его.
• draw(): Визуализирует граф.
• aviable(): Выводит доступные вершины.
• hamiltonian_cycle(start): Находит Гамильтонов цикл, начиная СЃ заданной вершины.
• draw_graph(path=None): Отображает граф СЃ выделенным Гамильтоновым циклом.

3. Primal_min

Класс Primal_min реализует алгоритм РџСЂРёРјР° для нахождения минимального остовного дерева.

Конструктор

Primal_min(graph)

• graph: Граф РІ РІРёРґРµ словаря, РіРґРµ ключи — это вершины, Р° значения — СЃРїРёСЃРєРё рёбер СЃ весами.

Методы

• run(begin): Запускает алгоритм РџСЂРёРјР°, начиная СЃ заданной вершины.
• min_tree(): Выводит минимальное покрывающее дерево Рё его суммарный вес.

Пример использования

# Пример создания графа и нахождения минимального остовного дерева
points = [(0, 0), (1, 1), (2, 0), (1, -1)]
edges = [(0, 1, 1.5), (0, 2, 1.0), (1, 3, 2.0), (2, 3, 1.0)]

kruskal = Kruskal(points, edges)
sorted_edges = kruskal.sort_edges_min()
mst = kruskal.alg_Kraskala(sorted_edges)
kruskal.view(mst, sorted_edges, 3)

# Пример нахождения Гамильтонова цикла
hamilton = Hamilton(points, edges)
cycle = hamilton.hamiltonian_cycle(0)
hamilton.cycle_exist(cycle)
hamilton.draw_graph(cycle)

Лицензия

Этот проект лицензирован под MIT License. Пожалуйста, ознакомьтесь с файлом LICENSE для получения дополнительной информации.