Найти группы точек сочленения

Ответ 1

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

Хотя язык программирования не указан, пожалуйста, позвольте мне использовать пример python.

Когда вы выполняете поиск точек сочленения, самым известным методом является алгоритм Tarjans. Я думаю, что все, кто это читает, знают это, поэтому я пропущу его как функцию, если вы не против, где вы можете найти в https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in- a-graph/.

class Graph:
   #From www.geeksforgeeks.org
def worker(g, prefix, arr, u):

    container = g.graph[u]
    if u in g.AP():
        print prefix
        arr.append([prefix])
        del g
    else:
        for i in container:
            if str(i) not in prefix.split(' '):
                new_prefix = prefix + ' ' + str(i)
                new_g = copy.deepcopy(g)
                new_g.combineNode(u, i)
                if len(new_g.graph) > 1:
                    worker(new_g, new_prefix, arr, i)

struct = {
    0:[1,12,13,14,15],
    1:[2,12,14,15],
    2:[3,4,5,14],
    3:[4],
    4:[5,6],
    5:[6,9],
    6:[7,8,9],
    7:[8,10,11],
    8:[9,10,11],
    9:[10],
    10:[11],
    12:[15],
    13:[14,15]
} 
g1 = Graph (total)

for key,value in struct.iteritems():
    for child in value:
        g1.addEdge(key, child)

result = []
for i in range(0, total):
    print 'Remove root ' + str(i)
    worker(g1, str(i), result, i)
print result

Я пишу это в случае, если только наименьшая длина группы разделит график. Как, скажем, (4, 5), если это уже точка доступа, любые точки, соединяющиеся с ними, также должны быть AP.

На всякий случай, кому-то нужен полный тестовый код. https://gist.github.com/MichaelKHTai/c438fd0911d0584be1e37f1fd1599b7e

Кроме того, его следует оптимизировать, пропуская дублированную группу узлов, например (4,5) и (5,4).

Ответ 2

Один из подходов состоит в том, чтобы найти "2-компонентные компоненты" вашего графа.

2-связный граф - это граф, который связан и не содержит точек сочленения.

Любой простой граф можно разбить на несколько 2-связных подграфов.

Первый пример:

На приведенном выше графике представлены 2-соединенные компоненты:

• 4–2 3–4 3–1 2–3 1–2
• 8-9
• 8–5 7–8 5–7
• 6–0 5–6 1–5 0–1
• 10-11

Второй пример:

Каждый цвет соответствует 2-компонентному компоненту. Разноцветные вершины являются вырезанными вершинами (точками сочленения) и, таким образом, принадлежат нескольким 2-связным компонентам.

Я думаю, что каждый компонент является ответом на ваш вопрос. Вы можете использовать алгоритм Тарьяна, чтобы найти эти компоненты. Его временная сложность составляет O (| V | + | E |) или O (n + m).

time = 0
function DFS(vertex, adj[][], low[], disc[], parent[], visited[], V, stack)
    disc[vertex]=low[vertex]=time+1
    time = time + 1
    visited[vertex]=true
    child = 0
    for i = 0 to V
        if adj[vertex][i] == true
            if visited[i] == false
                child = child + 1
                push edge(u,v) to stack
                parent[i] = vertex
                DFS(i, adj, low, disc, visited, V, time, stack)
                low[vertex] = minimum(low[vertex], low[i])
                if parent[vertex] == nil AND child > 1
                    while last element of stack != (u,v)
                        print last element of stack
                        pop from stack
                    print last element of stack
                    pop from stack
                if parent[vertex] != nil AND low[i] >= disc[vertex]
                    while last element of stack != (u,v)
                        print last element of stack
                        pop from stack
                    print last element of stack
                    pop from stack
            else if parent[vertex] != i AND disc[i] < low[vertex]
                low[vertex] = disc[i]
                push edge(u,v) to stack

fuction biconnected_components(adj[][], V)
    for i = 0 to V
        if visited[i] == false
            DFS(i, adj, low, disc, parent, visited, V, time, stack)
            while stack is not empty
                print last element of stack
                pop from stack 

Источники:

https://www.geeksforgeeks.org/biconnected-components/

https://en.wikipedia.org/wiki/Biconnected_component

https://www.hackerearth.com/practice/algorithms/graphs/biconnected-components/tutorial/