Объяснение алгоритма поиска точек сочленения или разрезанных вершин графа

Ответ 1

Поиск вершин сочленения - это применение DFS.

В двух словах,

• Применить DFS на графике. Получить дерево DFS.
• A node, который посещается ранее, является "родителем" тех узлов, которые были достигнуты им и посещены позже.
• Если у какого-либо дочернего элемента node нет пути к любому из предков его родителя, это означает, что удаление этого node сделает этот ребенок не пересекающимся с графиком.
• Есть исключение: корень дерева. Если у него более одного ребенка, то это точка артикуляции, иначе нет.

Точка 3 по существу означает, что это node является точкой сочленения.

Теперь для ребенка этот путь к предкам node будет через задний край от него или от любого из его дочерних элементов.

Все это прекрасно объясняется в этом PDF.

Ответ 2

Я попытаюсь разработать интуитивное понимание того, как работает этот алгоритм, а также дать комментарий псевдокода, который выводит Bi-Components, а также мосты.

На самом деле легко разработать алгоритм грубой силы для точек сочленения. Просто выньте вершину и запустите BFS или DFS на графике. Если он остается подключенным, то вершина не является точкой сочленения, иначе это так. Это будет работать в O(V(E+V)) = O(EV) времени. Задача состоит в том, как это сделать в линейном времени (т.е. O(E+V)).

Точки сочленения соединяют два (или более) подграфа. Это означает, что нет ребер от одного подграфа к другому. Итак, представьте, что вы находитесь в одном из этих подграфов и посещаете его node. По мере того, как вы посещаете node, вы отмечаете его, а затем переходите к следующему unflagged node с использованием некоторого доступного края. Пока вы это делаете, как вы знаете, что находитесь внутри одного и того же подграфа? Проницательность здесь заключается в том, что если вы находитесь в пределах одного и того же подграфа, вы, в конце концов, увидите флаг node через край при посещении unflagged node. Это называется обратным фронтом и указывает, что у вас есть цикл. Как только вы найдете задний край, вы можете быть уверены, что все узлы с помощью этого флага node к тому, который вы посещаете сейчас, являются частью одного и того же подграфа, и между ними нет точек сочленения. Если вы не видели никаких задних краев, все узлы, которые вы посещали до сих пор, являются точками сочленения.

Таким образом, нам нужен алгоритм, который посещает вершины и маркирует все точки между объектом задних ребер, как узлы, находящиеся в настоящее время, как и те же подграфы. Очевидно, что в подграфах могут быть подграфы, поэтому нам нужно выбрать самый большой подграф, который мы имеем до сих пор. Эти подграфы называются Bi-Components. Мы можем реализовать этот алгоритм, присвоив каждому бикомпоненту ИД, который инициализируется как просто счет количества вершин, которые мы посетили до сих пор. Позже, когда мы найдем задние края, мы можем reset бикомпонентный идентификатор до самого низкого уровня, который мы нашли до сих пор.

Мы, очевидно, нуждаемся в двух проходах. В первом проходе мы хотим выяснить, какую вершину мы можем видеть из каждой вершины через задние края, если они есть. Во втором проходе мы хотим посещать вершины в противоположном направлении и собирать минимальный бикомпонентный идентификатор (т.е. Самый ранний предок, доступный от любых потомков). DFS естественно подходит здесь. В DFS мы сначала спускаемся вниз, а затем возвращаемся обратно, поэтому оба вышеуказанных прохода могут быть выполнены в одном обходе DFS.

Теперь без дальнейших церемоний здесь псевдокод:

time = 0
visited[i] = false for all i
GetArticulationPoints(u)
    visited[u] = true
    u.st = time++
    u.low = v.st    //keeps track of highest ancestor reachable from any descendants
    dfsChild = 0    //needed because if no child then removing this node doesn't decompose graph
    for each ni in adj[i]
        if not visited[ni]
            GetArticulationPoints(ni)
            ++dfsChild
            parents[ni] = u
            u.low = Min(u.low, ni.low)  //while coming back up, get the lowest reachable ancestor from descendants
        else if ni <> parent[u] //while going down, note down the back edges
            u.low = Min(u.low, ni.st)

    //For dfs root node, we can't mark it as articulation point because 
    //disconnecting it may not decompose graph. So we have extra check just for root node.
    if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
        Output u as articulation point
        Output edges of u with v.low >= u.low as bridges
    output u.low as bicomponent ID

Ответ 3

Если low потомка u больше, чем dfsnum of u, тогда u называется точкой сочленения.

int adjMatrix[256][256];
int low[256], num=0, dfsnum[256];

void cutvertex(int u){
    low[u]=dfsnum[u]=num++;
    for (int v = 0; v < 256; ++v)
    {
        if(adjMatrix[u][v] && dfsnum[v]==-1)
        {
            cutvertex(v);
            if(low[v]>dfsnum[u])    
                cout<<"Cut Vertex: "<<u<<"\n";
            low[u]=min(low[u], low[v]);
        }
        else{
            low[u]=min(low[u], dfsnum[v]);
        }
    }
}