超图的实现


在本教程中,我们将学习如何在 C++ 中实现超图。

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

在普通图中,一条边只能连接 2 个顶点,但超图是图的推广,可以使用一条边连接 2 个以上的顶点。

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

这里,我们实现了超图。

示例

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

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

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

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

void createHyperGraph() {
    // Creating the hypergraph
    map<string, vector<int>> 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<int> 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)。

空间复杂度 - 存储 N 条边的空间复杂度为 O(N)。

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

超图的现实应用案例

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

  • 社交网络 - 我们可以使用超图来表示社交网络。在社交网络中,人们可以通过不同的关系进行连接,例如友谊、工作同事、家人等。因此,我们可以将每条边视为一种关系,并将每个人视为图的顶点。现在,我们可以认为每种关系中可能存在 2 个以上的个人。例如,一个家庭包含 4 到 5 个人,一群朋友有 10 个人。

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

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

超图的类型

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

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

  • 二部超图:在二部超图中,每个顶点被分成两个不相交的集合。此外,每个超边都包含来自这两个集合的顶点。

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

  • 带权重的超图:我们可以为每个顶点连接分配一个权重,以赋予每个连接不同的重要性。

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

在这里,我们实现了基本的超图。但是,在实时开发中,单个超边可以连接数百个图顶点。此外,我们还了解了超图的类型和现实应用案例。

更新于: 2023年8月2日

187 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告