Поиск в артикуляции Очки

Question

Я читал некоторые учебники по поиску точек сочленения в графе и наткнулся на этой

Выполняет поиск в глубине в G, начиная с любого узла. Пусть T будет деревом, сгенерированным поиском глубины, и для каждого узла v графика пусть prenum [v] будет числом, заданным поиском.

траверс дерева Т в postorder. Для каждого посещенного узла v вычислите наименьший [v] как минимум prenum [v] prenum [w] для каждого узла w, такого как , что существует ребро (v, w) в G, которое не имеет соответствующего ребра в T . низкая [х] для каждого ребенка х V в Т.

Articulation точки в настоящее время определяется следующим образом. Корень T является точкой сочленения G тогда и только тогда, когда он содержит более одного ребенка. Узел v, отличный от коренья T, является точкой шарнира G тогда и только тогда, когда v имеет дочерний элемент x , такой, что самый низкий [x] ≥ prenum [v].

, но я не очень понимаю, как вычислить самый низкий [х]. Может ли кто-нибудь сделать это более понятным? Спасибо!

Answer 1

Шаг 2, в псевдокоде:

def visit(v): 
    lowest[v] = prenum[v] 
    for w in nodes: 
     if v is the parent of w in T: 
      visit(w) 
      lowest[v] = min(lowest[v], lowest[w]) 
     elif w is connected to v in G: 
      if w is not the parent of v in T: 
       lowest[v] = min(lowest[v], prenum[w]) 

Answer 2

Итерационный псевдокод версия, которая сочетает в себе шаги 1 и 2:

i = 0 
prenum[1] = lowest[1] = i = i + 1 
S = EMPTY STACK 

for each edge e connected to nodes[1]: 
    push edge e onto S 

while S is not empty: 
    peek at edge e on S 
    let (u,v) = e such that prenum[u] <= prenum[v] or prenum[v] is undefined 
    if e is unvisited 
    mark e as visited 
    if prenum[v] is undefined 
     mark e as parent of v 
     prenum[v] = lowest[v] = i = i + 1 
     for each edge e' connected to nodes[v] except e: 
     push edge e' onto S 
    else 
     pop e from S 
     lowest[v] = min(lowest[v], prenum[u]) 
    else 
    pop e from S 
    if e is marked as parent of v 
     lowest[u] = min(lowest[u], [lowest[v])