給定圖形刪除給定的Q個頂點後的連通分量數量

刪除 Q 個指定頂點後，圖中剩餘頂點所建立的斷開子圖的數量由連通分量的計數表示。各個組件之間沒有邊緣連接；相反，每個連接的組件都由透過邊連接的頂點的集合組成。由於 Q 頂點的移除，一些頂點可能會變得孤立，導致連接崩潰並形成新的組件。該方法旨在確定最終會有多少個不相連的子圖。許多應用程序，包括網路分析、社交網路研究和最佳化方法，都需要了解連接組件的數量。

使用的方法

• Kosaraju 演算法

• 基於矩陣的方法

#Kosaraju演算法

從圖中刪除 Q 個指定頂點後，Kosaraju 演算法用於確定網路中連結組件的數量。它分兩次使用深度優先搜尋 (DFS)。它在第一遍中研究原始圖以獲得每個頂點的“完成時間”。在第二遍中，圖被轉置（所有邊的方向都反轉），並且從完成時間最長的頂點開始，將 DFS 應用於變換後的圖。此方法確定更改圖中的連結組件的數量，透過在過程中忽略刪除的 Q 頂點來暴露頂點刪除後斷開的子圖的數量。

演算法

• 要儲存初始 DFS 通道的頂點，請建立一個空堆疊。

• 在原始圖上，執行第一個 DFS 遍歷：

  使用 DFS 從未探索的頂點開始探索連接的頂點的元件。

  當所有頂點的周圍的頂點已被訪問過，Mark 訪問該頂點並將其壓入堆疊。

• 反轉每條邊的方向以轉置圖形。

• 對於第二次 DFS 遍歷，建立一個布林數組來追蹤訪問過的頂點。

• 透過第二次 DFS 遍歷運行修改後的圖：

  從堆疊中依序刪除每個頂點。

  使用 DFS 探索頂點的相關元件（如果沒有）沒有被存取或破壞（不在Q中）。在整個過程中，Mark 訪問了頂點。

• 移除 Q 個頂點後，連通分量的計數等於呼叫第二個 DFS 的次數。

• 刪除 Q 個頂點後，流程會產生網路中連通分量的數量。

範例

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfs1(int vertex, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& stk) {
    visited[vertex] = true;
    for (int neighbor : graph[vertex]) {
        if (!visited[neighbor])
            dfs1(neighbor, graph, visited, stk);
    }
    stk.push(vertex);
}

void dfs2(int vertex, vector<vector<int>>& transpose_graph, vector<bool>& visited) {
    visited[vertex] = true;
    for (int neighbor : transpose_graph[vertex]) {
        if (!visited[neighbor])
            dfs2(neighbor, transpose_graph, visited);
    }
}

int kosaraju(int N, vector<vector<int>>& graph, vector<vector<int>>& transpose_graph, vector<int>& Q) {
    vector<bool> visited(N + 1, false);
    stack<int> stk;

    for (int i = 1; i <= N; i++) {
        if (!visited[i])
            dfs1(i, graph, visited, stk);
    }

    fill(visited.begin(), visited.end(), false);

    for (int i = 0; i < Q.size(); i++) {
        visited[Q[i]] = true;
    }

    int count = 0;
    while (!stk.empty()) {
        int vertex = stk.top();
        stk.pop();
        if (!visited[vertex]) {
            dfs2(vertex, transpose_graph, visited);
            count++;
        }
    }

    return count;
}

int main() {
    int N = 7; 
    int M = 8; 
    int E = 2; 

    vector<vector<int>> graph(N + 1);
    vector<vector<int>> transpose_graph(N + 1);

    vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 1}, {2, 4}, {4, 5}, {5, 6}, {6, 4}, {7, 6}};

    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        transpose_graph[v].push_back(u);
    }

    vector<int> Q = {3, 4};

    int result = kosaraju(N, graph, transpose_graph, Q);
    cout << result << endl;

    return 0;
}

輸出

5

基於矩陣的方法

鄰接矩陣或鄰接列表用於表示基於矩陣的方法中的圖。然後從矩陣中刪除 Q 個指定的頂點。然後，透過使用圖遍歷演算法（例如深度優先搜尋（DFS）或廣度優先搜尋（BFS））來確定更改的圖的連接組件的數量。記錄已遍歷的頂點以防止重新處理。刪除 Q 個頂點後圖中連通分量的計數對應於遍歷方法運行的次數。對於不同的圖分析和網路相關應用，此方法可以有效計算連結組件計數。

演算法

• 使用鄰接矩陣或鄰接表來表示圖。

• 修改圖是透過從矩陣或清單中刪除指定的 Q 頂點來產生的。

• 設定一個變數來追蹤連接組件的數量。

• 最初迭代更新圖中的每個頂點。

• 對每個未探索的頂點套用圖遍歷演算法（DFS 或 BFS）。

• 標記遍歷過程中造訪過的頂點，以防止重新處理。

• 繼續遍歷，直到與初始頂點相關的所有頂點都被看到。

• 對於發現的每組唯一的互連頂點，將方程式中的連通分量數量增加 1。

• 要存取更新圖中的每個頂點，請根據需要重複步驟 5 到 8。

• 刪除所需頂點後，圖中斷開的子圖總數由連接元件計數的最終值表示。

範例

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor);
        }
    }
}

int countReachableNodes(vector<vector<int>>& graph) {
    int N = graph.size();
    vector<bool> visited(N, false);
    int count = 0;

    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            count++;
        }
    }

    return count;
}

int main() {
    // Create the graph (Adjacency List representation)
    vector<vector<int>> graph = {
        {1},
        {0, 2},
        {1},
        {4},
        {3}
    };

    int reachableNodes = countReachableNodes(graph);
    cout << "Number of nodes accessible from all other nodes: " << reachableNodes << endl;

    return 0;
}

輸出

Number of nodes accessible from all other nodes: 2

結論

總之，網路分析和相關領域的一個關鍵指標是刪除一定數量的頂點後圖中剩餘的連通分量的數量。基於矩陣的方法和 Kosaraju 演算法都提供了計算此計數的有效方法。基於矩陣的方法在重新設計的圖上使用 DFS 或 BFS 等圖遍歷演算法來有效地尋找連結組件，而 Kosaraju 演算法在兩次遍歷中使用深度優先搜尋來識別強連接組件。即使在刪除某些頂點之後，這兩種方法也會產生可靠的結果，有助於理解圖的連結性和結構特徵。圖的屬性和當前挑戰的特定要求決定了要使用的方法。

以上是給定圖形刪除給定的Q個頂點後的連通分量數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！