超图的实现

在本教程中，我们将学习用 C++ 实现超图。

定义- 超图是图的特殊版本。其中单个可以连接2个或多个顶点。

在普通图中，单条边只能连接 2 个顶点，但超图是图的泛化，可以用于用单条边连接 2 个以上的顶点。

在超图中，边称为超边。我们可以用 H(E, V) 来表示超图，其中 E 是一条超边，v 是由单个超边连接的顶点集合。

在这里，我们实现了超图。

示例

在下面的示例中，我们演示了使用 C++ 中的地图数据结构实现超图。在地图中，我们将边名称存储为键，将边连接的顶点集存储为值。

之后，我们使用erase()方法从图中删除“edge2”。另外，使用 insert() 方法将连接 4 个顶点的“edge4”插入到图中。

最后，我们打印了图形的所有边及其连接的顶点。

#include 
#include 
using namespace std;

void createHyperGraph() {
    // Creating the hypergraph
    map> h_graph = {{"edge1", {32, 21, 90}},
                                        {"edge2", {21, 47, 54}},
                                        {"edge3", {43, 76}}};
    // Removing edge from the hypergraph
    h_graph.erase("edge2");
    // Inserting a new edge in the hypergraph
    h_graph.insert({"edge4", {48, 61, 93, 52, 89}});
    cout << "The hypergraph is :-" << endl;
    for (auto ele : h_graph) {
        string edge = ele.first;
        cout << edge << " : ";
        vector vert = ele.second;
        for (int v : vert) {
            cout << v << " ";
        }
        cout << endl;
    }
}
int main() {
    createHyperGraph();
    return 0;
}

输出

The hypergraph is :-
edge1 : 32 21 90 
edge3 : 43 76 
edge4 : 48 61 93 52 89

时间复杂度 - O(N) 遍历所有边。

空间复杂度 - O(N) 来存储 N 个边。

在上面的例子中，我们看到超边可以连接不同的顶点。

Hypergraph 的现实用例

当我们研究超图相对于普通图的实现时，第一个问题是为什么我们应该使用超图。在这里，我们将看到一些可以使用超图的现实用例。

ListenHub

超真实的AI播客生成器

下载

• 社交网络- 我们可以使用超图来表示社交网络。在社交网络中，人们可能会与不同的关系产生联系，例如友谊、同事、家人等。因此，我们可以将每条边用作关系，将每个人用作图的顶点。现在，我们可以认为每个关系中可能有两个以上的人。例如，家庭有 4 至 5 人，一群 10 名朋友。

• 数据库建模- 我们可以使用超图来对数据库进行建模，在该数据库中我们需要以单个关系连接表的多个属性。

• 复杂系统表示- 使用超图的另一个用例是开发复杂系统，例如交通系统、生物相互作用等。

超图的类型

在这里，我们将讨论 5 种类型的超图。

• 均匀超图：均匀超图的每条边都包含相同数量的顶点。

• 二分超图：在二分超图中，每个顶点都分为两个不相交的集合。此外，每个超边都包含两个集合中的顶点。

• 有向超图：在有向超图中，每个超边都有方向。因此，我们需要考虑每个超边连接顶点的顺序。

• 带权重的超图：我们可以为每个顶点连接分配一个权重，从而为每个连接分配不同的重要性。

• 带标签的超图：我们可以为顶点的每个连接添加标签，以传达有关顶点的更多信息。

在这里，我们已经实现了基本的超图。然而，在实时开发中，单个超边可以连接数百个图顶点。此外，我们还看到了超图的类型和现实生活中的用例。