Разбить неориентированный граф по отрицательным ребрам

Question

Интересно, существует ли алгоритм для разделения графа неориентированного связного компонента по заданным отрицательным ребрам.

По существу вершины, представленные в отрицательных ребрах, должны быть недоступны.

Answer 1

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

Вот алгоритм.

Begin 
    For each edge e in graph G, if e is negative, remove e from G.

    For each vertex v in G, do:
        If v is not labeled as visited
            Let c be a new component, and add c to set C.
            Call procedure DFS(v, c) to find one component of positive edges only.
        End If
    End For

    The set C contains all the connected components consisting of positive edges only.
End

Procedure DFS(v, c)
    Add v to c, and label v as visited.
    For each edge from v to w, do
        If vertex w is not labeled as visited then
            Call DFS(G,w)
        End If
    End For
End Procedure