关节点算法 - 回溯边识别

Question

我正在学习使用DFS查找图中的关节点，这被称为Tarjan算法。

一些注释： https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

low[] : It is an array of N elements which stores the discovery time of every vertex. It is initialized by 0.

disc[]: It is an array of N elements which stores, for every vertex v, the discovery time of the earliest discovered vertex to which v or any of the vertices in the subtree rooted at v is having a back edge. It is initialized by INFINITY.

现在是算法：

from collections import defaultdict 

#This class represents an undirected graph 
#using adjacency list representation 
class Graph: 

    def __init__(self,vertices): 
        self.V= vertices #No. of vertices 
        self.graph = defaultdict(list) # default dictionary to store graph 
        self.Time = 0

    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
        self.graph[v].append(u) 

    '''A recursive function that find articulation points 
    using DFS traversal 
    u --> The vertex to be visited next 
    visited[] --> keeps tract of visited vertices 
    disc[] --> Stores discovery times of visited vertices 
    parent[] --> Stores parent vertices in DFS tree 
    ap[] --> Store articulation points'''
    def APUtil(self,u, visited, ap, parent, low, disc): 

        #Count of children in current node 
        children =0

        # Mark the current node as visited and print it 
        visited[u]= True

        # Initialize discovery time and low value 
        disc[u] = self.Time 
        low[u] = self.Time 
        self.Time += 1

        #Recur for all the vertices adjacent to this vertex 
        for v in self.graph[u]: 
            # If v is not visited yet, then make it a child of u 
            # in DFS tree and recur for it 
            if visited[v] == False : 
                parent[v] = u 
                children += 1
                self.APUtil(v, visited, ap, parent, low, disc) 

                # Check if the subtree rooted with v has a connection to 
                # one of the ancestors of u 
                low[u] = min(low[u], low[v]) 

                # u is an articulation point in following cases 
                # (1) u is root of DFS tree and has two or more chilren. 
                if parent[u] == -1 and children > 1: 
                    ap[u] = True

                #(2) If u is not root and low value of one of its child is more 
                # than discovery value of u. 
                if parent[u] != -1 and low[v] >= disc[u]: 
                    ap[u] = True    

                # Update low value of u for parent function calls    
            elif v != parent[u]: 
                low[u] = min(low[u], disc[v]) 


    #The function to do DFS traversal. It uses recursive APUtil() 
    def AP(self): 

        # Mark all the vertices as not visited 
        # and Initialize parent and visited, 
        # and ap(articulation point) arrays 
        visited = [False] * (self.V) 
        disc = [float("Inf")] * (self.V) 
        low = [float("Inf")] * (self.V) 
        parent = [-1] * (self.V) 
        ap = [False] * (self.V) #To store articulation points 

        # Call the recursive helper function 
        # to find articulation points 
        # in DFS tree rooted with vertex 'i' 
        for i in range(self.V): 
            if visited[i] == False: 
                self.APUtil(i, visited, ap, parent, low, disc) 

        for index, value in enumerate (ap): 
            if value == True: print index, 

# Create a graph given in the above diagram 
g1 = Graph(5) 
g1.addEdge(1, 0) 
g1.addEdge(0, 2) 
g1.addEdge(2, 1) 
g1.addEdge(0, 3) 
g1.addEdge(3, 4) 

print "\nArticulation points in first graph "
g1.AP() 

g2 = Graph(4) 
g2.addEdge(0, 1) 
g2.addEdge(1, 2) 
g2.addEdge(2, 3) 
print "\nArticulation points in second graph "
g2.AP() 


g3 = Graph (7) 
g3.addEdge(0, 1) 
g3.addEdge(1, 2) 
g3.addEdge(2, 0) 
g3.addEdge(1, 3) 
g3.addEdge(1, 4) 
g3.addEdge(1, 6) 
g3.addEdge(3, 5) 
g3.addEdge(4, 5) 
print "\nArticulation points in third graph "
g3.AP() 

#This code is contributed by Neelam Yadav 

在这个算法中，我们感兴趣的是以下代码行：

low[u] = min(low[u], low[v]) 

这行文字很容易理解。 通过后向边与u相连的最早发现的顶点 = 通过后向边与任何一个子节点(v)相连的最早发现的顶点。

好的，现在是基本条件？

elif v != parent[u]:  
    low[u] = min(low[u], disc[v]) 

这也很容易理解：如果与 u 相连的顶点 v 已经被访问过（检查与此 elif 对应的 if 条件），并且 v 不是 u 的父节点，则将 disc[v] 包括在 low[u] 中以更新它。

现在我的问题是：只因为 v 已经被访问过，你就知道边 (u,v) 不是一条树边。但你怎么能确定它是一条反向边呢？ 根据 Tarjan 算法： low[u] = min(disc[u], disc[w])，其中 w 是 u 的祖先，且存在从 u 的某个后代到 w 的反向边。

如果它不是一条树边，它可以是前向边、反向边或横叉边。要从这 3 种类型的边中识别出反向边，我们需要每个顶点的起始时间和结束时间。我们没有进行任何这些检查。那么我们如何确信我们正在进行的更新确实使用了一条反向边呢？

- user257330

Answer 1

您说得对，在有向图中，有四种类型的边：树边、返祖边、前向边和横叉边。维基百科 给出了简要定义和解释性图表。然而，在无向图中，只有树边和返祖边。这是为什么呢？

正向边（上面链接中的1-8）：在有向图中，考虑一条正向边（u，v）。DFS算法首先访问u，然后通过不同的路径（上面链接中的1-5-6-8）到达v，返回该路径，然后考虑边（u，v），并说：“哦，我已经访问过v了；从发现/完成时间可以看出v是u的后代，这意味着（u，v）是正向边。”但在无向图中，当访问节点v时，边（u，v）将首先以相反的顺序考虑，因此它成为一条反向边（v，u）。

横叉边（上面链接中的6-3）：通过类似的过程，在有向图中的横叉边（u，v）将在无向图中相反地被发现，并成为树边（v，u）。在本例中，从节点3开始，我们访问节点4，然后访问节点6，它成为3的子节点。

- Cătălin Frâncu