铰接点算法-后缘识别

Question

我将介绍Tarjan的算法，用于使用DFS在图中找到连接点。

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

好的。现在是基本条件？

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

这也很容易理解：如果连接到u的顶点v已经被访问过（检查与此elif对应的If条件）“不知何故”，并且v不是u的父级，那么更新low[u]以包括disc[v]。

现在我的问题是：

Answer 1

在有向图中有四种边：树边、后边、前边和交叉边，这是正确的。维基百科有简短的定义和一个解释图。然而，在无向图中，只有树和后边。这是为什么？

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