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