C++ 实现超图

在本教程中，我们将学习如何在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)来遍历所有边缘。

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

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

超图的实际应用案例

当我们看超图在普通图上的实现时，第一个问题是为什么我们要使用超图。在这里，我们将看到一些超图可以使用的实际应用案例。

社交网络 -我们可以使用超图来表示社交网络。在社交网络中，人们可以通过不同的关系进行连接，例如友谊，工作同事，家庭等。因此，我们可以将每个边缘用作关系，将每个人用作图的顶点。现在，我们可以认为每个关系中可能有超过2个人。例如，一个家庭有4到5个人，一个由10个朋友组成的群体。
数据库建模 -我们可以使用超图来建模需要在单个关系中连接表的多个属性的数据库。
复杂系统表示 -使用超图的另一个用例是开发复杂系统，例如交通系统，生物互动等。