移除 Q 个指定顶点后给定图中连通分量的数量
移除 Q 个指定顶点后，图中剩余顶点所创建的断开子图的数量由连通分量的数量表示。没有边连接各个分量；相反，每个连通分量由一组通过边连接的顶点组成。移除 Q 个顶点后，某些顶点可能会变得孤立，从而导致连接断开并形成新的分量。该方法旨在确定最终会有多少个断开子图。许多应用，包括网络分析、社交网络研究和优化方法，都需要了解连通分量的数量。
使用的方法
Kosaraju 算法
基于矩阵的方法
Kosaraju 算法
从图中删除 Q 个指定顶点后，使用 Kosaraju 算法确定网络中连通分量的数量。它在两次传递中使用深度优先搜索 (DFS)。它在第一次传递中调查原始图以获取每个顶点的"完成时间"。在第二次传递中，图被转置(所有边的方向都被反转)，并将 DFS 应用于转换后的图，从完成时间最高的顶点开始。该方法确定了更改后的图中链接组件的数量，通过在过程中忽略已删除的 Q 个顶点来显示顶点删除后断开连接的子图的数量。
算法
要存储初始 DFS 传递的顶点，请创建一个空堆栈。
在原始图上，运行第一个 DFS 传递:
使用 DFS 从未探索的顶点开始探索连通顶点的组件。
当访问了顶点的所有周围顶点后，Mark 会访问该顶点并将其推送到堆栈上。
反转每条边的方向以转置图。
对于第二个 DFS 传递，创建一个布尔数组来跟踪访问过的顶点顶点。
通过第二次 DFS 传递运行修改后的图形:
依次从堆栈中删除每个顶点。
如果尚未访问或销毁(不在 Q 中)，则使用 DFS 探索顶点的相关组件。在此过程中，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() {
// 创建图表(邻接表表示)
vector<vector<int>> graph = {
{1},
{0, 2},
{1},
{4},
{3}
};
int reachableNodes = countReachableNodes(graph);
cout << "可从所有其他节点访问的节点数:" << reachableNodes << endl;
return 0;
}
输出
可从所有其他节点访问的节点数:2
结论
总之，网络分析和相关领域中的一个关键指标是删除一定数量的顶点后图中剩余的连接组件数。基于矩阵的方法和 Kosaraju 算法都提供了计算此计数的有效方法。虽然基于矩阵的方法在重新设计的图上使用 DFS 或 BFS 等图遍历算法来有效地找到链接组件，但 Kosaraju 算法在两次传递中使用深度优先搜索来识别强连接组件。即使在删除某些顶点之后，这两种方法都能产生可靠的结果，有助于理解图的连通性和结构特征。图的属性和当前挑战的特定要求决定了要使用的方法。
