Contrôle des Composantes Connexes avec l'Algorithme de Kruskal

L'algorithme de Kruskal est traditionnellement utilisé pour trouver l'arbre couvrant de poids minimum (ACPM) complet. Cependant, en modifiant la condition d'arrêt, il devient un outil puissant pour les problèmes de regroupement spatial (clustering). Si l'objectif est de partitionner un ensemble de points en exactement $k$ groupes de manière à maximiser la distance minimale entre ces groupes, il suffit d'exécuter Kruskal et de stopper le processus lorsqu'il reste $k$ composantes connexes. La dernière arête ajoutée avant d'atteindre $k-1$ composantes représente la distance minimale entre les clusters.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

struct Point { double x, y; };
struct Edge { 
    int u, v; 
    double weight; 
    bool operator<(const Edge& other) const { return weight < other.weight; }
};

class UnionFind {
    std::vector<int> parent;
    int components;
public:
    UnionFind(int n) : parent(n), components(n) {
        for(int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int i) { return parent[i] == i ? i : parent[i] = find(parent[i]); }
    bool unite(int i, int j) {
        int root_i = find(i), root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
            return true;
        }
        return false;
    }
    int get_components() const { return components; }
};

double solve_clustering(const std::vector<Point>& points, int k) {
    int n = points.size();
    std::vector<Edge> edges;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            double dx = points[i].x - points[j].x;
            double dy = points[i].y - points[j].y;
            edges.push_back({i, j, std::sqrt(dx * dx + dy * dy)});
        }
    }
    std::sort(edges.begin(), edges.end());
    
    UnionFind uf(n);
    double max_min_distance = 0.0;
    for (const auto& edge : edges) {
        if (uf.get_components() == k) break;
        if (uf.unite(edge.u, edge.v)) {
            max_min_distance = edge.weight;
        }
    }
    return max_min_distance;
}

Prim avec File de Priorité Multi-Critères

