给定图形删除给定的Q个顶点后的连通分量数量

删除 Q 个指定顶点后，图中剩余顶点创建的断开子图的数量由连通分量的计数表示。各个组件之间没有边缘连接；相反，每个连接的组件都由通过边连接的顶点的集合组成。由于 Q 顶点的移除，一些顶点可能会变得孤立，导致连接崩溃并形成新的组件。该方法旨在确定最终会有多少个不相连的子图。许多应用程序，包括网络分析、社交网络研究和优化方法，都需要了解连接组件的数量。

使用的方法

• Kosaraju 算法

• 基于矩阵的方法

Kosaraju算法

从图中删除 Q 个指定顶点后，Kosaraju 算法用于确定网络中链接组件的数量。它分两次使用深度优先搜索 (DFS)。它在第一遍中研究原始图以获得每个顶点的“完成时间”。在第二遍中，图被转置（所有边的方向都反转），并且从完成时间最长的顶点开始，将 DFS 应用于变换后的图。该方法确定更改图中的链接组件的数量，通过在过程中忽略删除的 Q 顶点来暴露顶点删除后断开的子图的数量。

算法

• 要存储初始 DFS 通道的顶点，请创建一个空堆栈。

• 在原始图上，运行第一个 DFS 遍历：

  使用 DFS 从未探索的顶点开始探索连接的顶点的组件。

  当所有顶点的周围的顶点已被访问过，Mark 访问该顶点并将其压入堆栈。

• 反转每条边的方向以转置图形。

• 对于第二次 DFS 遍历，创建一个布尔数组来跟踪访问过的顶点。

• 通过第二次 DFS 遍历运行修改后的图：

  从堆栈中依次删除每个顶点。

  使用 DFS 探索顶点的相关组件（如果没有）没有被访问或破坏（不在Q中）。在整个过程中，Mark 访问了顶点。

• 移除 Q 个顶点后，连通分量的计数等于调用第二个 DFS 的次数。

  

  玄鲸Timeline

  一个AI驱动的历史时间线生成平台

  下载

• 删除 Q 个顶点后，该过程会生成网络中连通分量的数量。

示例

#include 
#include 
#include 
using namespace std;

void dfs1(int vertex, vector>& graph, vector& visited, stack& 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>& transpose_graph, vector& visited) {
    visited[vertex] = true;
    for (int neighbor : transpose_graph[vertex]) {
        if (!visited[neighbor])
            dfs2(neighbor, transpose_graph, visited);
    }
}

int kosaraju(int N, vector>& graph, vector>& transpose_graph, vector& Q) {
    vector visited(N + 1, false);
    stack 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> graph(N + 1);
    vector> transpose_graph(N + 1);

    vector> 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 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 
#include 
using namespace std;

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

int countReachableNodes(vector>& graph) {
    int N = graph.size();
    vector 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> 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 算法在两次遍历中使用深度优先搜索来识别强连接组件。即使在删除某些顶点之后，这两种方法也会产生可靠的结果，有助于理解图的连通性和结构特征。图的属性和当前挑战的特定要求决定了要使用的方法。