python - 关节点算法-后边缘识别

Question

我正在研究 Tarjan 的算法，该算法使用 DFS 在图中查找接合点。

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]) 

这一行很容易理解。The earliest discovered vertex connected to u via a backedge = The earliest discovered vertex connected to any of its child nodes(v) via a backedge

好的。现在基本情况？

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

这也很容易理解:如果连接到 u 的顶点 v 已经“以某种方式”访问过(检查与此 elif 对应的 if 条件)并且 v 不是 u 的父节点，则更新 low[u] 以包含 disc[v]。

现在是我的问题:

仅仅因为 v 已经被访问过，所以你知道边 (u,v) 不是树边。但是你怎么能确定它是后缘呢？根据 Tarjan 的算法:

low[u] = min(disc[u], disc[w]) where w is an ancestor of u and there is a back edge from some descendant of u to w.

如果不是树边，可以是前向边、​​后向边或交叉边。要从这 3 种类型的边中识别后边，我们需要每个顶点的开始时间和结束时间。我们不在这里进行任何这些检查。那么我们如何假设我们正在进行的更新确实使用了后缘？

Answer 1

你是对的，有向图中有四种边:树边、后边、前边和交叉边。 Wikipedia有简要定义和解释图。然而，在无向图中只有树边和后边。这是为什么？

• 前向边(上面链接中的 1-8):在有向图中，让我们考虑一个前向边(u，v)。 DFS 算法首先访问 u，然后通过不同的路径(上面链接中的 1-5-6-8)到达 v，从该路径返回，然后考虑edge (u, v) 并说“哦，我已经访问过 v；从发现/完成时间我可以看到 v 是 u 的后代，这意味着 (u, v) 是前向边。”但是在无向图中，边(u, v)在访问节点v 反向 em>，所以它变成了后边(v，u)。
• 交叉边(上面链接中的6-3):通过类似的过程，将在有向图中发现交叉边(u，v)在无向图中反转，成为树边(v, u)。在示例中，我们从节点 3 访问节点 4，然后是节点 6，它成为节点 3 的子节点。