在二维空间中可视化加权图（其中权重为顶点之间的距离）

Question

我有一个加权邻接列表，其中权重是顶点之间的距离。我想通过将每个顶点转换为x，y坐标来可视化它。

是否有一种算法可以接受这个邻接列表，并在二维空间中绘制图形，以便图形与列表保持一致（即所有图形线条的长度都由距离权重指定）？

- MikeRand

Answer 1

一般来说，答案是否定的，你不能在二维平面上精确保留距离的同时绘制一个普通图形。

原因是为了能够嵌入一个不改变距离的图形，距离必须具有非常特殊的属性。例如，它们必须满足三角不等式等条件。

为了看清这一点，请考虑一个带有3个顶点A、B、C和距离d(A,B)=1 d(B,C)=2 d(A,C)=5的图形。你可以很容易地看出这是行不通的。事实上，你将无法将其嵌入到任何欧几里得空间中，无论是多少维！

你可以做的是：尝试使用PCA这样的算法降低维度（将图形嵌入到二维空间）。PCA被广泛使用，你可以在任何你喜欢的编程语言中轻松找到实现。它会给你一个在二维平面上的表示，但不能保证保持距离。然而，如果你的图形恰好具有与二维嵌入一致的距离，PCA可以找到它。

顺便提一下，将PCA直接应用于距离有时被称为多维缩放（MDS）。

- Bitwise