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

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

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

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