图的可视化
来源：10-1 看得见的算法，下一季再见！
JamesChi
2018-01-09
波波老师您好。我在自己用H5的canvas编写tree和graph的可视化，用一个个圆形表示每一个节点。tree比较好办，我是递归的计算出每个节点圆心的x, y值。但在画graph的各个节点时，我没有想到一个好的方法，根据什么规则把N个节点画到canvas上。波波老师有什么建议吗？有没有某一个算法能够比较优雅的画出N个节点？
写回答
1回答
-
对于一个已知图将其“平面化”，是一个经典且复杂的问题。如果希望了解更多，可以搜索学习Planar Graph的相关理论。
我的建议是：如果是随机生成图，不要先生成图再平面化，而是直接在二维平面上随机生成节点的二维坐标，每一个节点只和离其最近的k个节点随机生成边。（k为超参数，可以自己指定，也可以在生成的时候判定边之间不相交即可。判定平面上线的相交，又是一个经典的计算几何的问题。）
如果图的规模比较小，手动指定图的每个节点在二维平面上的坐标和相应的边，也是一种选择。
012018-01-09
相似问题