C++ Gomory-Hu 树构造

2025年3月24日 | 阅读 6 分钟

Gomory-Hu 树 是无向图中任意一对节点之间最小割值的压缩表示。该树可用于高效解决网络流、最小割和连通性类型问题。在 Gomory-Hu 树中，每条边表示原始图中两个顶点之间的最小割。我们可以通过遍历树来轻松确定任意两个顶点之间的最小割。

Gomory-Hu 的应用

网络流问题： 在流网络中寻找瓶颈。
图划分： 为并行处理图的最佳划分方法。
聚类： 聚类算法用于将一组数据点分组到聚类中，其中点与点之间的距离涉及结构。

Gomory-Hu 树解释

定义和属性

图中两个顶点之间的割是指最小值的边集，从整个图中移除这些边会导致两个顶点断开连接。这种移除的成本连接了该选定边集的基本权重，表示分离这两个顶点所需的最小总权重。

Gomory-Hu 树结构

Gomory-Hu 树 T 是一棵具有 n 个叶子的树，其中每个叶子节点对应于 G 中的一个顶点。
TT 中的每条边对应一个最小割值，该值将由该边两端子树的叶子表示的两组顶点分开。
Gomory-Hu 树中边 (u,v)(u, v) 的权重表示与以 uu 和 vv 为根的两个子树的叶子对应的顶点之间的最小割容量。

构造算法

Gomory-Hu 树 按照以下步骤构建

初始设置： 从无向图 GG 开始，并任意选择顶点 r 作为 Gomory-Hu 树的根。
最大流计算： 对于 GG 中的每个顶点（r 除外）
- 从 rr 到 vv 运行流算法（例如 Edmonds-Karp）来计算从 r 到 v 的最大流。
- 之后，意识到这个最大流表示分离 r 和 v 的最小割的容量。

树构造

对于每对 (r,v)，向 Gomory-Hu 树添加一条边，其权重为计算出的最小割。
对由最小割递归定义的子图重复相同的操作，直到包含所有顶点。

应用

Gomory-Hu 树的主要应用可以说明如下：

网络设计： 在电信和计算机网络中，Gomory-Hu 树允许设计人员识别特定连接并优化网络的可靠性。
图像分割： Gomory-Hu 树通过计算图像分割成不同区域或扇区最弱的分离性，从而实现图像的进一步分割。
聚类算法： Gomory-Hu 树的结构可以帮助推导分层聚类，其中聚类对应于分离这些数据点组的最小割。
鲁棒性分析： 在可靠性工程中，Gomory-Hu 树可以通过评估最小割来帮助分析网络和系统对故障的鲁棒性。

示例

//Program to implement the Gomory-Hu Tree Construction in C++
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <queue>

using namespace std;

class Gomory_Hu_Tree {
public:
    Gomory_Hu_Tree(int num) : num(num), parent(num), minimumCut(num, vector<int>(num, 0)) {}

    void addEdge(int u1, int v1, int value) {
        adjacent[u1].emplace_back(v1, value);
        adjacent[v1].emplace_back(u1, value);
    }

    void build_Method() {
        for (int i = 1; i < num; ++i) {
            int cut = minCutValue(0, i);
            parent[i] = cut;
            // The tree is updated with new cut value.
            updateMinCuts(0, i, cut);
        }
    }

    void printTree_values() {
        for (int i = 1; i < num; ++i) {
            cout << "The Edge from " << parent[i] << " to " << i << "  having cut value is " << minimumCut[0][i] << endl;
        }
    }

private:
    int num;
    vector<vector<pair<int, int>>> adjacent = vector<vector<pair<int, int>>>(100);
    vector<int> parent;
    vector<vector<int>> minimumCut;

    int minCutValue(int src, int dest) {
        //The max flow
       
        vector<int> parent(num, -1);
        vector<int> value(num, 0);
        value[src] = numeric_limits<int>::max();

        queue<int> que;
        que.push(src);

        while (!que.empty()) {
            int u1= que.front();
            que.pop();

            for (auto& edges : adjacent[u1]) {
                int v1 = edges.first;
                int cap = edges.second;

                if (parent[v1] == -1 && cap > 0) {
                    parent[v1] = u1;
                    value[v1] = min(value[u1], cap);
                    if (v1== dest) {
                        return value[v1];
                    }
                    que.push(v1);
                }
            }
        }
        return 0;
    }

