按负边拆分无向图

Question

想知道是否存在一种算法可以在给定负边的情况下拆分无向连通分量图。

本质上，负边中提供的顶点应该是不可到达的。

Answer 1

如果您希望图形的连通分量仅包含正边，则首先从图形中删除所有负边。然后运行一个 DFS (depth-first-search) 来找到所有连接的组件。

这是算法。

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

按负边拆分无向图

Split undirected graph by negative edges

graph-theory

graph

connected-components