网络图的计算机算法和显示方法探究

於政理

摘 要：随着信息技术的不断发展，网络图在很多领域发挥了越来越重要的作用，关于网络图的计算机算法和显示方法的研究受到了研究者们的广泛关注。本文首先介绍了网络图的相关概念和理论；其次，阐述了网络图的计算算法，包括点符号全控制算法和边符号控制算法；然后从基础理论、步骤和需要注意的问题等三个方面详细介绍了网络图的显示方法；最后，提出了网络图的计算机算法和显示方法的改进策略，包括层次策略、搜索策略和堆运算等。

关键词：图网络；计算机算法；显示方法；控制算法

中图分类号：TP319 文献标识码：A 文章编号：1671-2064（2018）20-0015-02

网络图可将日常可见的各种原始网络图中机构和原件抽象出来，形成计算机可识别的拓扑结构。利用网络图，工作人员可对原始网路进行定量或定性分析，并在此基础上进行优化处理。网络图发挥的作用已经得到了普遍认可，在学术领域，网络图的计算机算法和显示方法已经成为较为热门的研究领域[1]。因此，开展网络图的计算机算法和显示方法研究具有重要的使用价值和研究意义。

1 网络图的概念及相关理论

网络图是指将实际原始网络的结构和各类原件的相关网络信息，如网络的结构、元件的种类、各种参量等，抽象成计算机能够接收和理解的拓扑结构[2]。

关于网络图的研究主要包括网络图的计算算法和网络图的显示算法两个方面。在网络图的计算算法方面，目前的研究主要集中在点符号全控制算法和边符号控制算法两类。网络图的显示方法和相关算法以计算机相关显示理论为基础，对网络图进行绘制，且绘制出的网络图可进行大小和位置的更改。

2 网络图的计算算法

2.1 点符号全控制算法

点符号控制算法将点符号的相关基础理论与全控制算法相结合。点符号全控制算法在融合了符号控制算法的基础上，又引入了限定了最大度和最小度的极限度的概念。点符号控制算法关注的是局部占優问题，点符号全控制算法是对点符号控制算法的改进和延伸，能够将原来符号控制算法中，部分处于闭领域中点扩展到开领域，从不同的角度开展研究，同时，通过引入最大度和最小度，可为一般的网络图中给出下限。在随后的研究过程中，研究人员提出了更多新的网络图符号控制边界，提高了原有边界的适用性。随着符号全控制算法的不断充实和完善，反符号算法也被研究者们提出，这种反符号算法为符号全控制算法提出了新的研究思路和研究视角，为算法的后续研究提供了更为坚实的基础，可进一步提高网络图的计算速度[3]。

2.2 边符号控制算法

边符号控制算法的相关概念由徐保于2001年提出，边符号控制算法的提出，对网络图控制算法的内容进行了充实和完善。随后，有学者对边符号控制算法进行了发展和完善，对边符号控制算法的上下界和算法数给出了较为准确的具体数值，对界限进行了完善。边符号控制算法是对符号边算法的隐身。在最近的关于边符号控制算法的研究中，研究者们将原有边符号控制算法中的函数值域卜由[-1，1]改成[-1，0，1]，提出了成为减边控制的算法，但是由于减边控制算法的相关研究难度较大，目前尚未出现有代表性的研究成果，关于减边控制算法的研究仍在继续。

点符号控制算法和边符号控制算法的提出和完善初步构成了可显示和查询点的网络图系统，但是，这种系统尚不够完善，无法对操作的历史记录进行查看，且显示的图像不够清晰，为了完善该系统，可通过发挥数据库的作用来改进，实现对数据的快速查询。

3 网络图的显示方法

3.1 基础理论

利用计算机来显示网络图往往利用较为基础的C语言实现。利用C语言显示网络图的优势在于，一方面C语言本身功能强大，且该语言相对简洁，十分适合在屏幕上实现对网络图的回执，另一方面，C语言具有较高的执行率，在运行C语言程序时，程序占用系统的内存相对较少且运行速度比其他语言更快[4]。在对网络图进行分析时，通常从点和连线两方面入手，尽管这种分析方法具有一定效果，但是由于点和边的关系有时较为复杂，不可避免出现错误。针对该问题，研究人员通常利用C语言，首先绘制出各个顶点，然后在顶点之间建立连接，实现时利用物理坐标，坐标形式如图1所示。

如图1所示，在所用的物理坐标系中，垂直方向为纵轴（即Y轴），且向下为正；水平向下为横轴（即X轴），且向右为正。在使用该物理坐标系时，要求点的坐标必须为在某一范围内的整数。

对绘制出的网络图，有时需要根据需求调整图形的位置、大小等属性，因此，图形需具备平移、缩放和旋转等功能。

3.2 显示步骤

完成网络图的显示算法，通常包括以下几个步骤：

步骤1：图形绘制。研究人员根据用户输入的网络图信息，在计算机屏幕上将网络图的完整图形绘制出来；

