通过切割2条边来分割图

Question

我有一个无向图。我希望以这样的方式对其进行分区，以便识别实际上有 2 个将它们连接到主网络的桥的子图。不需要进一步细分这些子图。想象一下只有 2 条与外界相连的道路的村庄。我想要整个村庄的网络，并且不想进一步分割它。有人可以指出我的方向吗：

1. 我正在寻找的算法 - 因为我确定这是一个已知问题。
2. 任何包含上述算法实现的 Java 或 jvm 语言或 Python 语言的库。 谢谢

Answer 1

对图执行深度优先搜索 (DFS)：

• 当你第一次访问一个顶点时，给它一个唯一的、递增的索引号；
• 每条边要么是树边（如果它到达未访问过的顶点），要么是 cotree（后）边（如果它到达已经访问过的顶点）。
• 随着深度优先搜索回溯，跟踪 DFS 内后代子图中可到达的最低索引。

如果你发现一个树边

(U -> V)

，其中在 DFS 树中由其后代组成的子图中存在一个协树边

(W -> U)

（即

V

是

W

的 DFS 祖先），并且没有该子图中连接到

U

（或任何祖先）的其他边

U

），然后从图中删除这两条边将断开以

V

为根的子图。

在 Python 中，识别可以删除以断开图形连接的边对：

from __future__ import annotations


UNVISITED_EDGE = None
TREE_EDGE = True
COTREE_EDGE = not TREE_EDGE


class Vertex:
    def __init__(self, name):
        self.name = name
        self.adjacent = []
        self.dfs_index = -1
        self.low_point = -1
        self.parent_edge = None

    def update_parent(self, edge, dfs_index):
        self.parent_edge = edge
        self.dfs_index = dfs_index
        self.low_point = dfs_index

    def __str__(self):
        return f"{self.name}"


class Edge:
    def __init__(self, vertex1, vertex2):
        self.vertex1 = vertex1
        self.vertex2 = vertex2
        self.dfs_edge_type = UNVISITED_EDGE
        self.low_point_edges = set([self])
        vertex1.adjacent.append(self)
        vertex2.adjacent.append(self)

    def other_end(self, vertex):
        assert vertex in (self.vertex1, self.vertex2)
        return self.vertex2 if vertex == self.vertex1 else self.vertex1

    @property
    def dfs_root(self):
        v1, v2 = self.vertex1, self.vertex2
        if self.dfs_edge_type == TREE_EDGE:
            # Tree edge connects earlier to later vertex
            return v2 if v1.dfs_index > v2.dfs_index else v1
        else:
            # Cotree edge connects later to earlier vertex
            return v1 if v1.dfs_index > v2.dfs_index else v2

    @property
    def dfs_leaf(self):
        v1, v2 = self.vertex1, self.vertex2
        if self.dfs_edge_type == TREE_EDGE:
            # Tree edge connects earlier to later vertex
            return v1 if v1.dfs_index > v2.dfs_index else v2
        else:
            # Cotree edge connects later to earlier vertex
            return v2 if v1.dfs_index > v2.dfs_index else v1

    def update_low_point(self, dfs_index):
        root = self.dfs_root
        if dfs_index < root.low_point:
            root.low_point = dfs_index
            if root.parent_edge is not None:
                root.parent_edge.low_point_edges.clear()
                root.parent_edge.low_point_edges.update(self.low_point_edges)
        elif dfs_index == root.low_point:
            if root.parent_edge is not None:
                root.parent_edge.low_point_edges.update(self.low_point_edges)

    def __str__(self):
        if self.dfs_edge_type is UNVISITED_EDGE:
            edge_type = "-"
        elif self.dfs_edge_type is TREE_EDGE:
            edge_type = "Tree"
        else:
            edge_type = "Cotree"
        return f"({self.vertex1}, {self.vertex2}, {edge_type})"


class Graph:
    def __init__(self, vertex_names, edges):
        self.vertices = {
            name: Vertex(name)
            for name in vertex_names
        }

        self.edges = [
            Edge(self.vertices[name1], self.vertices[name2])
            for name1, name2 in edges
        ]

    def depth_first_search(self):
        dfs_index = 0
        stack = []
        for root in self.vertices.values():
            if root.dfs_index >= 0:
                continue
            root.dfs_index = dfs_index
            dfs_index += 1
            stack.extend(reversed(root.adjacent))

            while stack:
                edge = stack[-1]
                if edge.dfs_edge_type is UNVISITED_EDGE:
                    v1, v2 = edge.vertex1, edge.vertex2
                    if v1.dfs_index > v2.dfs_index:
                        v1, v2 = v2, v1

                    # Unvisited edge
                    if v1.dfs_index == -1:
                        # Unvisited vertex
                        edge.dfs_edge_type = TREE_EDGE
                        v1.update_parent(edge, dfs_index)
                        dfs_index += 1
                        stack.extend(reversed(v1.adjacent))
                    else:
                        # Visited vertex, cotree (back) edge
                        edge.dfs_edge_type = COTREE_EDGE
                        edge.update_low_point(v1.dfs_index)
                        _ = stack.pop()
                else:
                    if edge.dfs_edge_type is TREE_EDGE:
                        edge.update_low_point(v2.low_point)
                    _ = stack.pop()


graph = Graph(
    ["A", "B", "C", "D", "E", "F"],
    [
        ("A", "B"),
        ("A", "C"),
        ("A", "D"),
        ("B", "C"),
        ("B", "D"),
        ("C", "D"),
        ("A", "E"),
        ("A", "F"),
        ("E", "F"),
    ]
)
graph.depth_first_search()
for edge in graph.edges:
    if (
        edge.dfs_edge_type == TREE_EDGE
        and len(edge.low_point_edges) == 1
        and edge.dfs_root.dfs_index == edge.dfs_leaf.low_point
    ):
        print(edge, *edge.low_point_edges)

哪个输出：

(A, E, Tree) (A, F, Cotree)

删除这些边会断开包含顶点

E, F

的子图与包含顶点

A, B, C, D

的子图。