为了账号安全,请及时绑定邮箱和手机立即绑定

无向图中的循环

无向图中的循环

慕村225694 2019-10-17 10:23:47
给定具有n个顶点(| V | = n)的无向图G =(V,E),您如何查找它是否包含O(n)的循环?
查看完整描述

3 回答

?
肥皂起泡泡

TA贡献1829条经验 获得超6个赞

实际上,深度优先(或实际上广度优先)搜索还不够。您需要一个复杂得多的算法。


例如,假设有一个图,它的节点为{a,b,c,d},而边为{(a,b),(b,c),(b,d),(d,c)}的边为(x ,y)是从x到y的边。(看起来像这样,所有边缘都朝下。)


    (a)

     |

     |

    (b)

    / \ 

  (d)  |

   |   |

    \ /

    (c)

然后进行深度优先搜索可能会访问节点(a),然后访问(b),然后访问(c),然后回溯到(b),然后访问(d),最后再次访问(c),并得出一个循环-没有的时候。广度优先发生类似的事情。


您需要做的是跟踪访问过程中的哪些节点。在上面的示例中,当算法到达(d)时,它已经完成了对(c)的访问,但没有完成对(a)或(b)的访问。因此,重新访问完成的节点很好,但是访问未完成的节点意味着您有一个周期。通常的做法是为每个节点上白色(尚未访问),灰色(正在访问后代)或黑色(完成访问)上色。


这是一些伪代码!


define visit(node n):

  if n.colour == grey: //if we're still visiting this node or its descendants

    throw exception("Cycle found")


  n.colour = grey //to indicate this node is being visited

  for node child in n.children():

    if child.colour == white: //if the child is unexplored

      visit(child)


  n.colour = black //to show we're done visiting this node

  return

那么只有当有一个循环(最初所有节点都应该为白色)时,运行visit(root_node)才会引发异常。


查看完整回答
反对 回复 2019-10-17
?
德玛西亚99

TA贡献1770条经验 获得超3个赞

一个没有周期的连通无向图G是一棵树!任何一棵树都恰好具有n − 1条边,因此我们可以简单地遍历图的边列表并计算边。如果我们计算n − 1个边,则返回“是”,但是如果到达第n个边,则返回“否”。这需要O(n)时间,因为我们最多查看n个边。

但是,如果图形未连接,那么我们将不得不使用DFS。我们可以遍历这些边,如果有任何未探索的边通向被访问的顶点,则它具有循环。


查看完整回答
反对 回复 2019-10-17
  • 3 回答
  • 0 关注
  • 684 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信