資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究超圖的實現
在本教程中，我們將學習如何在 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 種超圖型別。
均勻超圖：均勻超圖的每條邊都包含相同數量的頂點。
二部超圖：在二部超圖中，每個頂點被分成兩個不相交的集合。此外，每個超邊都包含來自這兩個集合的頂點。
有向超圖：在有向超圖中，每個超邊都有方向。因此，我們需要考慮每個超邊連線頂點的順序。
帶權重的超圖：我們可以為每個頂點連線分配一個權重，以賦予每個連線不同的重要性。
帶標籤的超圖：我們可以為每個頂點連線新增一個標籤，以傳達有關頂點的更多資訊。
在這裡，我們實現了基本的超圖。但是，在即時開發中，單個超邊可以連線數百個圖頂點。此外，我們還了解了超圖的型別和現實應用案例。
187 次檢視
