※ 引述《tool11 (:))》之铭言： : 题目 在这 : http://www.postimage.org/image.php?v=aV1g5Cz0 : 以n-1条线结束 : 所以为 6 条 : 为(0,1) (1,2) (0,3) (0,4) (2,6) (4,5) : 这应该算是a小题吧 : 那b小题是指变成双向的吗? : 那这样其实结果不也是跟第一题一样吗 (a) 我依Prim's algorithm结果是 (以下为依序建立) (0,3) (2,3) (1,2) (0,4) (2,6) (5,6) 如果权重没看错 , 一开始 (0,1) (0,3) (0,4) ,权重分别为 16 12 18 不会选择到(0,1)才对 , 是(0,3) 依照Prim's algo " 由现有的顶点集合 , 去选择最小的连结边 " (b) 由於 "一个顶点限制最多两个连结" 那麽刚刚依照Prim's algo所建立的图形 , 在顶点 2 就产生问题 (branch > 2) 因为有 (2,3) (2,6) (1,2) 甚至在此条件下 , 顶点 3 , 也连带发生问题 为了避免这样情形发生 , 且在branch <= 2之下,产生另一个图形 (以下为依序建立) (0,3) (2,3) (1,2) (0,4) (4,5) (5,6) 手头上没书,也有一阵子没碰了 , 有错在讨论看看:) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.119.162.51