首页 > 其他 > 详细

支配树

时间:2019-01-28 13:21:39      阅读:141      评论:0      收藏:0      [点我收藏+]

写在前面:

  学习笔记

  非原创部分标明出处

 

  • 支配树

  对于一棵树,我们规定一个起点s,从s点到图上另一个点v可能存在很多条路径

  如果对于是s→v的任意一条路径中都存在一个点p,那么我们称点v为p的支配点(也可以称作是s→v的必经点)

  s点是树的根节点,不讨论它的支配点,也不讨论它当支配点

——https://www.cnblogs.com/ZeonfaiHo/p/6594642.html

技术分享图片

  如图

    3是4,5,8的支配点

    1是6的支配点

 

  类比无向图中的割点[?]Tarjan算法

  最明显的区别是需要规定一个根节点

 

支配树

原文:https://www.cnblogs.com/Antigonae/p/10329387.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!