Нахождение минимального остовного дерева графа по алгоритму Крускала
#include <iostream>
#include <vector>
using namespace std;
// Структура для представления графа
struct Graph {
// V - вершины; E - ребра графа
int V, E;
/*
* Делаю вектор ребер, который состоит из всех ребер в графе,
* каждый элемент вектора содержит 3 параметра:
* источник, место назначения, вес ребра между источником и местом назначения
*
* Первый элемент соответствует весу ребра,
* второй элемент является парой и содержит две вершины ребра
*/
vector<pair<int, pair<int, int>>> edges;
// Конструктор
Graph(int V, int E) {
this->V = V;
this->E = E;
}
// Функция для добавления ребер в вектор
// w - вес, u - источник, v - место назначения
void addEdge(int u, int v, int w) {
edges.push_back({w, {u, v}});
}
// Функция для нахождения минимального остовного дерева графа используя алгоритм Крускала
int kruskalMST();
};
// Структура для представления непересекающихся множеств
struct DisjointSets {
int *parent, *rnk;
int n;
// Конструктор
DisjointSets(int n) {
this->n = n;
parent = new int[n + 1];
rnk = new int[n + 1];
// Изначально, все вершины находятся в разных множествах, и имеют ранг 0
for (int i = 0; i <= n; i++) {
rnk[i] = 0;
// Каждый элемент является родителем самого себя
parent[i] = i;
}
}
// Представителем дерева будем считать его корень.
// Тогда для нахождения этого представителя достаточно
// подняться вверх по родительским ссылкам до тех пор, пока не наткнемся на корень
// Фактически переподвесим все эти вершины вместо длинной ветви непосредственно к корню.
int find(int u) {
// Если u не родитель самого себя
if (u != parent[u]) {
parent[u] = find(parent[u]);
}
return parent[u];
}
// Слияние
void merge(int x, int y) {
x = find(x);
y = find(y);
if (rnk[x] > rnk[y]) {
parent[y] = x;
} else { // Если rnk[x] <= rnk[y]
parent[x] = y;
}
if (rnk[x] == rnk[y])
rnk[y]++;
}
};
// Функция возвращает вес минимально остовного дерева
int Graph::kruskalMST() {
int mstWeight = 0;
// Использую встроенную функцию для сортировки ребер в порядке возрастания (не убывания)
sort(edges.begin(), edges.end());
// Создаю объект непересекающихся множеств
DisjointSets ds(V);
// Обьявляю итератор it
// Итерируюсь по всем уже отсортированным ребрам
vector<pair<int, pair<int, int>>>::iterator it;
for (it = edges.begin(); it != edges.end(); it++) {
// Обращаюсь ко второй паре, первому и второму элементу
int u = it->second.first;
int v = it->second.second;
// DisjointSets
int set_u = ds.find(u);
int set_v = ds.find(v);
// Проверяю если текущее ребро создает цикл или нет
// Цикл создается если u и v принадлежит одному и тому же множеству
if (set_u != set_v) {
// Текущее ребро будет в МОД, поэтому вывожу его на экран
cout << u << " - " << v << endl;
// Обновление веса МОД
mstWeight += it->first;
// Объединяю два множества
ds.merge(set_u, set_v);
}
}
return mstWeight;
}
int main() {
// Вершины считаются с нуля, ребра с единицы
int V = 8, E = 9;
Graph g(V, E);
// Первый аргумент - источник, второй - место назначения, третий - вес
g.addEdge(7, 8, 1);
g.addEdge(0, 1, 2);
g.addEdge(0, 6, 3);
g.addEdge(1, 3, 3);
g.addEdge(1, 5, 4);
g.addEdge(5, 8, 4);
g.addEdge(3, 4, 5);
g.addEdge(3, 5, 5); // образует цикл, вершины 3 и 5 находятся в одном множестве
g.addEdge(0, 2, 6);
g.addEdge(5, 7, 6);
// Конец, все вершины сливаются в одно множество
g.addEdge(2, 3, 7);
g.addEdge(0, 3, 8);
g.addEdge(4, 6, 8);
g.addEdge(1, 2, 9);
g.addEdge(4, 7, 9);
cout << "Ребра минимального остовного дерева " << endl;
int mstWeight = g.kruskalMST();
cout << "Вес минимального остовного дерева " << mstWeight << endl;
return 0;
}
Вывод программы:
Ребра минимального остовного дерева
7 - 8
0 - 1
0 - 6
1 - 3
1 - 5
5 - 8
3 - 4
0 - 2
Вес минимального остовного дерева 28
Обход вершин дерева
#include <iostream>
using namespace std;
struct Node {
int value;
struct Node *left;
struct Node *right;
};
// Функция для создания нового узла дерева
Node *newNode(int value) {
Node *temp = new Node;
temp->value = value;
temp->left = nullptr;
temp->right = nullptr;
return temp;
}
/*
* Обход дерева сверху вниз (в прямом порядке - Pre Order): A, B, C — префиксная форма.
* Прямой порядок обхода заключается в том, что корень дерева посещается раньше, чем его поддеревья.
*/
void printPreOrder(struct Node *node) {
if (node == nullptr) { // Пока не встретится пустой узел
return;
}
// Вывожу значение узла (корень дерева)
cout << node->value << " ";
// Рекурсия для левого поддерева
printPreOrder(node->left);
// Рекурсия для правого поддерева
printPreOrder(node->right);
}
/*
* Обход дерева слева направо (во внутреннем порядке - In Order): B, A, C — инфиксная форма.
* Внутренний порядок обхода заключается в том, что корень посещается после посещения одного из его поддеревьев.
*/
void printInOrder(struct Node *node) {
if (node == nullptr) {
return;
}
// Рекурсия для левого поддерева
printInOrder(node->left);
// Вывожу значение узла (корень дерева)
cout << node->value << " ";
// Рекурсия для правого поддерева
printInOrder(node->right);
}
/*
* Обход дерева в снизу вверх (в обратном порядке - Post Order): B, C, A — постфиксная форма.
* Обратный порядок обхода заключается в том, что корень дерева посещается после его поддеревьев.
*/
void printPostOrder(struct Node *node) {
if (node == nullptr) {
return;
}
// Рекурсия для левого поддерева
printPostOrder(node->left);
// Рекурсия для правого поддерева
printPostOrder(node->right);
// Вывожу значение узла (корень дерева)
cout << node->value << " ";
}
int main() {
struct Node *root = newNode(1);
// просто рандомные значения для теста (не относятся к минимальному остовному дереву)
root->left = newNode(2);
root->left->right = newNode(5);
root->left->left = newNode(4);
root->left->left->right = newNode(8);
root->right = newNode(3);
root->right->right = newNode(7);
root->right->left = newNode(6);
root->right->left->left = newNode(9);
root->right->left->right = newNode(10);
cout << "Обход в прямом порядке:" << endl;
printPreOrder(root);
cout << endl;
cout << "Обход во внутреннем порядке:" << endl;
printInOrder(root);
cout << endl;
cout << "Обход в обратном порядке" << endl;
printPostOrder(root);
cout << endl;
return 0;
}
Всем привет! Надо сделать программу которая бы обходила вершины минимального остовного дерева графа. Но в программе обхода вершин дерева мы записываем Node'ы, и указываем где они находятся, right->left, left->right и т.д. Но мы же не знаем где находятся вершины нашего минимального остовного дерева и как быть в такой ситуации. Допустим даже если мы не будем делать автоматический ввод нашего минимального остовного дерева в программу обхода вершин дерева, а оставим эту работу пользователю, то программа которая находит минимальное остовное дерево тоже не знает где они находятся чтобы сказать пользователю. Помогите пожалуйста.