极客笔记C++ 给定图形在删除给定的Q个顶点后的连接组件数
在删除了Q个指定顶点后，在图形中剩余顶点创建的断开子图数量由连接组件的计数表示。各个组件之间没有边连接；相反，每个连接组件由通过边相连的顶点集合组成。由于删除了Q个顶点，一些顶点可能变得孤立，导致连接断开并形成新的组件。这个方法旨在确定最终会有多少个断开的子图。许多应用程序，包括网络分析、社交网络研究和优化方法，都需要了解连接组件的数量。
使用的方法
- Kosaraju算法
-
基于矩阵的方法
Kosaraju算法
在从图中删除了Q个指定顶点之后，使用Kosaraju算法来确定网络中连接组件的数量。它使用深度优先搜索（DFS）进行两次遍历。在第一次遍历中，它研究原始图以获取每个顶点的“完成时间”。在第二次遍历中，将图进行转置（所有边的方向都被反转），并对转置后的图应用DFS，从具有最高完成时间的顶点开始。该方法确定更改后的图中的连接组件的数量，通过在过程中忽略掉已删除的Q个顶点，暴露出顶点删除后的断开子图数量。
步骤
- 创建一个空栈来存储初始DFS通行证的顶点。
-
对原始图运行第一个DFS通行证：
使用DFS从未被探索的顶点开始探索一个连接的顶点组件。
当访问了一个顶点的所有相邻顶点时，标记访问该顶点，并将其推入栈中。
- 反转每条边的方向来转置图形。
-
为第二个DFS通行证创建一个布尔数组来跟踪已访问的顶点。
-
将修改后的图形通过第二个DFS通行证：
依次从栈中删除每个顶点。
如果一个顶点尚未被访问或被删除（不在Q中），则使用DFS来探索与该顶点相关的组件。在此过程中，标记已访问的顶点。
- 删除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）。
-
标记在遍历过程中访问的顶点，以防止重复处理。
-
继续遍历，直到已看到与初始顶点相关的所有顶点。
-
对于发现的每组相互连接的顶点，通过增加等式中的连通分量的数量来增加连通分量的数目。
-
根据需要重复执行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算法则使用两次深度优先搜索来识别强连通分量。即使在移除一定的顶点之后，这两种方法仍然能够产生可靠的结果，帮助理解图的连通性和结构特征。图的属性和当前挑战的特定要求决定了要使用的方法。