algorithm - 寻找可能由 Dijkstra 提供的算法

Question

我正在寻找一种将节点分布在平面上的算法，以使边缘的大小都相同。我想是 Dijkstra 的，但我不记得了。有人听说过这个算法吗？

Answer 1

一般来说，这是不可能的。实际上，您想要类似于平面平铺中的有限图片的东西。

有一些简单的情况 - 正多边形和一些包含连接多边形的图，但即使是像 4 点（四面体）的完整图这样简单的东西也是不可能的。

如果您想要尝试平衡不可能的约束的东西，请尝试使用graphviz及其neato 程序。

Answer 2

好吧，如果您想创建具有此类属性的任何图形，那么有许多图形可以帮助您，例如：一条线、一个环、一棵树等.. 但在这里，您是决定什么的人要包含或排除的边。

如果您有某个图，并且您希望所有边的大小相同，那么这是不可能的（由于某些情况）-例如：超过 3 个节点的完整图，具有一个主节点和多个节点的星形拓扑5个奴隶，直接靠近的奴隶是邻居。[相信其他帖子中的案例会告诉你更多]

一种特殊情况，给定一个图 $G(V,E)$，绘制 $G$ 使得 $e \in E$ 中的每条边的长度小于一个单位。这是一个 NP-Hard 问题。[即你无法判断任意图$G$是否为单位盘图]