algorithm - 将无向循环图投影到坐标平面上

Question

我有一组房间，每个房间都通过主要方向(北、南、东、西)与一个或多个其他房间相连。这些房间的连接方式是，如果 A 在 B 的西边，则 B 在 A 的东边；因此无向图。现在我需要获取这些房间的集合并将它们绘制在坐标平面上。所有边必须平行于 X 或 Y 轴。

我尝试了一些不同的方法，但我认为目前为止最有效的方法如下:

1. 找到“中心”并将其指定为 (0,0)(到每个其他房间的最短路径长度总和最小的房间)。我不知道这是否真的有必要，但它使输出居中更容易。
2. 从中心 C 走出去，对于遇到的每个房间 R，分配一个坐标(X，Y)，其中 P 是连接 C=>R 的路径，导致坐标平面上的最大位移，X 是净水平沿 P 的移动，Y 是沿 P 的净垂直移动。

假设方向向量如下: 北 = [0,1] 南 = [0,-1] 东 = [1,0] 西 = [-1,0]

Answer 1

这听起来像是一个合理的方法。我认为有一整套方法相当于对图进行拓扑排序，然后按顺序处理节点，这样对于每个节点你都有空间放置它，因为拓扑顺序小于它的节点都是到它的一侧。

另一种查看拓扑排序的方法不是从中心开始工作，而是形成一个有向图，其中每个链接都是从北到南或从东到西。按照拓扑排序，您知道在放置节点时，到目前为止还没有位于其北部或西部的节点，因此您可以根据其东部和南部邻居分配其坐标。

如果您希望像以前一样将节点放置在原点周围，您可以在之后更改它们，向每个坐标值添加一个常量以根据需要移动它们。