绘制一个图，其中顶点之间的距离对应于边权重

Question

当我给他一个加权图并且顶点之间的边权重指向顶点之间的距离时，是否有一种算法可以给我图中顶点的坐标？

就像是：

public _ArrayOfCoordinatesForVertices_ **super_hyper_algorithm**(weighted_graph){  
     return _foo_;  
}

Answer 1

这通常是不可能的：想象一个具有 3 个节点 n1、n2 和 n3 的图。

现在考虑以下距离：

n1-n2: 4
n1-n3: 1
n2-n3: 1

（这违反了三角形不等式）。

Answer 2

您所指的称为多维缩放（MDS），现在您应该找到大量实现，并且您知道如何搜索它。

就像其他人所说的那样，在某种程度上，如果不违反一些约束（点之间的距离），就不可能绘制出完美的图形。MDS 算法专门针对最大限度地减少此类违规行为。