Я прохожу алгоритм Тарьяна для нахождения точки сочленения в графе с использованием 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])
Эта строка проста для понимания.Самая ранняя обнаруженная вершина, соединенная с u через задний край = Самая ранняя обнаруженная вершина, соединенная с любым из ее дочерних узлов (v) через задний край
OK.Теперь базовое условие?
elif v != parent[u]:
low[u] = min(low[u], disc[v])
Это также легко понять: если вершина v, связанная с u, уже посещена (проверьте условие if, соответствующее этому elif), «как-то», и v не является u'sparent, затем обновите low [u], чтобы включить диск [v].
СЕЙЧАС МОЙ ВОПРОС:
Только потому, что v уже посещен, вы знаете, что край(u, v) не является ребром дерева.Но как можно точно сказать, что это задний край?В соответствии с алгоритмом Тарьяна:
low [u] = min (disc [u], disc [w]), где w является предком u и существует обратный край от некоторого потомка u кw.
Если это не край дерева, это может быть передний край, задний край или поперечный край.Чтобы идентифицировать задний край из этих трех типов ребер, нам нужно время начала и время окончания для каждой вершины.Мы не делаем никаких этих проверок здесь.Тогда как мы можем предположить, что обновление, которое мы делаем, действительно использует задний край?