数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究查找移除后不会断开图的边
分析图中每条边的连通性，以找到移除后不会破坏图的边。我们可以通过系统地检查移除单个边的影响来识别哪些边对于保持节点之间的连通性至关重要。“桥边”或“关键边”是指移除后仍然使图保持连通的边。这些边对于维持图的整体结构和避免断开至关重要。在网络分析、交通规划和基础设施设计中，必须识别此类边以确保系统的鲁棒性和有效的通信。
使用的方法
Tarjan 算法
克鲁斯卡尔算法
Tarjan 算法
为了在图中找到关键边并发现强连通分量，使用 Tarjan 算法。它通过执行深度优先搜索，根据遍历的顺序为每个节点分配唯一的标识（低连接值）。当节点的低连接值与其祖先的标识匹配时，就找到了一个强连通分量。同一分量内的节点通过非关键边连接，这意味着可以移除它们而不会断开图。但是，必须保留连接来自不同分量的节点的边以保持整体连通性。Tarjan 算法用于有效地分析图的结构并识别关键边。
算法
设置一个空栈来记录已访问的节点，一个空列表来存储关键边，以及一个计数器来跟踪节点发现的顺序。
从图中的任意一点开始深度优先搜索 (DFS) 探索。
根据发现的顺序，在 DFS 期间为每个节点分配不同的低连接值，并将它们存储在栈中。
访问一个节点时，将其低连接值更新为其自身索引和其相邻节点的低连接值的最小值，以便发现强连通分量 (SCC)。如果节点的低连接值与其索引一致，则该节点是强连通分量的根。通过从栈中弹出节点直到根节点，将节点添加到分量列表中。
继续 DFS 探索，发现并存储图中的所有强连通分量。重复 SCC 识别。
调查强连通分量中每个节点的邻居。
如果相邻节点是另一个 SCC 的成员，则连接它们的边是关键边。
将关键边添加到列表中以供进一步检查，以便存储它们。
继续遍历图，直到每个节点都被查看和处理。
在步骤 8 中获得的关键边列表包含如果移除会导致图断开的边。为了保持整体连通性，这些边至关重要。程序识别关键边以进行图完整性和结构分析。
示例
#include <iostream>
#include <vector>
using namespace std;
const int MAX_NODES = 1000;
vector<int> adj[MAX_NODES];
vector<bool> visited;
vector<int> disc, low;
vector<pair<int, int>> criticalEdges;
int timeCounter = 0;
void dfs(int u, int parent) {
visited[u] = true;
disc[u] = low[u] = ++timeCounter;
for (int v : adj[u]) {
if (v == parent) continue;
if (!visited[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u])
criticalEdges.emplace_back(min(u, v), max(u, v));
} else {
low[u] = min(low[u], disc[v]);
}
}
}
void findCriticalEdges(int nodes) {
visited.assign(nodes, false);
disc.assign(nodes, 0);
low.assign(nodes, 0);
criticalEdges.clear();
timeCounter = 0;
for (int i = 0; i < nodes; i++) {
if (!visited[i]) {
dfs(i, -1);
}
}
}
int main() {
int nodes = 5; // Number of nodes in the graph
// Add edges to the adjacency list
adj[0].push_back(1);
adj[1].push_back(0);
adj[1].push_back(2);
adj[2].push_back(1);
adj[1].push_back(3);
adj[3].push_back(1);
adj[3].push_back(4);
adj[4].push_back(3);
findCriticalEdges(nodes);
cout << "Critical edges in the Graph:\n";
for (const auto& edge : criticalEdges) {
cout << edge.first << " " << edge.second << "\n";
}
return 0;
}
输出
Critical edges in the Graph: 1 2 3 4 1 3 0 1
克鲁斯卡尔算法
在查找移除后不会断开图的边的上下文中，使用克鲁斯卡尔算法创建最小生成树 (MST)。该算法迭代地将权重最小的边添加到 MST 中，同时确保不会出现循环，按权重的升序对边进行排序。对于保持图内连通性至关重要的边是包含在 MST 中的边。其余边，即未包含在 MST 中的边，可以被视为非关键边，因为移除它们不会导致图断开，但可能会使图更重且效率更低。
算法
创建一个名为“non_critical_edges”的空列表，用于保存非关键边。
根据权重的递增顺序对 G 的边进行排序。
创建一个不相交集数据结构，并将其初始化为跟踪连接的元素。
为 G 中的每个顶点创建一个不相交集。
在排序后的边列表中，对于每条边 (u, v)，
验证当添加边 (u, v) 时 MST 是否会产生循环
使用不相交集数据结构找到包含顶点 u 和 v 的集合的根（代表）。
如果根不同，则不存在循环；将边 (u, v) 添加到 MST 中。否则，跳过此边并继续下一个边。
如果处理完所有边后剩余 (n − 1) 条边，则 MST 完成。终止循环。
如果 MST 中的边数少于 (n − 1)，则图未完全连接并且存在非关键边。
再次遍历排序后的边列表，将剩余的边（未在 MST 中找到）添加到“non_critical_edges”列表中。
现在，“non_critical_edges”中包含移除后不会导致图断开的边。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct CustomEdge {
int u, v, weight;
};
struct UniqueDisjointSet {
vector<int> parent, rank;
UniqueDisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i)
parent[i] = i;
}
int find(int u) {
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}
void union_sets(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u != root_v) {
if (rank[root_u] < rank[root_v])
parent[root_u] = root_v;
else if (rank[root_u] > rank[root_v])
parent[root_v] = root_u;
else {
parent[root_v] = root_u;
rank[root_u]++;
}
}
}
};
vector<CustomEdge> findUniqueNonCriticalEdges(int n, vector<CustomEdge>& edges) {
vector<CustomEdge> non_critical_edges;
UniqueDisjointSet ds(n);
sort(edges.begin(), edges.end(), [](const CustomEdge& a, const CustomEdge& b) {
return a.weight < b.weight;
});
for (const auto& edge : edges) {
int u = edge.u;
int v = edge.v;
if (ds.find(u) != ds.find(v)) {
ds.union_sets(u, v);
}
else {
non_critical_edges.push_back(edge);
}
if (non_critical_edges.size() == n - 1)
break;
}
return non_critical_edges;
}
int main() {
int n = 5;
vector<CustomEdge> edges = {
{0, 1, 2},
{0, 2, 4},
{1, 2, 1},
{1, 3, 3},
{2, 3, 5},
{2, 4, 7},
{3, 4, 6}
};
vector<CustomEdge> unique_non_critical_edges = findUniqueNonCriticalEdges(n, edges);
cout << "Unique Non-Critical Edges:\n";
for (const auto& edge : unique_non_critical_edges) {
cout << "(" << edge.u << ", " << edge.v << ", " << edge.weight << ")\n";
}
return 0;
}
输出
Unique Non-Critical Edges: (0, 2, 4) (2, 3, 5) (2, 4, 7)
结论
通过巧妙地使用 Tarjan 和克鲁斯卡尔算法，我们有效地识别了可移除的边，而不会断开图。这些非关键边对于保持图的整体结构和避免断开至关重要。虽然克鲁斯卡尔算法创建最小生成树并识别非关键边，但 Tarjan 算法有助于发现强连通分量。边连通性分析有助于识别为了断开图而必须移除的边的绝对最小数量。在各种领域（包括网络分析、交通规划和基础设施设计）中，了解这些关键边和非关键边对于保持鲁棒性和有效通信至关重要。
138 次查看