Dans certains environnements, le choix de l'arête ne dépend pas uniquement de son poids, mais également de contraintes topologiques, comme l'altitude. L'algorithme de Prim peut être adapté en utilisant une file de priorité qui évalue d'abord un critère primaire (par exemple, la hauteur du nœud destination), puis un critère secondaire (le poids de l'arête). Cela garantit que l'exploration respecte les contraintes de directionalité ou de capacité tout en minimisant le coût global.

Construction de Graphe Implicite et Théorie des Nombres

Lorsque les sommets d'un graphe sont des entiers et que le poids des arêtes est défini par le plus petit commun multiple (PPCM), une construction naïve en $\mathcal{O}(N^2)$ est irréalisable pour de grandes plages. En exploitant les propriétés du plus grand commun diviseur (PGCD), on peut construire le graphe de manière implicite. En itérant sur les facteurs premiers et leurs multiples, on connecte les nombres partageant un facteur commun. Cette optimisation réduit la complexité de construction à $\mathcal{O}(N \log N)$, rendant l'application de Kruskal viable.

#include <vector>
#include <numeric>
#include <algorithm>

struct ImplicitEdge {
    int u, v;
    long long weight;
    bool operator<(const ImplicitEdge& other) const { return weight < other.weight; }
};

long long compute_lcm(int a, int b) {
    return (static_cast<long long>(a) / std::gcd(a, b)) * b;
}

std::vector<ImplicitEdge> build_lcm_graph(int left_bound, int right_bound) {
    std::vector<ImplicitEdge> edges;
    std::vector<int> first_multiple(right_bound + 1, 0);

    for (int factor = 2; factor <= right_bound; ++factor) {
        int start = ((left_bound + factor - 1) / factor) * factor;
        if (start > right_bound) continue;

        first_multiple[factor] = start;
        for (int multiple = start + factor; multiple <= right_bound; multiple += factor) {
            edges.push_back({first_multiple[factor], multiple, compute_lcm(first_multiple[factor], multiple)});
        }
    }
    return edges;
}

Gestion des Contraintes de Poids Spécifiques

Lorsqu'un arbre couvrant doit contenir exactement $k$ arêtes d'un poids spécifique (par exemple, des arêtes de poids nul), une approche en deux passes est requise. La première passe de Kruskal privilégie les arêtes de poids standard pour identifier les arêtes de poids nul qui sont strictement obligatoires pour maintenir la connexité. La seconde passe force l'inclusion de ces arêtes obligatoires, complète avec d'autres arêtes de poids nul jusqu'à atteindre $k$, et finalise l'arbre avec les arêtes de poids standard.

Transformation par Séquence DFS et Tableau de Différences

Les problèmes impliquant des modifications sur des sous-arbres peuvent être transformés en problèmes d'intervalles via la séquence DFS. En utilisant un tableau de différences, les opérations sur des intervalles $[l, r]$ se traduisent par des modifications aux bornes $l$ et $r+1$. Ces bornes peuvent être modélisées comme des arêtes dans un graphe auxiliaire. Trouver l'arbre couvrant de poids minimum sur ce graphe auxiliaire permet de résoudre le problème de modification de sous-arbre avec un coût minimal.

Algorithme de Borůvka pour les Graphes Denses Implicites

Pour les graphes complets où les arêtes sont définies par une fonction mathématique plutôt que par une liste d'adjacence, l'algorithme de Borůvka est particulièrement efficace. Il fonctionne en $\mathcal{O}(E \log V)$ et, à chaque étape, identifie l'arête sortante de poids minimal pour chaque composante connexe. Le nombre de composantes est au moins divisé par deux à chaque itération, ce qui limite le nombre de phases à $\mathcal{O}(\log V)$. En combinant Borůvka avec des structures de données comme les arbres de recherche binaire pour trouver rapidement les arêtes minimales, on évite l'énumération explicite de toutes les arêtes.

Arbre Couvrant Strictement Sous-Optimal avec LCA

Pour déterminer l'arbre couvrant strictement sous-optimal, on commence par construire l'ACPM standard. Ensuite, pour chaque arête exclue de l'arbre, on évalue le remplacement de l'arête de poids maximal sur le chemin reliant ses extrémités dans l'ACPM. Si le poids de l'arête exclue est égal à ce maximum, on doit utiliser le deuxième poids maximal strictement inférieur sur ce chemin. Cela nécessite une structure de plus petit ancêtre commun (LCA) avec saut binaire (binary lifting) capable de maintenir et fusionner les deux valeurs maximales strictes le long des chemins.

#include <vector>
#include <algorithm>
#include <iostream>

const long long INF = 1e18;

struct LiftingNode {
    int parent;
    long long max1, max2;
};

class StrictSecondMST {
    int log_depth;
    std::vector<std::vector<LiftingNode>> up;
    std::vector<int> depth;

    void merge_maxima(LiftingNode& target, const LiftingNode& a, const LiftingNode& b) {
        long long candidates[4] = {a.max1, a.max2, b.max1, b.max2};
        target.max1 = -INF;
        target.max2 = -INF;
        for (long long w : candidates) {
            if (w > target.max1) {
                target.max2 = target.max1;
                target.max1 = w;
            } else if (w < target.max1 && w > target.max2) {
                target.max2 = w;
            }
        }
    }

public:
    StrictSecondMST(int n, int max_log) : log_depth(max_log), up(max_log, std::vector<LiftingNode>(n + 1)), depth(n + 1, 0) {
        for(int i = 0; i <= n; ++i) {
            up[0][i] = {0, -INF, -INF};
        }
    }

    void set_parent(int u, int p, long long weight) {
        up[0][u].parent = p;
        up[0][u].max1 = weight;
        up[0][u].max2 = -INF;
    }

    void build_lifting_table(int n) {
        for (int j = 1; j < log_depth; ++j) {
            for (int i = 1; i <= n; ++i) {
                int mid = up[j - 1][i].parent;
                up[j][i].parent = up[j - 1][mid].parent;
                merge_maxima(up[j][i], up[j - 1][i], up[j - 1][mid]);
            }
        }
    }

    std::pair<long long, long long> query_path_max(int u, int v) {
        long long res_max1 = -INF, res_max2 = -INF;
        if (depth[u] < depth[v]) std::swap(u, v);
        
        int diff = depth[u] - depth[v];
        for (int j = 0; j < log_depth; ++j) {
            if ((diff >> j) & 1) {
                long long candidates[4] = {res_max1, res_max2, up[j][u].max1, up[j][u].max2};
                res_max1 = -INF; res_max2 = -INF;
                for(long long w : candidates) {
                    if(w > res_max1) { res_max2 = res_max1; res_max1 = w; }
                    else if(w < res_max1 && w > res_max2) { res_max2 = w; }
                }
                u = up[j][u].parent;
            }
        }
        if (u == v) return {res_max1, res_max2};

        for (int j = log_depth - 1; j >= 0; --j) {
            if (up[j][u].parent != up[j][v].parent) {
                long long candidates[6] = {res_max1, res_max2, up[j][u].max1, up[j][u].max2, up[j][v].max1, up[j][v].max2};
                res_max1 = -INF; res_max2 = -INF;
                for(long long w : candidates) {
                    if(w > res_max1) { res_max2 = res_max1; res_max1 = w; }
                    else if(w < res_max1 && w > res_max2) { res_max2 = w; }
                }
                u = up[j][u].parent;
                v = up[j][v].parent;
            }
        }
        long long final_candidates[6] = {res_max1, res_max2, up[0][u].max1, up[0][u].max2, up[0][v].max1, up[0][v].max2};
        res_max1 = -INF; res_max2 = -INF;
        for(long long w : final_candidates) {
            if(w > res_max1) { res_max2 = res_max1; res_max1 = w; }
            else if(w < res_max1 && w > res_max2) { res_max2 = w; }
        }
        return {res_max1, res_max2};
    }
};