(5)如首向量的先导向量就是后继向量（即结点数等于4），则输出最后一个矩形、计 算完毕，否则，按更新后的数据从头开始计算。 上述算法中根据状态变量进行四种不同的处理，每种处理可写成公用程序块。现对这四 种处理略加说明。 ①①=0，称并联处理（图5）。输出矩形L,L由首向量AB和y:一y确定。在链表 上酬余和矩形頂点相对应的四个结点，改CD,EF中保留下米的两个结点E、D的指针， 如图5令E指向D。按y坐标大小重新确定新链头。 字原西 图6 图7 图8 ②o=1,称单凹点处理，它有图6所示子种情况：a)(x1,x')∩(x2,x':)∩(xs x')=中，b)(x1,x')门(x2,x'2)中4，（x1,x')∩(x3,x'3)+中，c)(x1,x∩ (x,x)=,(×,x')∩(x,x')≠中。处理时，首先输出矩形L,L由首向量 AB和y1一y确定，然后在链表中删余AB并在(x:,y)和(x':,y)两点中删去与纵坐 标为y的向量里相重合的那个结点（即在链表结点C,D中删去C),其中剩下的一点为划 分点，插入链表。 ③⊙=2、称中空部分处理（图7）。输出矩形L。在链表中删除首向量AB,插入划 分点M(x1,y)和N(x',y),插入内边界链的各结点，修改相应指针，建立一个新的链 表以表示外边界（如图7为MGHIJNC…)。 ④⊙=3，称无凹点处理（图8）。输出两个矩形，由坐标x2、,x':、y2、y:和坐 标x、x',、y,y:确定。然后从链表中删余向量AB、CD和EF上各结点，插入划分 点M(x',y1)和N(x,y)。 最后，这个算法比文献【山的算法估计在查找、计算上会节省些，并且也作了并联处 理。但是，这个算法对X坐标相同的并联型凹点没有进行处理，因此还不能对所有的图形都 求得最优解答。 参芳文献 〔1)小山田： “LSIブ”一卜夕一夕R夕)刀最小分割”《情报处理》VoL.16. No.7. (2)J.A.Bondy and U.S.R.Murty:"Graph Thery with A pplications" .,1976. 147如首 向最的 先导 向量就是后继 向量 即结 点数等于 ， 则输 出最后一个矩形 、 计 算完毕 ， 否 则 ， 按 更新后 的 数据 从头 开 始计 算 。 上述算法中根 据状态 变 量进行 四 种不 同的 处理 ， 种处理略加说 明 。 每种 处理可 写 成公 用程序块 。 现对这 四 ① 。 ， 称 并 联 处 理 图 。 输 出矩 形 ， 由首 向量 和 一 确定 。 在 链表 上姗 杂和 矩 形厦 点 相 对应 的 四 个结 点 ， 改 ， 中保 留下来的 两个结 点 、 的 指针 ， 如图 令 指 向 。 按 坐标大 小重 新 确定 新链 头 。 月 、产 ﹄ 、 尹 图 人 ‘ 、 习 ， 薛习 ， 匕 己 目 ‘ 图 图 ② 。 ， 称 单 凹 点 处 理 ， 它有 图 所 示 冬种 清况 ，， 尹， 门 ， ‘ 门 产 小 ， 工 ， ， ’ 卜 一一夕 尹， 门 ， ‘ 子 译， ， 产， 门 ， 尹 斗 小 ， ， 尸 门 · ， 尹 门 ， 尸 笋 中 。 处 理时 ， 首 先输 出矩 形 ， 由首 向 里 和 一 确定 ， 然 后在 链 表 中删 余 并在 ， ， 和 产 ， 两点中删去 与纵坐 标为 的 向量 里 相 重 合 的 那 个结 点 即在 链 表结 点 ， 中删 去 ， 其 中剩下的 一 点为划 分 点 ， 插 入 链表 。 一 一寸 ③ 。 、 称 中空 部分处理 图 。 输 出矩 形 。 在 链 表 中删 除首 向量 ， 插入 划 分点 ， 和 产， ， 插 入 内边界链 的 各结 点 ， 修改 相应指 针 ， 建立一个新 的链 表 以 表示外 边界 如 图 为 … … 。 ④ 。 二 ， 称 无 凹点处理 图 。 输 出两个矩 形 ， 由坐 标 、 了 、 、 和坐 一 于 ， 一 ‘ 一今 标 ’ ‘ 、 ， 确定 。 然后 从链 表 中 删 余向量 、 和 上 各结点 ， 插 入划 分 点 尹 ， 和 ， ， 。 最后 ， 这个算法 比文 林川 的算法估 计 在 查 找 、 计 算上 会节 省些 ， 并且 也作 了并 联处 理 。 但是 ， 这个算法对 坐 标 相同的 并联 型 凹点 没 有进 行处理 ， 因此 还 不 能对所 有的图形都 求得最优解答 。 参 考 一 泛 献 〔 〕 小 山 田 “ 了 ” 一 卜 夕 一 夕 川 夕 ， 刀 最 小 分割 ” 《 情 报 处 理 》 〔 〕 “