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

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 算法专门针对最小化此类违规行为。

Answer 3

如果图形是在欧几里得空间中绘制的，则不能这样做，因为正如在此答案中指出的那样，您可能会违反Triangle Inequality。

通常，您可以通过使用不同的颜色（即通过将权重映射到颜色图）或通过使用不同的边缘厚度（即通过将权重映射到厚度比例）来直观地表示边缘的权重。

Answer 4

好的，我找到了一个python库，它为我创建了一个图形图像:) 我可以为边缘赋予权重，例如属性：边缘的权重。在dot中，重量越重，边缘越短、越直、越垂直。