|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- 判定图中是否存在初级回路的O(n)时间算法 (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=29551) |
|
-- 作者：Logician -- 发布时间：3/30/2006 2:53:00 AM -- 判定图中是否存在初级回路的O(n)时间算法 首先假定图是用邻接表表示的。 直接对图作DFS，如果搜索时遇到以前访问过的顶点，则直接返回False。 为了判断G是否被遍历完，我们可以做一个小trick： 用一个变量k记录最小的未被访问过顶点号。 初始时，k=1，（假定G中顶点是从1开始编号的）。 每次访问一个顶点时，比较这个顶点的编号与k，如果不相等，则不修改k。 如果正好相等，就让k往上增加大下一个没有被访问过顶点号。 当k>n时，返回True。 设置变量k是为了避免当G不连通时，需多次扫描全图（从而导致时间复杂度增至Θ(kn)，k为连通分支数）。
|
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
56.641ms |