绘制一个图，其中顶点之间的距离对应于边权重
当我给他一个加权图并且顶点之间的边权重指向顶点之间的距离时，是否有一种算法可以给我图中顶点的坐标？
像这样的东西：
public _ArrayOfCoordinatesForVertices_ **super_hyper_algorithm**(weighted_graph){
return _foo_;
}
Is there an algorithm that gives me coordinates of vertices in a graph, when I give him a weighted graph and the edge weights between vertices points to the distance between vertices?
Something like:
public _ArrayOfCoordinatesForVertices_ **super_hyper_algorithm**(weighted_graph){
return _foo_;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这通常是不可能的：想象一个具有 3 个节点 n1、n2 和 n3 的图。
现在考虑以下距离：（
这违反了三角形的不等性）。
This is in general not possible: Imagine a graph with 3 nodes n1, n2, and n3.
now consider the following distances:
(This violates the triangle inquality).
您所指的称为多维缩放（MDS），现在您应该找到大量的实现知道如何寻找它。
就像其他人所说的那样，在某种程度上，如果不违反一些约束（点之间的距离），就不可能绘制出完美的图形。 MDS 算法专门针对最大限度地减少此类违规行为。
What you are referring to is called Multidimensional scaling (MDS) and you should find plenty of implementations now you know how to search for it.
Like others said, to some extent, it is impossible to draw a perfect graph without violating some of your constraints (the distances between points). MDS algorithms are specifically targeted at minimizing such violations.
如果图形是在 欧几里得空间 中绘制的，则不能这样做，因为，正如所指出的在 这个答案您可能会违反三角不等式。
通常，您可以通过使用不同的颜色（即通过将权重映射到颜色图）或通过使用不同的边厚度（即通过将权重映射到厚度比例）来直观地表示边的权重。
If the graph is drawn in the Euclidean Space you can't do that, because, as pointed out in this answer you could violate the Triangle Inequality.
Usually, you can visually represent edges' weights by using different colour (i.e. by mapping weights to a colour-map), or by using different thickness of the edges (i.e. by mapping weights to a thickness scale).
好的，我已经找到了一个用于 python 的 library ，它为我创建了一个图形图像:)，我可以给边的权重，如属性：边的权重。以点计，重量越重，边缘越短、越直、越垂直。
OK i have found a library for python and it creates a graph image for me :) and i can give weights for edges like attribute: Weight of edge. In dot, the heavier the weight, the shorter, straighter and more vertical the edge is.