computer-science - 查找图的外边缘

Question

找到图形外边缘的最佳方法是什么？

例如，此图上的红色边：

我不知道这个算法是否有名字。这个名字足以帮助我在谷歌上找到一些东西。

Answer 1

我希望我没有误解这个问题，但我认为没有答案，除非你有一个特定的平面嵌入图。

即使对于大多数平面图¹，您也可以重新排列节点，以便不同的边位于“外部”。请参阅查找平面图（几何形状）的边界（边界）边。您的示例绝对不是平面的。

如果您有嵌入，那么您正在寻找的内容与一组点的凸包有关。这是 Dobb 博士关于它的文章http://www.drdobbs.com/architecture-and-design/building-the-convex-hull/201806315。“礼品包装”算法很容易实现。

但是，给定图嵌入的边界可能不是凸的，因此您必须修改算法以重新计算凸包中不是边的部分。（您可以将其称为“收缩包装”算法）。

注 1：我能想到的唯一一类在平面中具有独特嵌入的图是循环图。很容易有其他人。（编辑：至少在边界方面是唯一的，您可以顺时针或逆时针嵌入一个循环）

Answer 2

图只是一组顶点和一组边。图没有固有的“外边缘”概念。例如，在您作为示例给出的图中，形成五边形的边可以向内移动。