步骤2：边描绘。对步骤1得到的图形，对新添加的边，根据边的信息不同，分别用不同的颜色对边进行标注；

步骤3：连通图构建。根据用户新添加的点和边的信息，将图形中的点相互连接，构成连通图，同时用不同的颜色对新添加的点和边进行标注；

步骤4：边删除。在绘制指定的图形时，需要删除图中多余的边，在删除边时应当保证图中所有点不能成为孤立的点，必须至少要和一个点有连接关系；

步骤5：点删除。在绘制图形时，需要删除多余的点，在删除点时，应当同时删除与该点相关联的边；

步骤6：记录操作。为了便于后期的操作查询，在对网络图的各种操作都应当详细准确记录；

步骤7：观测时间。在每次操作网络图时，准确记录操作时间；

步骤8：构建系统。构建网络图的显示和查询系统，该系统对外提供显示和查询功能，可查询网络图的连通性和最短路径。

3.3 显示问题

在绘制网络图时，除了遵循上述步骤，还需注意相关的细节问题。网络图的显示是在点符号全控制算法和边控制算法的基础上进行的。研究人员在向系统中输入绘制的数据时，通常需要首先输入绘图的指令，然后在输入网络图的点的个数和编号、边的数量和编号，以及点的坐标等信息，最后将数据加入到创建的邻接多重表（邻接表的结构如图2所示），这些步骤涉及很多细节性的问题需要注意。例如，在输入边和点的信息时，需要首先输入相关质量，然后在向其中数据点或边的数量、起点和终点的熟练阿根、编号等，有时需要修改邻接多重表后才能完成整个网络图的绘制工作。在添加新的点时，如果该点具有孤立性且网络连通性不完整时，需要对网络图进行基本控制。

4 网络图的计算机算法和显示方法的改进

最短路径问题时图论中的经典问题之一，随着信息技术的不断发展，网络变得更为复杂，最短路径问题的研究更注重于时效性。本文从层次策略、搜索策略和堆运算三个方面详细阐述网络图的计算机算法和显示方法的改进策略。

4.1 层次策略

将问题的规模进行降阶是降低算法复杂度的有效方法之一。为了降低最短路徑算法的复杂度，可采用层次策略，将网络中的主要节点和相关的边提取出来，构建成具有层次化的结构模型，将网络的结构进行简化，使得网络结构中每个层次仅为其上一个层次的子集。层次策略中，分层的等级越高则涉及的边和节点越少。在分层的网络图中执行最短路径计算时，首先在原来网络的初始点及其局部开始，然后进入更高层次，在靠近目标点时回到原网络，直至到达目标。这样可有效减少需要遍历的节点数，提高算法效率。

4.2 搜索策略

搜索的盲目性使得传统的最短路径算法效率较低，遍历了大量无用节点。在搜索策略上的改进，可对原有算法进行启发式引导，加快算法的执行进度。现有的搜索策略改进方法大多包括层次策略、贪心策略和方向策略。搜索策略选择的是否正确直接影响着算法的计算效率和精度。通过对搜索策略的优化，可使得传统最短路径算法具有更快的响应速度和计算精度，以及较低的内存消耗。

4.3 堆运算

对算法执行中数据结构进行优化也是提高算法执行效率的有效方式之一，可采用的常见的数据结构有桶结构和堆结构，本文重点关注堆结构。堆结构中较为普遍使用的是二叉堆、二项堆和Fibonacci堆。在堆运算中，需要对堆进行修复和维护，以保证其一直具有堆序的原有特性，涉及到的运算主要包括：（1）删除最小值：在删除最小值时，首先用堆中最后元素替换根节点，降低堆的大小，然后将改点下滤，最后删除，以免影响堆的特性；（2）插入：需要先将堆大小加1，然后将需要插入的松弛节点加到堆的末尾，最后上滤到满足堆性质；（3）修改键值：当数据结构遭到调整，堆的特性受到影响时，需要采用上滤的方式进行修复。

采用二叉堆运算对算法仅优化时，整个算法的时间复杂度仅为O（mlogn），显著提高了原有算法的性能。

5 结语

网络图的发展和计算机技术的发展，促进了两者的结合和应用，未来将能够在更多领域发挥重要作用，因此，网络图的控制算法理论具有广阔的应用前景和实用价值。但是，该领域仍有很多问题需要进一步研究，网络图的控制算法理论仍需要进一步完善。

参考文献

[1]刘晓飞.探究网络图的计算机算法和显示方法[J].安庆师范大学学报（自然科学版），2016，22（2）：86-88.

[2]齐安智.控制算法理论及网络图计算机算法显示研究[J].中国新通信，2018，（1）：101.

[3]宋碧慧.网络图的计算机算法及显示方法研究[J].无线互联科技，2017，（21）：48-49.

[4]韩正一.基于网络图的计算机算法研究[J].信息通信，2016，（3）：43-44.