超圖的實現

在本教學中，我們將學習用 C 實作超圖。

定義- 超圖是圖的特殊版本。其中單一可以連接2個或多個頂點。

在普通圖中，單一邊只能連接 2 個頂點，但超圖是圖的泛化，可以用來用單一邊連接 2 個以上的頂點。

在超圖中，邊稱為超邊。我們可以用 H(E, V) 來表示超圖，其中 E 是一條超邊，v 是單一超邊連接的頂點集合。

在這裡，我們實作了超圖。

範例

在下面的範例中，我們示範了使用 C 中的地圖資料結構來實現超圖。在地圖中，我們將邊名稱儲存為鍵，將邊連接的頂點集儲存為值。

之後，我們使用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 個邊。

在上面的例子中，我們看到超邊可以連接不同的頂點。

Hypergraph 的現實用例

當我們研究超圖相對於普通圖的實作時，第一個問題是為什麼我們應該使用超圖。在這裡，我們將看到一些可以使用超圖的現實用例。

• 社群網路- 我們可以用超圖來表示社群網路。在社交網絡中，人們可能會與不同的關係產生聯繫，例如友誼、同事、家人等。因此，我們可以將每條邊用作關係，將每個人用作圖的頂點。現在，我們可以認為每個關係中可能有兩個以上的人。例如，家庭有 4 至 5 人，一群 10 名朋友。

• 資料庫建模- 我們可以使用超圖來對資料庫進行建模，在該資料庫中我們需要以單一關係連接表的多個屬性。

• 複雜系統表示- 使用超圖的另一個用例是開發複雜系統，例如交通系統、生物相互作用等。

超圖的型別

在這裡，我們將討論 5 種類型的超圖。

• 均勻超圖：均勻超圖的每條邊都包含相同數量的頂點。

• 二分超圖：在二分超圖中，每個頂點都分成兩個不相交的集合。此外，每個超邊都包含兩個集合中的頂點。

• 有向超圖：在有向超圖中，每個超邊都有方向。因此，我們需要考慮每個超邊連接頂點的順序。

• 帶有權重的超圖：我們可以為每個頂點連接分配一個權重，從而為每個連接分配不同的重要性。

• 帶有標籤的超圖：我們可以為頂點的每個連接添加標籤，以傳達有關頂點的更多資訊。

在這裡，我們已經實現了基本的超圖。然而，在即時開發中，單一超邊可以連接數百個圖頂點。此外，我們還看到了超圖的類型和現實生活中的用例。

以上是超圖的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！