平面点集的最小生成树

aimisiyou

1.算法简单描述

1).输入：一个加权连通图，其中顶点集合为V，边集合为E；

2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；

3).重复下列操作，直到Vnew = V：

a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

aimisiyou

(defun fp ()
    (setq sn (ssget ":N" '((0 . "point"))))
    (setq i 0 n (sslength sn) plst nil)
    (while (< i n)
        (setq plst (cons (cons (+ i 1) (cdr (assoc 10 (entget (ssname sn i))))) plst))
        (setq i (+ i 1))
    )
   (reverse plst)
)
(defun mindist (alst blst)
  (setq dlst nil)
  (foreach a alst
       (foreach b blst
            (setq dlst (cons (list (car a) (car b) (distance (cdr a) (cdr b)))  dlst))
        )
  )
  (setq qlst (car (vl-sort dlst '(lambda(a b) (< (last a) (last b)) ) )))
  qlst
)
(defun c:tt ()
   (setq ptlst (fp))
   (setq vlst (list (car ptlst)) rlst (cdr ptlst))
   (while (not (null rlst))
          (setq qlst (mindist vlst rlst))
          (command "line" (cdr (assoc (car qlst) vlst)) (cdr (assoc (cadr qlst) rlst)) "" )
          (setq vlst (cons (assoc (cadr qlst)  rlst) vlst))
          (setq rlst (vl-remove (assoc (cadr qlst)  rlst) rlst))
   )
)

ynhh

谢谢大师
感觉象最短线路