C++ 寻找不会断开图形的边缘删除

分析图中每条边的连通性，找出不会破坏图形的删除边缘。我们可以通过系统地检查消除单个边的影响来确定哪些边缘对于保持节点之间的连通性至关重要。被称为“桥边”或“关键边”的边缘在被消除后仍然保持图形的连通性。这些边缘对于维持图形的总体结构和避免断连非常重要。在网络分析、交通规划和基础设施设计中，必须识别出这些边缘，以确保系统的稳健性和有效的通信。

使用的方法

• Tarjan算法

• Kruskal算法

Tarjan算法

为了找到图形中的关键边和发现强连通分量，使用Tarjan算法。它通过进行深度优先搜索，根据遍历顺序为每个节点分配独特的标识（低连接值）。 当节点的低连接值与其祖先的标识匹配时，已发现一个高度连通的分量。同一分量中的节点由非关键边连接，这意味着它们可以被删除而不会断开图形。但是，为了保持总体连通性，连接来自不同分量的节点的边是必不可少的，必须保留它们。为了高效地分析图形的结构并确定关键边，使用Tarjan算法。

步骤

• 建立一个空堆栈以记录访问过的节点，一个空列表以存储关键边，以及一个计数器来跟踪节点发现顺序。

• 从图中的任意一个点开始进行深度优先搜索（DFS）探索。

• 根据发现顺序，在DFS过程中为每个节点分配不同的低连接值，并将它们存储在堆栈中。

• 访问节点时，将其低连接值更新为其自身索引和其相邻节点的低连接值的最小值，以便发现高度连接的组件（SCCs）。如果节点的低连接值与其索引相符，则该节点是一个强连通分量的根节点。通过从堆栈中弹出节点，将节点添加到组件列表中，直到达到根节点。

• 继续进行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

Kruskal算法

在定位删除边不会使图断开连接的上下文中，使用Kruskal算法创建最小生成树（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和Kruskal算法，我们有效地确定了可移除的边缘，同时不会使图形断开连接。这些非关键的边缘对于保留图形的总体结构并避免断开是至关重要的。虽然Kruskal算法创建了一个最小生成树并确定了非关键边缘，但Tarjan算法有助于发现强相关的组件。通过分析边缘连通性，可以确定必须删除的最小边缘数量，以使图形断开连接。为了保持稳健性和有效的通信，在各种领域，包括网络分析、交通规划和基础设施设计中，理解这些重要的非关键边缘是必不可少的。