超图的实现
在本教程中,我们将学习如何在 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 种超图类型。
均匀超图:均匀超图的每条边都包含相同数量的顶点。
二部超图:在二部超图中,每个顶点被分成两个不相交的集合。此外,每个超边都包含来自这两个集合的顶点。
有向超图:在有向超图中,每个超边都有方向。因此,我们需要考虑每个超边连接顶点的顺序。
带权重的超图:我们可以为每个顶点连接分配一个权重,以赋予每个连接不同的重要性。
带标签的超图:我们可以为每个顶点连接添加一个标签,以传达有关顶点的更多信息。
在这里,我们实现了基本的超图。但是,在实时开发中,单个超边可以连接数百个图顶点。此外,我们还了解了超图的类型和现实应用案例。