0

Нахождение минимального остовного дерева графа по алгоритму Крускала

#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 и т.д. Но мы же не знаем где находятся вершины нашего минимального остовного дерева и как быть в такой ситуации. Допустим даже если мы не будем делать автоматический ввод нашего минимального остовного дерева в программу обхода вершин дерева, а оставим эту работу пользователю, то программа которая находит минимальное остовное дерево тоже не знает где они находятся чтобы сказать пользователю. Помогите пожалуйста.

1 ответ 1

0

Код для дерева не подходит, например, потому что остовное дерево не является бинарным деревом - у каждого узла может быть любое количество детей, и у него нет выделенного корня.

Поэтому можно выполнить обход из любой вершины - примените обычный BFS для графов.

2
  • Спасибо, BFS это в ширину да? А можно в глубину?
    – vadyanysh
    Commented 28 окт. 2022 в 14:16
  • Да, можно. В ширину даёт, возможно, более логичную группировку вершин, но принцип тот же
    – MBo
    Commented 28 окт. 2022 в 14:41

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.