超图的实现

在本教程中，我们将学习用 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<string, vector> 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 的现实用例

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

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

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

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

超图的类型

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

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

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

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

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

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

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

以上就是超图的实现的详细内容，更多请关注创想鸟其它相关文章！