    void updateMinCuts(int src, int dest, int cval) {
        minimumCut[src][dest] = cval;
        // Updating Graph Structure
    }
};

int main() {
    int number= 5; // declaring the number of veritices
    Gomory_Hu_Tree tree(number);
   
    // Adding edges (u, v, val)
    tree.addEdge(0, 1, 15);
    tree.addEdge(0, 7, 5);
    tree.addEdge(1, 2, 15);
    tree.addEdge(1, 4, 9);
    tree.addEdge(2, 4, 10);
    tree.addEdge(3, 2, 5);
   
    tree.build_Method();
    tree.printTree_values();

    return 0;
}   

输出

 
The Edge from 15 to 1  having cut value is 15
The Edge from 15 to 2  having cut value is 15
The Edge from 5 to 3  having cut value is 5
The Edge from 9 to 4  having cut value is 9

说明

数据成员

Number： 图中的顶点数。
Parent： 一个向量，存储树中每个顶点的父节点。
MinimumCut： 一个二维向量，用于存储顶点对之间的最小割值。
Adjacent： 图的邻接列表表示，其中每个顶点指向一对（邻居，容量）列表。
Constructor： 它初始化顶点数并设置父节点和 minimumCut 结构。
Methods： addEdge(int u1, int v1, int value)
添加一条具有从顶点 u1 到顶点 v1 容量的双向边。
build_Method： 它构建 Gomory-Hu 树。该算法在每次迭代中查找根节点（即顶点 0）和所有其他顶点之间的最小割值，并更新树结构。
printTree_values()： 输出 Gomory-Hu 树的边及其对应的割值。
minCutValue(int src, int dest)： 它使用 BFS 最大流算法计算从源 src 到汇 dest 的最小割值。
updateMinCuts(int src, int dest, int cval)： 使用找到的割值更新 minimumCut 矩阵。

主要方法

添加边： addEdge 创建两个顶点之间的双向链接，并提供固定的容量，这使得动态构建图变得容易。
构建树： build_Method 计算每个顶点相对于根的最小割。它修改树中的父关系和最小割值。
查找最小割： minCutValue 实现使用 BFS 查找从 src 到 dest 的最大流，该流由边的容量定义。minCutValue 函数返回最小割值，即从源到目的地的最大流。
更新最小割： updateMinCuts 将更新存储在给定源和目的地的 minimumCut 矩阵中的最小割。

主函数

初始化
它创建了一个 Gomory_Hu_Tree 实例，其中包含五个顶点。
添加边
向图中添加多条具有特定容量的边。
构建树
调用 build_Method 根据添加的边构建 Gomory-Hu 树。
打印树
打印出结果，指示 Gomory-Hu 树中的边及其割值。

结论

这是一个简单的 C++ 程序，用于获取 Gomory-Hu 树， 它是一种高效的方法，用于查找任何连接的无向图中顶点对之间的所有最小割。它声明了一个类，包含有关组件的必要参数，例如顶点数、树结构父向量、最小割值矩阵和作为邻接列表的图。可能的关键方法可能包括添加具有容量的边，通过计算 BFS 的最小割值来构建 Gomory-Hu 树，并将边打印到其定义值作为割森林中的权重。

该程序以分步方式构造一棵包含五个顶点的树，向其添加边，并显示该树。其树的打印输出使用图论概念在一行中。

下一主题C++ 中的 Dudeney 数

C++ Gomory-Hu 树构造

Gomory-Hu 的应用

Gomory-Hu 树解释

定义和属性

Gomory-Hu 树结构

构造算法

树构造

应用

示例

说明

数据成员

主要方法

主函数

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Gomory-Hu 树构造

Gomory-Hu 的应用

Gomory-Hu 树解释

定义和属性

Gomory-Hu 树结构

构造算法

树构造

应用

示例

说明

数据成员

主要方法

主函数

结论

相关帖子

C++ 中的自数

C++ 中找到射破所有气球所需的最少箭数

C++ std::pmr::synchronized_pool_resource

C++ 魔幻图案

C++ 中的起伏数

C++ 珠排序（重力排序）算法

C++ 中的 Aronson 序列