网络拓扑可视化布局——逻辑布局算法

来源：田鑫网络

2022-03-08 10:30

逻辑布局算法与物理布局算法不同，它不需要关注节点的物理位置，只是根据网络节点的相互关系来进行布局。由于逻辑布局算法不需要网络节点的物理位置信息来进行拓扑布局的特点，所以逻辑布局算法能过解决抽象网络的拓扑布局问题，现阶段已有许多有效的逻辑拓扑布局算法，是实现网络拓扑结构可视化的重要技术。

1、树型布局算法

树型布局算法是早期使用的布局算法，但因其布局算法简单，很容易进行算法实现，所以该算法现在依然常常被人们使用。树型布局算法首先要对网络节点进行分组，每一组中的节点使用相同的纵坐标值，之后査找该分组的根节点，根据根节点的位置为该组节点分配横坐标位置，直至递归遍历完所有节点后结束。

树型布局算法节点排列层次性明显，与其他算法相比结构更加清晰，并且在完成的网络拓扑布局图中布局效率比较高，是比较常用的网络拓扑绘制布局算法。

2、射线型布局算法

在该布局算法中，网络拓扑图中每组节点到其中心节点的距离都是最短路径。射线型布局算法首先要找到拓扑的中心点，将整个拓扑的中心点放置于此；之后找到与该根节点连接的所有子节点，将所有子节点平均的散布在以根节点为圆心的圆上；若子节点下面还有节点，将其平均的散布在以父节点为圆心的圆上；最后按该步骤递归遍历完所有节点后结束。

射线型布局算法实现的原理也比较简单，是一种绘图空间利用率较高的算法，可以清晰的展示节点较多的网络拓扑，但该算法不适用于节点层次较多的网络。

3、直交布局算法

在直交布局算法中,所有的节点间的连线都要与横坐标轴或纵坐标轴平行, 所以直交布局算法能够清晰的展现节点之间的连接关系，能够使得网络拓扑布局可读性更强，是实现网络布局的比较重要的算法之一。

直交布局算法更实用于小规模网络拓扑可视化的展示。

4、层次型布局算法

层次型布局算法对有明显分层的网络拓扑绘制效果明显，该算法能够清晰的展示网络拓扑节点层与层之间的相互作用。层次型布局算法首先根据拓扑结构将节点进行分层；之后确定各个节点在网络拓扑中的坐标；之后按照各个节点之间连线尽可能少交叉的原则，对余下的节点位置进行优化和排序。

层次型布局算法在大规模网络的使用中，往往不能避免的出现连线交叉的情况，因此在小型网络中应用较好。

5、力导向布局算法

力导向布局算法是由 P.Eades 发表的目前网络拓扑布局算法中最重要的布局算法之一。力引导布局算法将网络拓扑中的节点看做物理学中的微粒，每个微粒都会排斥其附近的微粒，同时节点之间的连线会给微粒之间产生类似于弹簧的弹力，使得微粒与微粒相互靠近。网络拓扑中的节点在这种如同物理学中库仑力和胡克引力的相互作用下，会不断的调整节点与节点间的相对位置，当各个节点相互作用趋于平衡后，节点将不再发生位移，达到最终形态。

现阶段力导向布局算法在网络拓扑可视化中有很多的应用，力导向布局算法在小规模的网络拓扑布局中有这比较好的布局效果，但对于大型的复杂网络布局，因其算法的复杂度较高，很难对其拓扑布局进行计算。因此当力导向布局算法应用于复杂网络拓扑时，需要针对具体网络进行改进，一般会在局部网络布局中进行使用。

通过对五种常用布局算法的分析，并结合用户实际需求，本文决定使用层次型布局算法实现本系统拓扑展示部分。