Embedded Files
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <unordered_map>
#include <fstream>
#include <sstream>
using namespace std;
class Graph {
public:
// Метод для чтения графа из файла
void readGraph(std::string fileName) {
ifstream inputFile(fileName); // Открытие файла для чтения
char typeInput;
string line;
int number;
inputFile >> typeInput; // Чтение типа представления графа (C - матрица, L - список, E - ребра)
// Устанавливаем тип представления графа в зависимости от символа
if (typeInput == 'C') {
typeRepr = 0; // Матрица смежности
} else if (typeInput == 'L') {
typeRepr = 1; // Список смежности
} else if (typeInput == 'E') {
typeRepr = 2; // Список рёбер
}
inputFile >> cntV; // Чтение количества вершин
if (typeRepr == 2) {
inputFile >> cntE; // Чтение количества рёбер, если представление - список рёбер
}
inputFile >> isOriented; // Чтение информации, ориентирован ли граф
inputFile >> isWeighted; // Чтение информации, взвешенный ли граф
// Если граф представлен матрицей смежности
if (typeRepr == 0) {
for (auto& row : adjacencyMatrix) { row.clear(); } // Очистка предыдущих данных
adjacencyMatrix.clear(); // Очистка самой матрицы
for (int i = 0; i < cntV; i++) {
adjacencyMatrix.push_back(vector<int>(cntV, 0)); // Инициализация новой матрицы с нулями
}
for (int i = 0; i < cntV; i++) {
for (int j = 0; j < cntV; j++) {
inputFile >> number; // Чтение значений в матрицу
if (number != 0) { cntE++; } // Увеличиваем количество рёбер, если вес ребра не 0
adjacencyMatrix[i][j] = number;
}
}
}
// Если граф представлен списком смежности
else if (typeRepr == 1) {
for (auto& s : adjVerList) { s.clear(); } // Очистка предыдущих данных
adjVerList.clear(); // Очистка списка
vector<int> numbers;
getline(inputFile, line); // Чтение пустой строки, чтобы перейти к следующей
for (int i = 0; i < cntV; i++) { adjVerList.emplace_back(); } // Инициализация пустых списков для каждой вершины
for (int i = 0; i < cntV; i++) {
numbers.clear();
getline(inputFile, line); // Чтение строки с соседними вершинами для каждой вершины
istringstream iss(line); // Используем istringstream для обработки строки
while (iss >> number) { // Разбиваем строку на числа (соседей)
numbers.push_back(number);
}
// Если граф невзвешенный, то добавляем рёбра с весом 1
if (!isWeighted) {
for (int j : numbers) {
adjVerList[i].insert(make_pair(numbers[j] - 1, 1)); // Вставляем соседей
cntE++; // Увеличиваем количество рёбер
}
}
// Если граф взвешенный
else {
for (int j = 0; j < numbers.size(); j += 2) {
adjVerList[i].insert(make_pair(numbers[j] - 1, numbers[j + 1])); // Вставляем пары соседей и их веса
cntE++; // Увеличиваем количество рёбер
}
}
}
cout << endl << cntE << endl; // Выводим количество рёбер
}
// Если граф представлен списком рёбер
else if (typeRepr == 2) {
int u, v;
edgeList.clear(); // Очистка списка рёбер
for (int i = 0; i < cntE; i++) {
inputFile >> u >> v; // Чтение ребер
u--; v--; // Индексация с 0
if (isWeighted) {
inputFile >> number; // Если граф взвешенный, читаем вес рёбер
} else {
number = 1; // Если граф невзвешенный, присваиваем вес 1
}
edgeList.push_back(make_tuple(u, v, number)); // Добавляем ребро в список рёбер
}
for (auto& i : edgeList) {
cout << get<0>(i) << " " << get<1>(i) << " " << get<2>(i) << endl; // Выводим ребра
break; // Прерываем цикл после первого ребра
}
}
}
// Метод для добавления ребра в граф
// from и to от 1 до количества вершин
void addEdge(int from, int to, int weight = 1) {
from--; // Индексация с 0
to--; // Индексация с 0
cntE++; // Увеличиваем количество рёбер
if (typeRepr == 0) {
adjacencyMatrix[from][to] = weight; // Для матрицы смежности
if (!isOriented) {
adjacencyMatrix[to][from] = weight; // Если граф неориентированный
}
} else if (typeRepr == 1) {
adjVerList[from].insert(make_pair(to, weight)); // Для списка смежности
if (!isOriented) {
adjVerList[to].insert(make_pair(from, weight)); // Если граф неориентированный
}
} else if (typeRepr == 2) {
edgeList.push_back(make_tuple(from, to, weight)); // Для списка рёбер
}
}
// Метод для удаления ребра из графа
// from и to от 1 до количества вершин
void removeEdge(int from, int to) {
from--; to--; // Индексация с 0
if (typeRepr == 0) {
adjacencyMatrix[from][to] = 0; // Для матрицы смежности
if (!isOriented) {
adjacencyMatrix[to][from] = 0; // Если граф неориентированный
}
} else if (typeRepr == 1) {
for (const auto& pair : adjVerList[from]) {
if (pair.first == to) {
adjVerList[from].erase(pair); // Удаление ребра из списка смежности
break;
}
}
if (!isOriented) {
for (const auto& pair : adjVerList[to]) {
if (pair.first == from) {
adjVerList[to].erase(pair); // Если граф неориентированный
break;
}
}
}
} else if (typeRepr == 2) {
pair<int, int> eraseInd;
eraseInd.first = -1; eraseInd.second = -1;
for (int i = 0; i < cntE; i++) {
if (get<0>(edgeList[i]) == from && get<1>(edgeList[i]) == to) {
eraseInd.first = i;
}
}
if (eraseInd.first != -1) {
edgeList.erase(edgeList.begin() + eraseInd.first); // Удаление ребра из списка рёбер
}
}
cntE--; // Уменьшаем количество рёбер
}
// Метод для изменения веса ребра
// from и to от 1 до количества вершин
int changeEdge(int from, int to, int newWeight) {
from--; to--; // Индексация с 0
int oldWeight;
pair<int, int> edge;
if (typeRepr == 0) {
oldWeight = adjacencyMatrix[from][to]; // Для матрицы смежности
adjacencyMatrix[from][to] = newWeight;
if (!isOriented) {
adjacencyMatrix[to][from] = newWeight; // Если граф неориентированный
}
} else if (typeRepr == 1) {
for (const auto& pair : adjVerList[from]) {
if (pair.first == to) {
oldWeight = pair.second;
edge.first = pair.first;
edge.second = newWeight;
adjVerList[from].erase(pair); // Для списка смежности
break;
}
}
adjVerList[from].insert(edge);
if (!isOriented) {
for (const auto& pair : adjVerList[to]) {
if (pair.first == from) {
edge.first = pair.first;
adjVerList[to].erase(pair);
break;
}
}
if (edge.first != to) { adjVerList[to].insert(edge); } // Если граф неориентированный
}
} else if (typeRepr == 2) {
for (int i = 0; i < cntE; i++) {
if (get<0>(edgeList[i]) == from && get<1>(edgeList[i]) == to) {
oldWeight = get<2>(edgeList[i]);
edgeList[i] = make_tuple(get<0>(edgeList[i]), get<1>(edgeList[i]), newWeight); // Для списка рёбер
break;
}
}
}
return oldWeight; // Возвращаем старый вес
}
// Преобразование графа в список смежности
void transformToAdjList() {
for (auto& s : adjVerList) { s.clear(); }
adjVerList.clear();
for (int i = 0; i < cntV; i++) { adjVerList.emplace_back(); }
if (typeRepr == 0) {
for (int i = 0; i < cntV; i++) {
for (int j = 0; j < cntV; j++) {
if (adjacencyMatrix[i][j] == 0) { continue; }
adjVerList[i].insert(make_pair(j, adjacencyMatrix[i][j])); // Переводим в список смежности
}
}
for (auto& row : adjacencyMatrix) { row.clear(); }
adjacencyMatrix.clear();
} else if (typeRepr == 2) {
for (int i = 0; i < cntE; i++) {
adjVerList[get<0>(edgeList[i])].insert(make_pair(get<1>(edgeList[i]), get<2>(edgeList[i]))); // Из рёбер в список смежности
if (!isOriented) {
adjVerList[get<1>(edgeList[i])].insert(make_pair(get<0>(edgeList[i]), get<2>(edgeList[i]))); // Если граф неориентированный
}
}
edgeList.clear();
}
typeRepr = 1; // Меняем тип представления на список смежности
}
// Преобразование графа в матрицу смежности
void transformToAdjMatrix() {
for (auto& row : adjacencyMatrix) { row.clear(); }
adjacencyMatrix.clear();
for (int i = 0; i < cntV; i++) {
adjacencyMatrix.push_back(vector<int>(cntV, 0)); // Инициализация пустой матрицы
}
if (typeRepr == 1) {
for (size_t i = 0; i < adjVerList.size(); ++i) {
for (const auto& edge : adjVerList[i]) {
adjacencyMatrix[i][edge.first] = edge.second; // Переводим в матрицу смежности
}
}
for (auto& s : adjVerList) {
s.clear();
}
adjVerList.clear();
} else if (typeRepr == 2) {
for (int i = 0; i < cntE; i++) {
adjacencyMatrix[get<0>(edgeList[i])][get<1>(edgeList[i])] = get<2>(edgeList[i]); // Из рёбер в матрицу смежности
if (!isOriented) {
adjacencyMatrix[get<1>(edgeList[i])][get<0>(edgeList[i])] = get<2>(edgeList[i]); // Если граф неориентированный
}
}
edgeList.clear();
}
typeRepr = 0; // Меняем тип представления на матрицу смежности
}
// Преобразование графа в список рёбер
void transformToListOfEdges() {
edgeList.clear();
if (typeRepr == 0) {
for (int i = 0; i < cntV; i++) {
for (int j = i + 1; j < cntV; j++) {
if (adjacencyMatrix[i][j] == 0) { continue; }
edgeList.push_back(make_tuple(i, j, adjacencyMatrix[i][j])); // Переводим в список рёбер
if (adjacencyMatrix[i][j] != adjacencyMatrix[j][i]) {
edgeList.push_back(make_tuple(j, i, adjacencyMatrix[j][i])); // Если граф неориентированный
}
}
}
for (auto& row : adjacencyMatrix) { row.clear(); }
adjacencyMatrix.clear();
} else if (typeRepr == 1) {
pair<int, int> el;
int j;
vector<vector<bool>> flags;
for (int i = 0; i < cntV; i++) { flags.push_back(vector<bool>(adjVerList[i].size(), false)); }
for (int i = 0; i < cntV; i++) {
j = -1;
for (const auto& edge : adjVerList[i]) {
j++;
if (flags[i][j]) { continue; }
edgeList.push_back(make_tuple(i, edge.first, edge.second)); // Добавляем ребро
flags[i][j] = true;
auto reverseEdge = adjVerList[edge.first].find(make_pair(i, edge.second));
if (reverseEdge != adjVerList[edge.first].end()) {
flags[edge.first][distance(adjVerList[edge.first].begin(), reverseEdge)] = true;
}
}
}
for (auto& s : adjVerList) { s.clear(); }
adjVerList.clear();
}
typeRepr = 2; // Меняем тип представления на список рёбер
}
// Метод для записи графа в файл
void writeGraph(string fileName) {
ofstream outFile(fileName); // Открытие файла для записи
if (!outFile) {
cout << "Ошибка открытия файла для записи." << endl; // Если файл не открылся, выводим ошибку
return;
}
if (typeRepr == 0) { outFile << "C "; } // Если матрица смежности
else if (typeRepr == 1) { outFile << "L "; } // Если список смежности
else if (typeRepr == 2) { outFile << "E "; } // Если список рёбер
outFile << cntV; // Записываем количество вершин
if (typeRepr == 2) { outFile << " " << cntE; } // Если список рёбер, записываем количество рёбер
outFile << endl;
outFile << (int)isOriented << " " << (int)isWeighted << endl; // Записываем ориентацию и взвешенность графа
// Запись графа в файл для разных типов представления
if (typeRepr == 0) {
for (int i = 0; i < cntV; i++) {
for (int j = 0; j < cntV; j++) {
outFile << adjacencyMatrix[j][i] << " "; // Запись матрицы смежности
}
outFile << endl;
}
} else if (typeRepr == 1) {
for (int i = 0; i < cntV; i++) {
for (const auto& edge : adjVerList[i]) {
outFile << edge.first << " "; // Запись списка смежности
if (isWeighted) { outFile << edge.second << " "; }
}
outFile << endl;
}
} else if (typeRepr == 2) {
for (int i = 0; i < cntE; i++) {
outFile << get<0>(edgeList[i]) + 1 << " " << get<1>(edgeList[i]) + 1; // Запись списка рёбер
if (isWeighted) { outFile << " " << get<2>(edgeList[i]); }
outFile << endl;
}
}
}
public:
// Матрица смежности
vector<vector<int>> adjacencyMatrix;
// Список смежных вершин
vector<set<pair<int, int>>> adjVerList;
// Список рёбер
vector<tuple<int, int, int>> edgeList;
bool isOriented; // Ориентирован ли граф
bool isWeighted; // Взвешенный ли граф
int typeRepr = 0; // Тип представления графа: 0 - матрица смежности, 1 - список смежности, 2 - список рёбер
int cntV = 0; // Количество вершин в графе
int cntE = 0; // Количество рёбер в графе
};
// Основная функция
int main() {
Graph g;
g.readGraph("input_1e3_1e5.txt"); // Чтение графа из файла
g.transformToAdjMatrix(); // Преобразование графа в матрицу смежности
g.transformToAdjList(); // Преобразование графа в список смежности
g.transformToListOfEdges(); // Преобразование графа в список рёбер
g.writeGraph("output.txt"); // Запись графа в файл
return 0; // Завершение программы
}
DSU (Система непересекающихся множеств):
Позволяет объединять вершины в множества
Родитель (parent) хранит представителя множества
Ранг (rank) помогает уравновешенно сливать множества
findSet(x) находит корень множества x
unite(x,y) объединяет два множества
Graph (класс для хранения и работы с графом):
Имеет поля:
rep (тип хранения): матрица смежности, список смежности, список рёбер
isOriented (ориентированный граф или нет)
isWeighted (взвешенный граф или нет)
N (число вершин)
M (число рёбер)
Внутренние структуры хранения: adjMatrix, adjListWeighted, edgeListWeighted и т.д.
readGraph(filename):
Читает из файла тип представления (C – матрица, L – список смежности, E – список рёбер)
Считывает данные о графе
Заполняет соответствующую структуру (adjMatrix, adjListWeighted, edgeListWeighted)
writeGraph(filename):
Записывает данные графа в файл
Сначала выводит, какой тип представления используется (C, L или E)
Затем сохраняет структуру (матрица, список смежности или рёбер)
addEdge(from, to, weight):
Добавляет ребро с весом weight
Учитывает, где хранится граф (матрица, список смежности или рёбер)
removeEdge(from, to):
Удаляет ребро между вершинами from и to
Учитывает тип текущего хранения
changeEdge(from, to, newWeight):
Меняет вес уже существующего ребра
Возвращает старый вес
transformToAdjMatrix(), transformToAdjList(), transformToEdgeList():
Меняют текущее представление графа на нужный формат
Например, из списка рёбер в матрицу смежности
Или из матрицы смежности в список смежности
Алгоритмы для построения остовных деревьев:
getSpanningTreePrim():
Применяет алгоритм Прима
Изначально выбирает одну вершину
Каждый шаг добавляет ребро минимального веса, которое ведёт к новой вершине
Возвращает новый граф mst как остовное дерево
getSpanningTreeKruskal():
Применяет алгоритм Крускала
Сортирует все рёбра по возрастанию веса (использует структуру priority_queue)
DSU (Система непересекающихся множеств) проверяет, не образуется ли цикл
Постепенно добавляет самые лёгкие рёбра, пока не наберётся N-1 ребро
getSpanningTreeBoruvka():
Упрощённая реализация алгоритма Борувки
Пошагово добавляет рёбра минимального веса к новому остову
Включает новую вершину, затем повторяет, пока все вершины не будут включены
main():
Создаёт объект Graph g
Считывает данные из файла input.txt
Вызывает getSpanningTreeBoruvka() (примеры с Примом и Крускалом закомментированы)
Преобразует результат в список рёбер (transformToEdgeList())
Записывает результат в файл output.txt
class DSU {
private:
vector<int> parent; // Родительский элемент для каждого элемента
vector<int> rank; // Ранг множества (глубина дерева)
public:
// Создает n множеств для элементов 0..n-1
explicit DSU(int n) : parent(n), rank(n, 0) {
for(int i = 0; i < n; i++){
parent[i] = i;
}
}
// Находит корень с путевой компрессией
int findSet(int x) {
if(x == parent[x]) return x;
return parent[x] = findSet(parent[x]);
}
// Объединяет два множества
void unite(int x, int y) {
x = findSet(x);
y = findSet(y);
if(x == y) return;
if(rank[x] < rank[y]) parent[x] = y;
else {
parent[y] = x;
if(rank[x] == rank[y]) rank[x]++;
}
}
};
class Graph {
private:
// Способ хранения графа: матрица смежности, список смежности, список рёбер
enum class Representation { AdjacencyMatrix, AdjacencyList, EdgeList };
Representation rep; // Текущее представление
bool isOriented; // Признак ориентированности
bool isWeighted; // Признак взвешенности
int N; // Количество вершин
int M; // Количество рёбер
// Внутренние структуры для хранения графа:
// - Матрица смежности
vector<vector<int>> adjMatrix;
// - Списки смежности (невзвешенные и взвешенные)
vector<set<int>> adjListNotWeighted;
vector<map<int,int>> adjListWeighted;
// - Списки рёбер (невзвешенные и взвешенные)
set<pair<int,int>> edgeListNotWeighted;
map<pair<int,int>,int> edgeListWeighted;
public:
// ...
};
void readGraph(const string &filename) {
// Открываем файл
ifstream fin(filename);
if(!fin.is_open()) {
throw runtime_error("Не удается открыть входной файл.");
}
// Считываем тип представления: C (матрица), L (список смежности), E (список рёбер)
char c;
fin >> c;
if(c == 'C') {
rep = Representation::AdjacencyMatrix;
} else if(c == 'L') {
rep = Representation::AdjacencyList;
} else {
rep = Representation::EdgeList;
}
// Далее вызываем вспомогательную функцию для заполнения структуры
readFromStream(fin);
fin.close();
}
// Считывает содержимое из потока и заполняет нужные структуры
void readFromStream(ifstream &fin) {
if(!fin.is_open()) {
throw runtime_error("Файл не удалось открыть.");
}
int flag;
// Сначала считываем количество вершин
fin >> N;
// Если представление — список рёбер, считываем и количество рёбер
if(rep == Representation::EdgeList) {
fin >> M;
}
// Определяем, ориентированный ли граф
fin >> flag;
isOriented = (flag != 0);
// Определяем, взвешенный ли граф
fin >> flag;
isWeighted = (flag != 0);
// Если представление — матрица смежности (AdjacencyMatrix)
if(rep == Representation::AdjacencyMatrix) {
adjMatrix.resize(N, vector<int>(N, 0));
M = 0; // будем считать рёбра, где в матрице не ноль
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int val = 0;
fin >> val;
adjMatrix[i][j] = val;
if(val != 0) {
M++;
}
}
}
// Если граф неориентированный, мы посчитали каждое ребро дважды, но обычно
// в коде для матрицы смежности не удваивают M. При необходимости можно скорректировать.
}
// Если представление — список смежности (AdjacencyList)
else if(rep == Representation::AdjacencyList) {
// Взвешенный список смежности
adjListWeighted.resize(N);
// Пропускаем перевод строки перед построчным чтением
fin.ignore(numeric_limits<streamsize>::max(), '\n');
for(int i = 0; i < N; i++) {
string line;
if(!getline(fin, line)) {
break;
}
istringstream row(line);
int v, w;
// В каждой строке идут пары (вершина, вес)
while(row >> v && row >> w) {
adjListWeighted[i].insert(make_pair(v, w));
}
}
// M можно вычислить, проходя по всем спискам, при необходимости
}
// Если представление — список рёбер (EdgeList)
else {
// Уже считали M, теперь считываем каждое ребро
for(int i = 0; i < M; i++) {
int from, to, weight;
fin >> from >> to >> weight;
// Если граф неориентированный, упорядочим вершины пары
if(!isOriented && from > to) {
swap(from, to);
}
edgeListWeighted[make_pair(from, to)] = weight;
}
}
}
void writeGraph(const string &filename) {
// Вызов вспомогательной функции записи в файл
writeToFile(filename);
}
void writeToFile(const string &filename) {
ofstream fout(filename);
if(!fout.is_open()) {
throw runtime_error("Не удается открыть выходной файл.");
}
// Определяем, какой тип представления выводить: C, L или E
if(rep == Representation::AdjacencyMatrix) {
fout << "C ";
}
else if(rep == Representation::AdjacencyList) {
fout << "L ";
}
else {
fout << "E ";
}
// Выводим количество вершин
fout << N;
// Для списка рёбер дополнительно выводим количество рёбер
if(rep == Representation::EdgeList) {
fout << " " << M;
}
fout << endl;
// Выводим признак ориентированности и взвешенности
fout << (int)isOriented << " " << (int)isWeighted << endl;
// Если матрица смежности
if(rep == Representation::AdjacencyMatrix) {
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
fout << adjMatrix[i][j];
if(j + 1 < N) fout << " ";
}
fout << endl;
}
}
// Если список смежности
else if(rep == Representation::AdjacencyList) {
for(int i = 0; i < N; i++){
bool firstItem = true;
for(const auto &p : adjListWeighted[i]) {
if(!firstItem) {
fout << " ";
}
fout << p.first << " " << p.second;
firstItem = false;
}
fout << endl;
}
}
// Если список рёбер
else {
for(const auto &edge : edgeListWeighted) {
fout << edge.first.first << " "
<< edge.first.second << " "
<< edge.second << endl;
}
}
fout.close();
}
void addEdge(int from, int to, int weight) {
// В зависимости от текущего представления выбираем нужную процедуру
if(rep == Representation::AdjacencyMatrix) {
addEdgeAdjMatrix(from, to, weight);
} else if(rep == Representation::AdjacencyList) {
addEdgeAdjList(from, to, weight);
} else {
addEdgeListOfEdges(from, to, weight);
}
M++;
}
void removeEdge(int from, int to) {
// Удаляем ребро в зависимости от представления
if(rep == Representation::AdjacencyMatrix) {
removeEdgeAdjMatrix(from, to);
} else if(rep == Representation::AdjacencyList) {
removeEdgeAdjList(from, to);
} else {
removeEdgeListOfEdges(from, to);
}
if(M > 0) M--;
}
int changeEdge(int from, int to, int newWeight) {
// Меняем вес ребра и возвращаем его старое значение
int oldWeight = 0;
// Проверяем текущее представление
if(rep == Representation::AdjacencyMatrix) {
oldWeight = getWeightAdjMatrix(from, to);
addEdgeAdjMatrix(from, to, newWeight);
}
else if(rep == Representation::AdjacencyList) {
oldWeight = getWeightAdjList(from, to);
removeEdgeAdjList(from, to);
addEdgeAdjList(from, to, newWeight);
}
else {
oldWeight = getWeightListOfEdges(from, to);
removeEdgeListOfEdges(from, to);
addEdgeListOfEdges(from, to, newWeight);
}
return oldWeight;
}
// Преобразует представление к матрице смежности
void transformToAdjMatrix() {
if(rep == Representation::AdjacencyList) {
transformAdjListToMatrix();
} else if(rep == Representation::EdgeList) {
transformListOfEdgesToMatrix();
}
rep = Representation::AdjacencyMatrix;
}
// Преобразует представление к списку смежности
void transformToAdjList() {
if(rep == Representation::AdjacencyMatrix) {
transformMatrixToAdjList();
} else if(rep == Representation::EdgeList) {
transformListOfEdgesToAdjList();
}
rep = Representation::AdjacencyList;
}
// Преобразует представление к списку рёбер
void transformToEdgeList() {
if(rep == Representation::AdjacencyMatrix) {
transformMatrixToListOfEdges();
} else if(rep == Representation::AdjacencyList) {
transformAdjListToListOfEdges();
}
rep = Representation::EdgeList;
}
// Построение остовного дерева алгоритмом Прима
Graph getSpanningTreePrim() {
// Преобразуем к списку смежности, если нужно
transformToAdjList();
// Создаем пустое дерево с таким же количеством вершин
Graph mst(N, /*weighted=*/true, isOriented);
set<int> picked; // уже добавленные вершины
set<int> unpicked; // оставшиеся вершины
// Изначально все вершины не добавлены
for(int i = 1; i <= N; i++){
unpicked.insert(i);
}
// Берем первую вершину из непокрытых
int last = *unpicked.begin();
picked.insert(last);
unpicked.erase(last);
// Очередь с приоритетом (ребра отсортированы по весу: (вес, из, в))
priority_queue<
tuple<int,int,int>,
vector<tuple<int,int,int>>,
greater<tuple<int,int,int>>
> edgesQueue;
// Пока есть непокрытые вершины
while(!unpicked.empty()){
// Добавляем все исходящие из last рёбра, ведущие к непокрытым вершинам
for(const auto &pr : adjListWeighted[last - 1]) {
if(picked.find(pr.first) == picked.end()) {
edgesQueue.push(make_tuple(pr.second, last, pr.first));
}
}
// Ищем ребро с минимальным весом, которое ведёт к новой вершине
while(!edgesQueue.empty()) {
auto edge = edgesQueue.top();
edgesQueue.pop();
int w = get<0>(edge);
int from = get<1>(edge);
int to = get<2>(edge);
// Если вершина ещё не покрыта, добавляем ребро в остов
if(picked.find(to) == picked.end()) {
mst.addEdge(from, to, w);
last = to;
break;
}
}
picked.insert(last);
unpicked.erase(last);
}
return mst;
}
// Построение остовного дерева алгоритмом Крускала
Graph getSpanningTreeKruskal() {
// Получаем все рёбра в структуру (min-heap) по возрастанию веса
edges_priority_queue wEdges = getWeightedEdgesQueue();
// Пустой MST с таким же количеством вершин
Graph mst(N, /*weighted=*/true, isOriented);
// DSU для отслеживания связных компонент
DSU dsu(N);
int edgesUsed = 0;
// Пока не набрали (N-1) рёбер и куча не пуста
while(!wEdges.empty() && edgesUsed < N - 1) {
auto edge = wEdges.top();
wEdges.pop();
int w = get<0>(edge);
int from = get<1>(edge);
int to = get<2>(edge);
// Проверяем, не в одной ли они компоненте
if(dsu.findSet(from - 1) != dsu.findSet(to - 1)) {
// Объединяем компоненты и добавляем ребро в остов
dsu.unite(from - 1, to - 1);
mst.addEdge(from, to, w);
edgesUsed++;
}
}
return mst;
}
// Упрощенная реализация алгоритма Борувки
Graph getSpanningTreeBoruvka() {
// Преобразуем к списку смежности при необходимости
transformToAdjList();
// Создаем пустое остовное дерево
Graph mst(N, /*weighted=*/true, isOriented);
set<int> picked;
set<int> unpicked;
for(int i = 1; i <= N; i++){
unpicked.insert(i);
}
// Начинаем с первой вершины
int last = *unpicked.begin();
picked.insert(last);
unpicked.erase(last);
// Очередь рёбер по возрастанию веса
priority_queue<
tuple<int,int,int>,
vector<tuple<int,int,int>>,
greater<tuple<int,int,int>>
> edgesQueue;
// Пока есть непокрытые вершины
while(!unpicked.empty()){
// Добавляем рёбра, исходящие из последней добавленной вершины
for(const auto &pr : adjListWeighted[last - 1]) {
if(picked.find(pr.first) == picked.end()) {
edgesQueue.push(make_tuple(pr.second, last, pr.first));
}
}
// Ищем очередное минимальное ребро, ведущее к новой вершине
while(!edgesQueue.empty()) {
auto edge = edgesQueue.top();
edgesQueue.pop();
int w = get<0>(edge);
int from = get<1>(edge);
int to = get<2>(edge);
if(picked.find(to) == picked.end()) {
// Добавляем ребро и переходим на новую вершину
mst.addEdge(from, to, w);
last = to;
break;
}
}
picked.insert(last);
unpicked.erase(last);
}
return mst;
}
int main() {
try {
// Создаём объект графа
Graph g;
// Считываем данные из файла input.txt
g.readGraph("input.txt");
// Примеры:
// Graph newG = g.getSpanningTreePrim();
// Graph newG = g.getSpanningTreeKruskal();
Graph newG = g.getSpanningTreeBoruvka();
// Преобразуем полученный остов в список рёбер и записываем в файл
newG.transformToEdgeList();
newG.writeGraph("output.txt");
}
catch(const exception &e) {
cerr << "Ошибка: " << e.what() << endl;
}
return 0;
}
Page updated
Google Sites
Report abuse