（电路与系统专业论文）网络图的计算机算法和显示方法的研究.pdf

硕士论文网络图的计算机算法和显示方法的研究 摘要 本文主要研究网络图的计算机算法和显示方法。包括：网络图的计算机显示、 连通性算法和最短路径算法。首先对图的六种存储结构进行分析，并以邻接多重 表作为图的存储结构，研究了网络图在屏幕上显示的方法，初步建立了一个网络 图显示和查询的系统。其次，介绍了图的连通性算法，针对系统生成图的研究， 本人改进了深度优先搜索算法，从而减少了连通性判断的计算时间。最后，全面 阐述图的最短路径算法，提出改进算法，有效地解决了含有多条相同长度的单源 点最短路径问题；本人还提出边长都相等的图的最短路径算法，与使用一般的最 短路径算法相比，本算法的效率要高得多。 关键词：图论、邻接多重表、图的显示、连通性算法、最短路径算法 硕士论文 网络图的计算机算法和显示方法的研究 a b s t r a c t t h i sp a p e rd e a l sw i t ht h ea l g o r i t h m so ft h eg r a p hd i s p l a y , t h ec o n n e c t i v i t yo ft h e g r a p ha n d t h es h o r t e s tp a t hi nt h eg r a p h b a s e do nt h ea d j a c e n c y m u l t i l i s t ，t h ea u t h o r g i v e st h ea l g o r i t h m so ft h eg r a p hd i s p l a ya n dc r e a t e sai n t e r a c t i v es y s t e ma b o u tt h e d i s p l a ya n dq u e r yo f t h eg r a p h t od e c r e a s er u n t i m e ，t h ea u t h o rh a si m p r o v e dt h e d f s a l g o r i t h mt h a td e t e r m i n st h ec o n n e c t i v i t yo ft h eg r a p h t h ep a p e rp r o p o s e sa n a l g o r i t h mt h a tc a l lf i n da l lr o u t e s 、i mt h es a m el e n g t ha n dp e r f e c tf u n c t i o n s ad e w a l g o r i t h mi sp r o p o s e d ，w h i c hs o l v e st h es h o r t e s tp a t hi nag r a p hw i t ht h es a m el e n g t h o ft h ee d g e s c o m p a r e dw i t ht h ea l g o r i t h m si ng r a p ht h e o r y , t h ea l g o r i t h mh a sm o r e e f f i c i e n c y k e yw o r d s ：g r a p ht h e o r y ，a d j a c e n c ym u l t i l i s t ，d i s p l a yo f t h eg r a p h ，a l g o r i t h mo ft h e c o n n e c t i v i t y , a l g o r i t h mo f t h es h o r t e s tp a t h 一_一 i l 硕士论文网络图的计算机算法和显示方法的研究 1 绪论 1 1 研究背景及意义 本文主要研究网络图的计算机算法和显示方法。 网络图广泛存在于我们的日常生活中，例如电路网络、电力网、通信网、交 通运输网、工序流程图等等。虽然实际使用中的电路网络各不相同，但是它们的 结构和各元件的种类及参量等网络信息都能拓扑成计算机能接收的信息，拓扑后 得到的就是网络图1 1 2 j 。对于其它的实际原始网络也同样可以拓扑得到网络图。 譬如图1 1 就是对实际电路网络拓扑生成的网络图。 其实，这种网络图包含原始实际网络的很多信息，包括边的权值( 如对应电 路的支路电流或电压等信息) 和顶点与边的邻接关系等等。针对这些信息，如何 判断图的连通性以及最短路径就有了实际意义。 8 3娑 e 1 7弋i 贰潞 石0 v 3 0 巡2 6 翼 v p 4 。卜v ，。 图1 1 对这种网络图进行研究的理论就是图论( g r a p ht h e o r y ) 。图论创始于1 7 3 6 硕士论文网络图的计算机算法和显示方法的研究 年，瑞士数学家欧拉( e u l e r ) 发表了一篇讨论哥尼斯堡七桥难题的问题。哥尼斯 堡城内有一条河，河中有两个岛，把市区分成了四块陆地( a 、b 、c 、d ) ，陆 地间有七座桥相通，如图1 2 ( a ) 所示。长期以来人们在议论，能否从任一陆地 出发，走遍七桥而每桥只走一次? 实践证明，这样的尝试不可能成功。欧拉从理 论上首次论述这个问题，他把图1 2 ( a ) 所示的问题表示为图1 2 ( b ) 所示的线 路，图中的点表示一块陆地，点间的连线表示相应的桥梁，然后他得出结论：只 有与每一个点相连的边的数目均为偶数时才存在上述路径1 6 j 。 a b a ( a )( b 图1 2 哥尼斯堡七桥 ( a ) 示意图；( b ) 模拟图 c d 从1 7 3 6 年到1 9 3 6 年，图论的发展经历了漫长的历程。在这段时间里比较突 出的贡献有： 克希霍夫与电网络方程； 凯莱( 1 8 5 7 ) 与树的来源； 哈 密顿图； 四色问题。1 9 3 6 年，匈牙利数学家k s n i g 完成的有限图与无限图 的理论是图论的第一本专著【6 。 1 9 4 6 年以后，图论得到了迅速发展。以最短路径问题为例，1 9 5 9 年，狄克 斯特拉( d i j k s t r a ) 提出了解决最短路径的问题的d i j k s t r a 算法【1 9 】。其后，弗洛伊 德( f l o y d ，1 9 6 2 ) 、福特( f o r d ，1 9 6 4 ) 、但茨希( d a n t z i n g ，1 9 6 7 ) 等人又相继 提出新的算法或改进了d i j k s t r a 算法。时至今日，关于最短路径问题已有1 7 种被 认为是有效解决这一问题的算法【2 9 1 。 由于实际使用的电路网络完全可以拓扑成网络图，因此图论是电路与系统学 科中个很重要的研究领域。 随着电路的规模日益庞大、结构日益复杂，对电路的分析使用手工方式是难 以想象的，因而，借助于计算机进行电路网络图的分析就越发必要且重要。 而对电路网络拓扑成的网络图进行计算机分析，首先要解决的问题就是如何 在计算机屏幕上显示网络图。然后对网络图进行分析，包括网络图是否连通、网 络图中的中心点到其它点的最短路径问题，等等。上述问题的解答有助于判断集 成电路的布图布线是否正确、合理一。本文主要讨论如何实现这种网络图在计 算机屏幕上的显示以及由此而引发的对图的连通性和最短路径的讨论。 早曰 硕士论文网络图的计算机算法和显示方法的研究 平凡 旧坩圈日业小仪丹1 1 日穴畀t 五日u 叩】九是1 = t ，忆恩人： 一、可以迅速自动生成网络图并在计算机屏幕上显示。如应用于实际中，它 可以模拟集成电路、通信网、交通运输网、电力网、工序流线图等。 二、网络连通性算法，对于判断v l s i 布图布线有重要的指导意义1 6 】。 三、最短路径算法。如应用于v l s i 中，有助于完成v l s i 的布线设计、集 成电路工艺中的制版设计及其印刷线路板设计【3 , 4 , 6 j ；它还可以应用于交通运输网 络中，有助于降低交通运输费用、提高效率【5 j ；此外，最短路径算法如果应用于 自然灾害预报系统中，可以迅速有效地指出最佳救援路线、最佳撤退和疏散人员 路线，极大地降低人们生命财产的损失。 实际上，本课题可应用于所有的网络中，并不仅仅局限于上面所述。 1 2 本文的内容和主要工作 本文主要研究网络图的计算机算法和显示方法。 根据由电路或通信网络、电力网拓扑得到的网络图，把它在计算机屏幕上显 示出来。其实，这种网络图包含原始实际网络的很多信息，包括边的权值( 如对 应电路的支路电流或电压等信息) 和顶点与边的邻接关系等等。针对这些信息， 还要判断图的连通性以及求解最短路径。 为简化讨论起见，我们假定两络图是无向图，图中边的权值都相等，譬如图 1 1 ，并以此图来验证有关算法是否正确。 本文的组织结构如下： 绪论部分。主要阐述了本文的研究背景、研究目的、研究的意义，交待了本 文的研究任务。最后介绍了本文的具体研究内容。 基础知识部分。本人在参阅大量文献资料时发现很多有关网络图的基本概念 和术语都不统一，因此有必要先统一有关网络图的概念和术语：然后本人讨论并 分析了图的数据结构，针对图1 1 特定的网络图应采用何种数据结构。 第三部分详细讨论了网络图的计算机显示算法。以邻接多重表作为图的存储 结构，详细论述网络图的显示和查询的方法，它包括： 对给定的网络图，如何在羼幕上自动显示； 若任意增加个顶点或若干条边，如何实现在屏幕上快速增加，并显示 为不同颜色； 对新增顶点或边，如何计算其增加的时间； 若任意删除一个顶点或若干条边，如何在屏幕上快速显示出来； 如何查询上一次操作的记录； 硕士论文网络图的计算机算法和显重查鲨盟堑塑 如何存储屏幕显示的图形。 第四部分主要讨论了图的连通性问题。介绍图连通性问题的算法，并在此基 础上，讨论如何判断图1 1 的连通性。 第五部分主要讨论了图的最短路径问题。介绍最短路径的经典算法，并以 d i j k s t r a 算法为基础，完善最短路径算法：最后针对图1 1 研究在特定情况下( 所 有边长都相等) 的最短路径算法。 第六部分是论文的总结和结论，并对进一步工作提出了建议。 4 硕士论文网络图的计算机算法和显示方法的研窭 2 基础知识部分 2 1 基本概念 图( g r a p h ) 是一个包含顶点、顶点之间连线的集合。许多事物，如电力网、 大规模集成电路、通信网络、计算机网络、煤气网、水网、地理网络等许多实际 应用的网络都可以抽象为图。因而，图论有及其重要的理论和实践价值。为了方 便讨论，先在此列出本文中用到的图论的概念、术语2 1 ， 1 、有向图 【定义】有向图( d i r e c t e dg r a p h ) 是一个具有下列特性的序偶g = ( 矿，a ) ： y 是一个有限的非空集。矿中的元素称为g 的顶点( v e r t e x ) 或节点 ( n o d e ) ； a 是一个有限的顶点序偶集合。也就是说，一v v 。a 中的元素称为 g 的弧( a r c ) 。 弧( 又称为有向边) ：用0 ，w ) 表示( 其中( 甜，w ) a ) ，代表从顶点“指向 顶点w 的有向边或弧。顶点w 称为它的头( h e a d ) ，“称为它的尾( t a i l ) ，且称顶 点w 邻接于( a d j a c e n t ) 顶点“。 图的某顶点的度( d e g r e e ) ：是该顶点所关联边的数目。 顶点的出度( o u t d e g r e e ) ：是指从该顶点发出的边的数目，记为p ( v ) i 。 顶点的入度( i n - d e g r e e ) ：是所有射入该顶点的边的数目，记为l f ( v ) i 。 孤立顶点：图g 中顶点v 的度为零的顶点，称v 为孤立顶点。 点独立集：它是顶点集y 的子集( 记为s ) ，并且在s 中任两点均不相邻。 换句话说就是：点独立集是由图g 中所有孤立顶点的集合。 2 、无向图 未指定弧的方向的图称为无向图( u n d i r e c t e dg r a p h ) 。无向弧称为边( e d g e ) ， 一般用( v ，e ) 表示顶点集合为v ，边集合为e 的无向图。 3 、稀疏图和密集图 通常，我们把边相对少的图称为稀疏图( s p a r s eg r a p h ) ，把边相对多的图称 为密集图( d e n s eg r a p h ) 。 4 、路径和路径长度 图g = ( 矿，彳) 的路径是一个非空的顶点序列，即p = v ，v ：，v 。) 。其中， 项士论文 网络图的计算机算法和显示方法的研究 v 。v ( 1 i n ) ，且v 。，vj + 1 ) ( 1 i n ) 。 在图g 的每条弧( v f v ，) 上附加一个数f 0 ，v ，) 。如图g 中不存在弧( v ，v ，) ，则 令，( v l v ，) = 。我们把z ( v ，v ) 认为是弧( v ，v ，) 的长度( 1 e n g t h ) 或权( w e i g h t ) 或费用( c o s t ) 。将路径长度( 1 e n g t h o f a p a t h ) 定义为组成路径的各条弧( 或边) 的权值之和。 5 、网络 我们将加权图称为网络或网( n e t w o r k ) 。 【术语】 通路：顶点与边序列互不相同的途径。 连通：顶点v 和w 之间存在通路，则称v 、w 连通。 连通图( c o n n e c t e d g r a p h ) ：图g 中任一对顶点均连通的图。 连通分支( e m b r a n c h m e n t ) ：图g 的顶点集v 中元素用连通关系( 等价) 分类，连通的顶点同类，类数即为连通分支数。连通分支用w f g l 来表示。显然， w ( g ) 1 表明图g 不连通。 生成树( s p a n n i n gt r e e ) ：一个连通图的极小连通子图就是一个生成树。 最小生成树( m i n i m u m s p a n n i n gt r e e ) ：对于一个网络图g ，其最小代价 的生成树。 最短路径( s h o r t e s t p a t h ) ：网络图g 中，从顶点v 到顶点w 的所有路径中， 具有最小的路径长度的路径称为从顶点v 到顶点w 的最短路径。 2 2 图的存储结构 由于本课题要在计算机上进行有关图的运算和存储，因而必须考虑存储图时 常用的存储结构。此外，分析个算法的优劣也与数据结构密不可分。 2 2 1 关联矩阵 【定义】设g = ( 矿，a ) 是具有n 个顶点、m 条边的图，则g 的关联矩阵 ( i n c i d e n c em a t r i x ) x ( g ) 定义如下【1 1 ： x ( g ) = 嘞( 1 j ，】勺肘) “x m 其中， 【l ，若边e ，关联到节点v 。 一1o ，若边e ，和节点，。不关联。 6 硕士论文网络图的计算机算法和显重查鲨盟堑塑 对于一个网络图g = ( 矿，e ) ，其顶点个数为、边的数目为m 。如果用关联 矩阵来表示，则要占用m n 的空间。如果要存储个网络图，假设它有1 0 0 个 顶点、4 0 0 条边，并且假设矩阵的每个元素是整型，则要占用空间1 0 0 4 0 0 2 1 0 2 4 1 9 5 k b 。占用的空间过大! 如果图g 是稀疏的，则矩阵中很多元素为零， 存储这些零元索没有什么意义，空间浪费太大。但是，它最大的优点在于表示图 的关系异常清晰。 2 2 2 邻接矩阵 当我们用计算机来描述一个图的结构时，通常用的是邻接矩阵而不是关联矩 阵。 【定义】设图g 的顶点集y = v ，v ：，v 。 ，令 一f 1 ，若 与v ，邻接 口一1 0 ，若v 。与v ，不邻接或v ，= v j 则称由元素a ，( f ，j = 1 , 2 ，n ) 构成的n 阶矩阵为图g 的邻接矩阵( a d j a c e n t m a t r i x ) ”，记做4 ( g ) 或爿。即a ( g ) = 【舀驴 。( 1 f ，) 。 显然，对于无向图，其邻接矩阵a 是主对角线对称矩阵：而有向图则不然。 如果用邻接矩阵a 来表示，则要占用n n 的空间。对于密集图g ，它占用 的空间要比关联矩阵要少得多，这是因为一般顶点个数要远远小于边的数目 m 。对于稀疏图g ，同样在矩阵中存储很多零元素；此外，对于无向图，邻接 矩阵是对称矩阵，我们可以用压缩的方式来存储，使得占用的空间减至n n 2 。 建立一个图g ，给邻接矩阵4 的每一个元素初始化约要2 次，对其中有邻接顶 点的元素赋值约要m 次，每次赋值前对顶点查编号需要o ( n ) 。时间复杂度为 o ( n 2 + m 1 。 2 2 3 邻接表 邻接表( a d j a c e n c yl i s t ) 是图的一种链式存储结构。 【定义】设图g = ( 矿，e ) 有n 个顶点、肘条边，将图中每一个顶点v ，和由v 出发的弧或边构成单链表，以映象图的逻辑关系。由这v 个单链表组成的数据结 构就称之为图的邻按表( a a j a c e n c yl i s t ) 。 链表结点：表示顶点v ，到另一顶点v 的一条弧或边，如图2 1 所示。 其中，a a j 为邻接点域( a d j v e x ) ，存放与v j 相邻接的顶点v 的编号；，是弧 硕士论文网络图的计算机算法和显示方涟塑堑塑 或边上的权或弧长，也可以是弧或边的相关信息( 若不考虑权时，下图中的权， 省略) ；n e x t 为指向与v ，相邻接的下一条弧或边结点的指针。 互 工二工二 玉互 0 ， 图2 1 在每个链表上设一个表头结点： 互匠工 亟 图2 2 其中，d a t a 域存储顶点数据；加m 为指向该顶点出发的第一条弧结点( 或边 结点) 的指针( f i r s ta r c ) 。有时候，还要加入v i s i t e d 域，表示顶点是否被访问过。 另外，可以将所有表头结点( 可以链表形式) 通常以顺序结构的形式存储。 如果用邻接表来表示具有个顶点、m 条边的无向图g = ( v ，e ) ，则它的邻 接表需个头结点和2 m 个表结点。显然，对于稀疏图，用邻接表表示图比关 联矩阵、邻接矩阵节省存储空间。 用邻接表来建立一个图g 的步骤如下： 建立邻接表，包括链表结点和表头结点； 输入顶点信息； 对每一条边，存入其邻接点编号，以其中一个端点作为单链表的第一结 点插入，完成边的输入。 若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度为 o ( n + m ) ；否则，其中每一条边都要先对顶点进行查找定位，其时间是o ( n ) ， 才能存入其邻接点编号。因此，邻接表的时间复杂度为o ( n m ) 。 2 2 4 十字链表 十字链表( o r t h o g o n a ll i s t ) 是有向图的另一种链式存储结构，它实际上是邻 接表和逆邻接表的结合，弧和顶点的信息分别由弧结点和顶点结点表示ij 0 。 弧结点： 表示有向图中的一条弧，如图2 3 所示。 硕士论文网络图的计算机算法和显示方法的研究 图2 3 其中，血f z 域存放弧尾v 的编号( 设为i ) ； p 日d 域存放弧头v ，的编号( 设为，) h l i n k 为指向弧头相同( 同为v ) 的下一条弧，而t l i n k 指向弧尾相同( 同为v ) 的下一条弧。有时候根据需要，也可以加入i n f o 域来存储弧的有关信息。 顶点结点： 巫 工j j 巫 图2 4 其中，d a t a 域存放顶点( 设为v ，) ；h 域为指向弧头的第一弧结点的指针， 相应逆邻接表指针；f o u t 域为指向弧尾的第一弧结点的指针，相应邻接表指针， 并将顶点组成顶点表。 如果用十字链表来表示图g ，其算法与邻接表相似，算法如下： 建立邻接表链和逆邻接表链，将相应的歼、f o u r 域置空( 初始化) ； 输入顶点数据，依次读入条边，形成链表结点，。 显然，用十字链表建立图g 的时间复杂度同建立邻接表。 2 2 5 邻接多重表 因为无向图中每条边都牵涉到两个链结点，所以当边数为m 时，链表结点 数为2 m 。为了节省存储空间，邻接多重表( a d j a c e n c ym u h i l i s t ) 便应运而生， 它是对无向图邻接表的改进。图中的边和顶点的信息分别用边结点和顶点结点来 表示【1 0 j 。 边结点：表示无向图中的条边( v ，v7 ) 。 图2 5 9 其中，f v 和一分别存放顶点v 和v 的编号( f 和，) ；i l i n k 指向与v 关联的下 一条边的结点：f l i n k 指向与v 关联的下一条边的结点。有时候根据需要，还要加 入，域( 表示边( v ，v ) 的权) 、m a r k e d 域( 表示该边是否被访问过) 。 顶点结点： i d a t a if e j 4 盟l 图2 6 其中，d a t a 域存储顶点数据；f e d g e 域指向域本顶点关联的第一条边的结点。 有时候，还要加入v i s i t e d 域，表示顶点是否被访问过。 用邻接多重表来表示图g 的基本操作同邻接表，只不过采用邻接多重表表示 的图更为简洁，所以其建立的复杂度也就同邻接表。 2 2 6 二数组法 先定义两个一维数组d 。( e ) 和d ：陋) 。将任意一条边e 。的两个端点v 和v ，改 变存放在两个数组的d 1 ( 七) 和d 2 ( ) 位，即第k 条边存放在数组的第k 个位置上， 数组元素是顶点号。对于加权图，还要加一个一维数组d 、 ) ，用来存放所对应 边的权，即边长。对于有向图，一般d ；陋) 存放边的起点，d ：伍) 存放边的终点； 对于无向图无此规定。1 6 j 此方法表示图比较方便、清晰，占用内存少，尤其适用于稀疏的无向图。 用二数组法来表示图可以完全照顾到用户的使用习惯；用户般是随机输入 网络图的边及边的标号，然后给出这条边的两个顶点，以及边长等基本信息。按 照这一习惯，计算机得到的先是顶点个数及其顶点标号，然后是边的数目m ， 每条边的两个顶点及边长。其实，按照用户的这一输入习惯，事实上已经表示出 网络图。二数组法就是按照这个习惯顺序生成顶点数组和边数组。所以，建立一 个图g 的时间复杂度为o ( n + m ) 。 2 2 7 图的存储结构比较 以上六种存储结构的比较： 第l 、2 、6 种结构实际上是数组结构，其余几种都是链表结构。 一个图的关联矩阵和邻接矩阵表示都是唯一的、不变的；但其邻接表的 表示不唯一。这主要是由于邻接表的表示中，各边表结点的链接次序取决于建立 邻接表的算法以及边的输入次序。 对一个有个顶点、m 条边的图g ，如用关联矩阵存储要m n 的空间， 硕士论文网络图的计算机算法和显示方法的研究 采用邻接矩阵的存储量为2 ；而采用邻接表、十字链表和邻接多重表更加节省 存储空间。 一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可 以用邻接表和十字链表表示，由于本课题主要针对无向图，因而采用邻接矩阵4 时，a 是对称矩阵；而图多是稀疏图，则采用邻接表结构较为合适。 表1 1 是几种图的存储结构的比较。 表1 1 几种图的存储结构的比较 名称实现方法优点缺点时间复杂度 1 、易判断两点间 的关系 o ( n 2 + m n 1 邻接矩阵二维数组占用空间大 2 、容易求得顶点 的度 1 、节省空间 1 、不易判断两 o ( n + m 1 或 邻接表链表2 、易得到顶点的 点间的关系 2 、不易得到顶 出度 o ( n m 、 点的入度 1 、空间要求较小o ( n + m 1 或 十字链表链表2 、易求得顶点的结构较复杂 出度和入度o ( n m ) 邻接 1 、节省空间 d ( + 吖) 或 多重表 链表2 、易判断两点闻结构较复杂 的关系 o ( n m ) 考虑到要在屏幕上绘制类似图1 1 的无向网络图，并想使程序执行时间尽可 能的少，需要选择合适的存储结构。同时考虑到用户实际使用时输入的网络图的 顶点和边的个数每次都不一样，还有若需要添加或删除顶点、边，这使得对图的 存储结构内容的修改较多；以及对网络图的顶点和边存储，还需要顶点和边的很 多信息，如顶点的二维坐标( x ，y ) 、边的权值等等。 结论：综合以上各个方面，采用邻接多重表表示无向网络图比较好! 硕士论文网络图的计算机算法和显示方法的研究 3 网络图的显示 3 1 图的显示理论 3 1 1 网络图的计算机显示理论 为了在屏幕上显示出网络图，我采用c 语言来实现网络图的绘制。之所以采 用c 语言，基于两点原因：一是c 语言简洁且功能强大，在屏幕上作图方便； 二是用c 语言编写程序一般占有内存少、执行效率高，适合我们这些对显示速度 要求较高的用户。 我们知道网络图是由点( 一般称之为顶点或节点) 以及点之间的连线( 对有 向图称为弧，对无向图称为称之为边) 构成，这些顶点和边的关系错综复杂。某 个点可能的度为1 ，也有的点的度数为大于1 的整数，如是非连通图还可能有的 点的度数为0 ；但是，每条边肯定有两个端点。因而，要在屏幕上绘制网络图， 可以先画出各顶点，再在相应的顶点间添加连线即边。 在屏幕上画出点，我们可以根据已知图先确定图上各点的坐标，我们称之为 用户坐标b ，y ) 。但要注意的是c 语言作图时，屏幕上采用的是物理坐标，即原 点在屏幕的左上角，水平方向为x 轴，向右为正；垂直方向为y 轴，向下为正， 如图3 1 所示l l “。 ( 0 ，0 ) 图3 1 物理坐标系 x 在这种坐标系中，屏幕上每一点的位置可由坐标伍，y ) 来确定，这里，x 、y 必须是整数，并且有一定的取值范围。j 、y 的取值范围与设置的图形模式有关， 即与屏幕的分辨率有关。物理坐标与用户坐标的关系式1 研为： x 轴方向： 2 硕士论文网络图的计算机算法和显示方法的研究 数值区间为x l x 2 ，屏幕点区间x 1 x 2 ，则数值x 对于的x 为： x x 2 - x 1 。+ 兰! ：兰! 二! ! ：丝 x 2 一x lx 2 一x 1 ( x l 工x 2 ，x 1 x x 2 1 ( 3 1 ) y 轴方向： 数值区间为y l y 2 ，屏幕点区间y 1 l ，2 ，则数值y 对于的y 为： y ：塑v + 坚：丝= 翌：! ! y 2 一y 1 。y 2 一y 1 ( y l y y 2 ，y 1 y 7 2 ) ( 3 2 ) 如x 、y 的计算结果不是整数，应取整数。 第二步，在屏幕上画边。根据一条边所对应的两个顶点，找出这两个顶点的 坐标，然后，在两个顶点间画上一条直线即可。 倘若需要在屏幕上任意添加顶点( 节点) ，均可用上述方法绘制。为使用户 一目了然，对于新增的支路( 或边) ，用不同颜色绘制，c 语言提供了1 6 种颜色 可供选择，一般来说应当满足我们的需要。 3 1 2 图形变换 绘制出来的网络图可能过大或太小，或者位置太偏，“跑到”屏幕的某个角 落去了。这时需要对图形进行缩放、平移、旋转等操作，使得显示出来的网络图 的大小、位置适宜。这时，可遵循计算机图形学中的二维平面图形的几何变换 执行： 1 、平移变换： 将二维空间上的点( x ，y ) 分别在x 方向( 水平方向) 和y 方向( 垂直方向) 分别移动出和咖，则变换后点g ，y ) 坐标值为： y = y + d y 用齐次坐标表示时的变换式为： 1 0 0 k 川扪1 】。o j 。， 2 、比例变换( 缩放) ： 以原点为中心，将图形各坐标点的x 分量和y 分量分别乘以s ，s 。，则可 以使图形进行放大和缩小，这时 工= x s 。 y 。2 y s y 当s ，= s ，时，图形作相似变换；当s ，s ，时，图形产生变形。利用齐次坐 标表示的变换式为： r s ；0 o b _ y 1 】= kyl 】1 o s y o l l0 0 1 j ( 3 4 ) 3 、旋转变换： 以原点为中心，将点0 ，y ) 旋转口角度而得到新的坐标g ，y ) 的齐次坐标变换 式为： c o s 0 s i n o 0 i y 7 1 1 = k y 妇+ l 一鼍l 口。苗口：j 。， 3 2 图的显示算法 本课题要求完成图形显示有以下的主要功能： 1 、绘制网络图。根据用户输入的信息，在屏幕上绘制出其对应的图形。 2 、添加若干条边。根据用户的要求和输入的信息，在屏幕上绘制出其对应 的图形，对于新添加的边，用不同的颜色表示以明确之。 3 、添加若干个顶点。在这里，我们认为用户添加的点要构成连通图，因此 用户输入的信息还应包含新添加边的信息，然后再在屏幕上绘制出其对应的图 形。对于新添加的顶点和边，用不同的颜色表示以明确之。 4 、删除若干条边。根据用户的要求和输入的信息，在屏幕上绘制出其对应 的图形。很明显，若删除这些边后不能有孤立顶点。 5 、删除若干个顶点。根据用户的要求和输入的信息，在屏幕上绘制出其对 应的图形。当然，与这些被删除的顶点的关联的边自然也要去掉。 6 、历史查询。根据用户的需求，对每次操作进行历史记录，以方便查询。 譬如，用户在做了一次删除若干个顶点的操作。想对比前后两次的图形，就需要 查询历史了。 7 、记录时间。根据用户的要求，对每次操作进行计时。 8 、其它功能。考虑到还有图的连通性查询、图的最短路径查询等等，故在 此留下可扩展的功能块。 把上述要求综合起来，我们初步构成个网络图显示和查询系统，系统结构 如图3 2 ： 4 硕士论文网络图的计算机算法和显示方法的研究 图3 2 网络图显示和查询系统框图 3 2 1 网络图显示的算法 要在屏幕上绘制出网络图，首先需要用户输入该网络图的相关信息。 1 、网络图的输入： 第步：用户输入网络图输入指令，通知计算机执行网络图的输入。 第二步：输入有关信息。包括：顶点的个数、边的数目m 、顶点和边的 编号、顶点的坐标，等等。 第三步：创建邻接多重表，并完成对邻接多重表的数据输入。 第四步：调用本人设计的h u a _ t u ( ) 子程序进行网络图的绘制。 2 、添加若干条边： 第一步：用户输入添加边的指令。 第二步：输入添加边的有关信息，包括：新增边的数目、边的起点和终点等 等。 第三步：修改邻接多重表。对新加的顶点设置标记v i s i t e d 为疗“p 。 本人设计的修改邻接多重表的方法，以图3 3 为例说明。 首先要生成一个新的边结点，对应图中的p 位置；然后要找到新增加的边的 ls 硕士论文网络图的计算机算法和显示方法的研究 两个顶点“和v 在邻接多重表中要插入的位置，如图中的q 和，；再对两个顶点所 对应的边链表做链表的插入，插入操作如下进行： p - i l i n k = q 一 i l i n k ； q 一 i l i n k = p ； p j l i n k = r - j l i n k ； r - j l i n k = p ； 臣五丑互习圆 口， ， 川二匣厦互匝困叫卫二由 ，” v 1i i d , k ij - k l 图3 , 3 上面操作结束后，新的结点就插入邻接多重链表中，如图3 4 所示。 ， 瞳匾卜一- 臣 二 蠡 巫j 图34 一n i r _ r 、- 卜 、式i i ：二 在实际程序设计中，本人是把新加的边直接插入所对应顶点的第一个边结点 的位置上，因为邻接多重表对邻接边的顺序无严格要求。这使得插入链表操作更 简单、快捷。 3 、添加若干个】页点： 显然，添加顶点必然要添加相应的边，否则，新添加的顶点是孤立的，网络 图不连通。 第一步：用户输入添加顶点的指令。 第二步：输入有关信息，包括：新增顶点的个数n 。、新增边的数目m 以及 新增边的两个顶点编号，等等。 第三步：修改邻接多重表，对新增的顶点和边在邻接多重表的插入同上面所 述。并对新加的顶点设置标记v i s i t e d 为t r u e 。新加的边设置标记小a r k e d 为t r “e 。 1 硕士论文网络图的计算机算法和显示方法的研究 第四步：调用函数h u at u ( ) 子程序实现新网络图的绘制。 4 、删除若干条边： 第一步：用户输入删除若干条边的指令。 第二步：输入有关信息，包括：删除边的数目m ，。 第三步：根据用户输入的边的标号，在邻接多重表中把它所对应的结点去掉。 第四步：判断删除边之后的网络图是否有孤立顶点，有则去掉。 第五步：调用画图子程序h u at u ( ) 绘制新的网络图。 为了把欲删除边邻接多重表中欲删除边所对应的结点去掉，本人设计了下面 这个算法来实现。 首先查找边( v ，v ) 所对应指针p 的两个父指针g 和r 。如图3 5 所示。 图3 5 删除边( v ，v7 ) 所对应的结点( 即指针p 指向的结点) 。可按下面的算法实现： l * r q 的f z 加域指向指针p 所对应的边和指针，的弦弭七域指向指针p 所对应的边+ i f ( p 一 i v = = v )p 判断指针p 的i v 域是否为顶点v + q - i l i n k = p - i l i n k ； r - j l i n k = p - j l i n k ； ) e l s e q - i l i n k = p 一 j l i n k ； r j l i n k 2 p - i l i n k ； ) f r e e ( p ) ； 判断有无孤立顶点，本人设计如下： 硕士论文网络图的计算机算法和显示方法的研究 判断“执行完第三步后的邻接多重表中是否有顶点的f e d g e 域为n u l l ” 如果是n u l l ，则删除该顶点。 5 、删除若干个顶点： 第一步：用户输入删除若干个顶点的指令。 第二步：输入有关信息，包括：欲删除顶点的个数，及其编号。 第三步：从邻接多重表中将这些顶点( 被标了记号) 所对应的结点删去。 第四步：判断与被删除顶点关联的边，把这些边去掉。 “判断与被删除顶点相关联的边”，本人设计了一个方法，其流程图如图3 6 。 图3 , 6 硕士论文网络图的计算机算法和显重查鲨盟堑塑 假设顶点v 是欲删除的顶点，依次检查每个边结点的i v 域和v 域有无被删除 的顶点，如有则删除该结点：否则，指针移到下一个边结点，检查每个边结点的 f v 域3 l ：l j v 域有无被删除的顶点标号，如有则删之；一直下去，直到指针指向n u l l 。 第五步：调用画图子程序h u a _ t u ( ) 绘制新的网络图。 6 、历史记录查询功能： 提供查询上一次操作的历史记录，这就不仅仅要求存储操作前的网络图，还 要存储对应的数据结构。 在此，本人设计了一个较为简单的方法来实现。每次修改网络图前，把网络 图及其对应的数据结构存储的地址分别赋值给两个指针b u f f e r l 和p 。在修改网 络图完成后，再把此时的网络图及其对应的数据结构分别存储到另外两个指针 b u f f e r 2 和儿中。然后调用g e t i m a g e ( x 1 ，y l ，b u f f e r , c o p y p u t ) 函数，就可以把修改 前的网络图显示在屏幕上，调用指针p 。可得到修改前的数据结构。如果要多次查 询历史记录，只要重复上面方法即可实现。 7 、时间查询： 有时候，我们需要查询添加边、顶点或删除边、顶点等操作的时间，因为这 些操作是由多个子程序实现的，所以查询操作时间问题就演变为测量子程序的执 行时间。此外，还可以用它来测量算法程序的执行时间。为此，本人提出在i b m p c 及其兼容机上的t u r b oc 语言环境下测量程序执行时间的方法： 首先，i n c l u d e 关键字将头文件“t i m e ，h ”、“s t d d e f h ”包含到程序中，定义 两个时间变量s t a r t 和f i n i s h ； 其次，在被测程序开始处插入语句：s t a r t - - t i m e ( n u l l ) ，开始计时； 再次，在被测程序结束处插入语句：f i n i s h - - - t i m e ( n u l l ) ，计时终止； 最后，调用d i f f t i m e ( f i n i s h ，s t m ) 函数，并将其值赋给变量tt i m e 。 其中，t i m e 函数读取系统时钟时间，d i m i m e 函数则给出了两个时间之差。 程序测出的时间单位为秒( s ) 。 以图3 5 为例，在该程序段的开始处插入语句：s t a r t - - t i m e ( n u l l ) ，再在程序 段的结束处插入语句：f i n i s h = t i m e ( n u l l ) 年1 p r i n t f ( “c d i f f t i m e ( f i n i s h ，s t a r t ) ) 。程 序结束后会自动显示该程序段的执行时间。 硕士论文网络图的计算机算法和显示方法的研究 3 2 2 网络图显示中涉及的功能算法 3 2 1 中的算法的最终实现，还需要有一些辅助功能方可实现。 1 、画网络图。由函数h u at u ( ) 实现。内容如下： 第一步：根据用户输入的顶点坐标( z ，y ) 画出该点，再以点( 墨y ) 为圆心作半 径为1 的圆。这样做的好处在于使顶点显示更加明显i 否则顶点不容易在屏幕 上看出。 第二步：从第一个顶点开始，依次检查与它邻接的边是否访问过( 假设该边 的结点存储地址所对应指针p 的位置，判断p 的m a r 妇d 域值是否为乃”p ，“什“e ” 表示访问过，“f a l s e ”则表示没访问过) ，如果没访问过，则在屏幕上画出这条边： 否则，访问与之相邻接的下一条边( 让当前指针移到当前指针的下一个边结点所 对应的存储地址) ，直至所有与第一个顶点相邻接的边访问完为止。然后再对第 二个顶点，依次检查与它邻接的边是否访问过，如果没访问过，则在屏幕上画出 这条边；否则，访问与之相邻接的下一条边，直至所有与第一个顶点相邻接的边 访问完为止。接着是第三、第四个顶点、，一直到所有的顶点都被访问过为 j e 。 2 、网络图的调整：对于画好的网络图，其大小和位置可能不是太好，采用 人机对话，让用户发出相应的指令，由计算机来执行，调整网络图的大小和位置。 针对网络图的调整，本人的设计如下：本人提供几个命令给用户：缩放命令 和缩放倍数、图形平移命令和平移值、图形旋转命令和旋转的角度0 。 当屏幕的网络图显示过大或时，输入网络图的横向和纵向缩放倍数s ，和s 。 然后，对于图中的每一个顶点的坐标利用“式( 3 4 ) ”来做比例变换，新的坐标 如果不是整数要取整。再重新生成图形。 当屏幕的网络图位置过偏时，输入横向平移值和纵向平移值，用“式( 3 3 ) ” 来对图中每个顶点的位置进行改变，再对新的顶点位置重瓤生成图形。 当屏幕的网络图需要旋转时，输入旋转角度口值，用“式( 3 5 ) ”来对图中 每个顶点的位置进行改变，再对新的顶点位置重新生成图形。 3 、网络图的存储： 注意：每次画完图，都应该保存屏幕上的图形。此外，考虑到有可能要查询 历史记录，每执行一次添加边或顶点的操作、每执行一次删除边或顶点的操作后， 都有必要保存图形，以各查询。 存储屏幕图形，自然是需要的图象保存到内存罩。因此，首先定义一个指针： 硕士论文网络图的计算机算法和显示方法的研究 然后调用i m a g e s i z e ( ) 函数测量出欲保存图形的容量，即所占的字节数；最后，用 保存屏幕图象的函数将图象存储到内存中。具体操作如下： 图形初始化； 定义字节数变量： i n ts i z e ； 定义指针： v o i d + b u f f e r ； 清屏，调用c l e a r d e v i c e ( ) 函数； 画图形； 测量屏幕图形( 从左上角( x l ，_ y 1 ) 到右下角0 2 ，y 2 ) 这个矩形区域的图象) 所占用的字节数，并赋值给变量s i z e ： s i z e = i m a g e s i z e ( x l ，y l ，x 2 ，y 2 ) ； 分配缓冲区( 按字节数) ： b u f f e r = m a l l o c ( s i z e ) ； 存储图形到b “f e r 指向的内存区域里。 g e t i m a g e ( x l ，y l ，x 2 ，y 2 ，b u f f e r ) ； 4 、添加若干条边或顶点后的图形显示，本人设计了3 种方法实现。 第一种方法：利用新生成的邻接多重表直接调用画图函数h u at u ( ) 画图。 第二种方法：先调用p u t i m a g e ( ) 函数将原先的网络图从内存中调出来显示在 屏幕上，然后，直接在已生成的图上绘制新添加的边和顶点( 注意，新添加的边 和顶点说用另外一种颜色显示) 。新添加的边和顶点在邻接多重表中已有标记标 出：对于顶点，查看它的v i s i t e d 域的值是否为t r u e ，“t r u e ”表示顶点已访问过， “f a l s e ”表示没访问过；对于边，则检查它的m a r k e d 域的值是否为t r u e ，“t r u e ” 为访问过，“f a l s e ”就表示没访问过。 第三种方法：先把新添加的边和顶点在屏幕上显示出来，然后调用p u t i m a g e f ) 函数将原先的网络图从内存中调出来，并与屏幕图形进行“或”运算，再显示在 屏幕上，即得到新的完整的网络图。其主要步骤如下： 在邻接多重表中查找新添加的顶点和边； 根据这些新添加顶点的坐标将它们显示在屏幕上，再根据这些新添加边 的信息将它们显示