檢查圖中是否存在滿足給定條件的長度為3的循環

檢查圖表中是否存在滿足給定條件的長度為 3 的循環，準備重複遍歷每個頂點並查看其相鄰頂點。如果一個頂點有兩個過於關聯的鄰居，則存在長度為 3 的環。此條件保證兩個鄰居之間有一條邊，從而形成一個三角形。透過過濾所有頂點及其相鄰頂點，我們將識別這樣的循環是否存在。如果我們發現一個頂點有兩個相關的鄰居，我們就可以得出結論，圖表中顯示了滿足給定條件的長度為 3 的循環。

使用的方法

• 鄰接矩陣方法

• #鄰接表方法

#鄰接法

為了檢查圖表中是否存在滿足給定條件的長度為 3 的循環，我們可以利用傳染性方法。在這種方法中，我們重複圖表中的每個頂點並檢查其相鄰的頂點。對於每個頂點，我們檢查其任何兩個相鄰頂點是否過於緊密關聯。如果找到這樣的匹配，我們將檢查是否符合該匹配的條件。如果滿足條件，則表示接近滿足給定條件的長度為 3 的循環。透過查看圖表中的所有頂點，我們可以確定是否存在這樣的循環。

演算法

• 將名為「cycleExists」的布林變數初始化為 false。

• 迭代圖中的每個頂點：

  • 對於每個頂點，重複其相鄰的頂點。

  • 對於每個相鄰頂點，強調其相鄰頂點（目前頂點除外）。

  • 如果任兩個相鄰頂點關聯，請繼續下一個步驟。

• 檢查步驟 2c 中找到的關聯頂點的組合是否滿足條件。

  • 如果滿足條件，則將「cycleExists」設為 true 並跳出循環。

• 完成循環後，檢查「cycleExists」的值。

  • 如果「cycleExists」為真，則圖中存在滿足給定條件的長度為 3 的循環。

  • 如果「cycleExists」錯誤，則不存在這樣的循環。

• 輸出結果。

• 此計算會重複圖表的頂點，分析其相鄰頂點，並檢查相鄰頂點的任何匹配是否形成滿足給定條件的長度為 3 的循環。

  李>

範例

#include <iostream>
#include <vector>

using namespace std;

bool checkCycle(vector<vector<int>>& graph, int v, vector<bool>& visited, int parent, int condition) {
    visited[v] = true;

    for (int u : graph[v]) {
        if (!visited[u]) {
            visited[u] = true;

            for (int w : graph[u]) {
                if (visited[w] && w != parent && condition == graph[v][u] + graph[u][w]) {
                    return true;
                }
            }

            visited[u] = false;
        }
    }

    return false;
}

bool hasCycleOfLength3(vector<vector<int>>& graph, int condition) {
    int numVertices = graph.size();
    vector<bool> visited(numVertices, false);

    for (int v = 0; v < numVertices; v++) {
        visited[v] = true;

        for (int u : graph[v]) {
            if (checkCycle(graph, u, visited, v, condition)) {
                return true;
            }
        }

        visited[v] = false;
    }

    return false;
}

int main() {
    int numVertices, numEdges;
    cout << "Enter the number of vertices and edges: ";
    cin >> numVertices >> numEdges;

    vector<vector<int>> graph(numVertices);

    cout << "Enter the connections between vertices (u, v) and their corresponding weights: " << endl;
    for (int i = 0; i < numEdges; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;

        graph[u].push_back(v);
        graph[v].push_back(u);

        // Store the weight/condition between u and v
        graph[u][v] = weight;
        graph[v][u] = weight;
    }

    int condition;
    cout << "Enter the condition to be satisfied: ";
    cin >> condition;

    if (hasCycleOfLength3(graph, condition)) {
        cout << "Cycle of length 3 satisfying the condition exists." << endl;
    } else {
        cout << "Cycle of length 3 satisfying the condition does not exist." << endl;
    }

    return 0;
}

輸出

Enter the number of vertices and edges:  

鄰接表方法

相鄰的列表方法可以是用於與圖表對話的資訊結構。在這種方法中，圖表的每個頂點都與包含其所有相鄰頂點的清單相關。為了檢查圖表中是否存在滿足給定條件的長度為 3 的循環，我們將迭代每個頂點及其相鄰頂點。對於每個相鄰頂點，我們檢查它是否包含與目前頂點共同的相鄰頂點。如果存在這樣的公共頂點，則找到長度為 3 的環。這種方法可以透過存放有關傳染性清單中幾乎所有頂點及其關聯的基本資料來確保對圖表的有效調查。

演算法

• 製作一個與圖表對話的傳染性列表，其中每個頂點都包含其相鄰頂點的列表。

• 迭代圖中的每個頂點。

• 對於每個頂點，重複其相鄰的頂點。

• 對於每個相鄰頂點，強調其相鄰頂點（目前頂點除外）。

• 檢查目前頂點和相鄰頂點的相鄰頂點之間是否存在公共頂點。

• 如果找到公共頂點，則存在一個長度為 3 的環。傳回 true。

• 如果沒有找到長度為 3 的環，則傳回 false。

範例

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

bool hasCycleOfLength3(vector<vector<int>>& graph) {
    int n = graph.size();
    
    for (int u = 0; u < n; ++u) {
        unordered_set<int> adjSet(graph[u].begin(), graph[u].end());

        for (int v : graph[u]) {
            for (int w : graph[v]) {
                if (w != u && adjSet.count(w) > 0) {
                    return true; // Cycle of length 3 found
                }
            }
        }
    }

    return false; // No cycle of length 3 found
}

int main() {
    // Create the graph as an adjacency list
    vector<vector<int>> graph = {
        {1, 2},
        {0, 2},
        {0, 1, 3},
        {2, 4},
        {3}
    };

    // Check if a cycle of length 3 exists
    bool cycleExists = hasCycleOfLength3(graph);

    // Print the result
    if (cycleExists) {
        cout << "A cycle of length 3 exists in the graph." << endl;
    } else {
        cout << "No cycle of length 3 exists in the graph." << endl;
    }

    return 0;
}

輸出

A cycle of length 3 exists in the graph.

結論

本文研究了檢查圖表中是否存在滿足給定條件的長度為 3 的循環的方法。它闡明了兩種方法，特別是傳染性框架方法和傳染性列表方法。本文追蹤了計算過程並給出了這兩種方法的 C 代碼位。傳染性網絡方法包括強調每個頂點及其相鄰頂點來識別滿足條件的長度為 3 的循環。傳染性列表方法利用與圖表對話的資訊結構，並檢查相鄰頂點之間的公共頂點來確定循環的接近程度。

以上是檢查圖中是否存在滿足給定條件的長度為3的循環的詳細內容。更多資訊請關注PHP中文網其他相關文章！