Как найти коннекторы на графике?

Я немного борюсь здесь, потому что, честно говоря, мой мозг поджарен, и я не знаю, что делать.

Моя задача — найти коннекторы в неориентированном невзвешенном графе.

Задача утверждает, что: В неориентированном графе вершина v является соединителем, если есть по крайней мере две другие вершины x и w, для которых каждый путь между x и w проходит через вершину v.

Не поймите меня неправильно, я понимаю, что это значит, но я безнадежно делаю это. Когда я просматриваю этот график (рекомендуется использовать DFS), что именно я должен делать?

Я просто хочу быть на правильном пути, чтобы закончить это.

Любая помощь высоко ценится!


java graph undirected-graph breadth-first-search depth-first-search
person Filip Kłosiewicz    schedule 03.12.2019    source источник
comment
Я думаю, что для того, чтобы быть соединителем, вершина должна быть соединителем для своих непосредственных соседей, поэтому: для каждой вершины v в графе получить всех ее соседей. Используйте DFS, чтобы получить все пути между каждой парой соседей n1, n2. Если все полученные пути проходят через v, то v является соединителем между n1, n2.   -  person c0der    schedule 05.12.2019

Ответы (1)


arrow_upward
1
arrow_downward

Соединитель, который вы описываете, представляет собой вершину разреза (или точку сочленения): https://en.wikipedia.org/wiki/Biconnected_component)

Чтобы найти все точки сочленения в неориентированном графе, мы можем использовать модифицированный алгоритм DFS. Общая идея состоит в том, чтобы запустить поиск в глубину на графе, пометив каждый узел n двумя переменными: целым числом LOW(n) ​​и целым числом dfs(n). Если сосед узла v имеет значение LOW(w) >= dfs(v), узел v является точкой артикуляции. Псевдокод описан ниже:

Execute DFS(v)
When a vertex v is first discovered, LOW(v) = dfs(v) 
For each of v’s neighbors w
    if w is undiscovered 
        execute DFS(w)
        LOW(v) = min of {LOW(v), LOW(w)}
        if LOW(w) ≥ dfs(v), v is connector!!!!!Store it.
    else if w is v’s parent, do nothing
    else (w is not v’s parent but has already been discovered)
        LOW(v) = min of {LOW(v), dfs(w)}

Время выполнения этого алгоритма такое же, как у базового алгоритма DFS: O(V+E), где V — количество вершин в графе, а E — количество ребер в графе.

person Stella Wang    schedule 04.02.2020