图的O（m + n）时间算法

我刚刚开始学习关于图的知识，似乎无法为此问题想出一个算法，甚至不知道从哪里开始。我将衷心感谢您的帮助！对于给定的连通图G =（V，E），设计O（n + m）时间算法以找到节点v∈V，因此移除v及其所有相邻边将不会断开连接G.图的O（m + n）时间算法

预先感谢您！

来源

2017-02-12 CSstudent

执行图的宽度优先搜索。找到的最后一个节点可以在不断开图形的情况下被移除。

证明：BFS生成图的生成树，找到的最后一个节点始终是该树的叶。移除生成树的树叶不会断开树，并留下剩余顶点的生成树。

来源

2017-02-12 23:01:11

这只是一个局部解决方案 - 在BFS树中可以有更多的关节点，删除该关节点将从该树的主体断开以该顶点为根的子树。 – MT0

@ MT0我不太清楚你的意思。您是否误解了“将断开G”而不是“不会断开G”的问题？ –

如果您找到所有关节点，那么任何非关节点都将成为双连通组件的一部分，如果它们被移除，则不会断开图形。执行BFS并取走叶子将无法找到图中的所有非关节点。 – MT0

一个顶点可以被移除（没有断开的曲线图的其余部分），如果：

它不是一个铰接点;或
它终止图中的路径，该路径只在一端连接;或
它是图中唯一的顶点。

一种算法参见Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378识别铰接点：

执行图表上的深度优先搜索 - 下面是一个递归DFS算法一些伪代码：

procedure RecursiveDFS (u) { 
    mark u as visited 
    u.index = u.lowPoint = ++global_index 
    if ( (u is the root and has zero connected edges) 
     or (u is not the root and has one connected edge)) { 
    mark u as a leaf 
    } 
    for each (edge e connected to u) { 
    if (e is unvisited) { 
     mark e as visited 
     let e = {u , v} 
     if (v is unvisited) { 
     mark e as tree edge 
     RecursiveDFS (v) 
     if (v.lowPoint < u.lowPoint) 
     { 
      u.lowPoint = v.index 
     } else { 
      mark u as an articulation-point 
     } 
     } else { 
     mark e as cotree edge 
     if (v.index < u.lowPoint) 
     { 
      u.lowPoint = v.index 
     } 
     } 
    } 
    } 
}

这将访问每个顶点和每个边一次O(m+n)，并且如果在给定顶点处存在以该顶点为根的DFS的子树（其不具有从该子树发出的共树（后）边），则将顶点标记为关节点连接到给定的verte的祖先X。

特殊情况是根顶点（您开始DFS的地方），它始终会被标记为关节点（因为它没有祖先供子树连接） - 相反，您应该检查根顶点只有一个相邻的树边和一个或多个相邻的共树（后）边（并且是双连通分量的一部分）。

顶点终止的路径要么是：

的DFS树的叶顶点（正好与一个连接树边缘，从DFS树中的父，并且零连接共树边缘） ;或者
DFS树的根顶点一个相邻的树边和零个相邻的共树（后）边。

来源

2017-02-14 15:30:29 MT0

图的O（m + n）时间算法

回答

相关问题