graph - 如何找到图形的边界？

Question

我想找到一个图的边界，每个顶点都被赋予了它的二维坐标（x，y）。边界路径必须是封闭的多边形并覆盖大部分区域。例如，在图中，边界路径为：1-2-3-4-1

我可以通过首先删除所有死角来做到这一点，然后从最左边的节点开始，然后我将保持“右转”直到我结束了起点。例如，在移除所有死角 (5,8,7) 并继续移除死角 (6) 后，我最终得到节点 1、2、3 和 4。之后，我从最左边的节点开始，即节点 1。我右转到节点 2。在节点 2，我有两个选择：要么去节点 3，要么去节点 4。但我一直右转，所以我会去节点 3。在节点 3，我只有一个选择去节点 4。类似地，在节点 4，我只有 1 个选项可以返回节点 1。因为我最终得到节点 1。我得出的结论是路径是 1-2-3-4。

但是，我想知道在任何现有的图论库中是否有一个“神奇”的函数可以以一种优雅的方式做到这一点？先感谢您。

蒂姆

标签： graphgraph-theoryvertexboundary