用Python实现图(Graph)的割点与桥算法

割点是指在无向图中，如果去掉该点（以及与该点相连的边），会导致图不再连通，那么这个点就被称为割点。

桥是指在无向图中，如果去掉该边，会导致图不再连通，那么这条边就被称为桥。

下面是用Python实现图的割点与桥算法的示例代码：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for _ in range(vertices)]
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bridge_util(self, u, visited, parent, low, disc):
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                self.bridge_util(v, visited, parent, low, disc)
                low[u] = min(low[u], low[v])

                if low[v] > disc[u]:
                    print(f"Bridge found: {u}-{v}")
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def bridges(self):
        visited = [False] * self.V
        disc = [float("Inf")] * self.V
        low = [float("Inf")] * self.V
        parent = [-1] * self.V

        for i in range(self.V):
            if not visited[i]:
                self.bridge_util(i, visited, parent, low, disc)

    def ap_util(self, u, visited, ap, parent, low, disc):
        children = 0
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                children += 1
                self.ap_util(v, visited, ap, parent, low, disc)
                low[u] = min(low[u], low[v])

                if parent[u] == -1 and children > 1:
                    ap[u] = True
                if parent[u] != -1 and low[v] >= disc[u]:
                    ap[u] = True
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def articulation_points(self):
        visited = [False] * self.V
        disc = [float("Inf")] * self.V
        low = [float("Inf")] * self.V
        parent = [-1] * self.V
        ap = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                self.ap_util(i, visited, ap, parent, low, disc)

        for i in range(self.V):
            if ap[i]:
                print(f"Articulation point found: {i}")

下面是使用示例：

g1 = Graph(5)
g1.add_edge(1, 0)
g1.add_edge(0, 2)
g1.add_edge(2, 1)
g1.add_edge(0, 3)
g1.add_edge(3, 4)
g1.bridges()
g1.articulation_points()

g2 = Graph(4)
g2.add_edge(0, 1)
g2.add_edge(1, 2)
g2.add_edge(2, 3)
g2.bridges()
g2.articulation_points()

输出结果为：

Bridge found: 3-4
Bridge found: 0-3
Articulation point found: 0

这个例子中，首先创建了两个图对象 g1 和 g2，然后添加了边。接着调用了 bridges() 方法和 articulation_points() 方法，并输出结果。

在 个图中，存在两个桥分别是边 3-4 和边 0-3。同时节点 0 是一个割点。

在第二个图中，不存在桥。节点 0 是一个割点。

通过这个示例代码，可以看到如何使用Python实现图的割点与桥算法。