菜单
  

        实际上,本文所提出的全拓扑排序算法实质上是拓扑排序算法思想用编程语言实现在计算机上求出所有可能的拓扑序列,这是因为现有的基于栈结构的拓扑排序算法的实现只能求得其中一个拓扑序列。
    2.2 基于栈结构的单拓扑序列求解方法
    拓扑排序算法用计算机语言编程实现,在以往的教材和研究中用到的数据结构是堆栈。堆栈是一种后进先出的线性存储结构,每次只能访问栈顶元素,也就是说,如果入度为0的顶点是压栈保护的,则每次只能访问到位于栈顶的入度为0的顶点,使得同一时刻多种可能的输出只能得到一种。
    在介绍栈结构的单拓扑排序前,下面先介绍图结构的存储及其C++类。
    2.2.1 图的存储结构
    图是比线性表、树和集合更一般、更复杂的数据结构。在线性结构中,每个数据顶点只有一个直接前驱和一个直接后继顶点。在树结构中,数据顶点之间有着明显的层次关系,同层的每个数据顶点可以与它下一层的零个或多个顶点,但只能与上一层中的一个顶点相关。集合结构中,数据顶点间除了同属于一个集合的联系外没其他关系。然而在图结构中,数据顶点的关系是任意的,每个顶点都可以和任何其他顶点相关。
    图的存储结构有很多种,其中矩阵表示法和邻接表表示法比较常见。鉴于下面要用到图结构的邻接表表示,所以在这里着重讲述图的邻接表表示法。
    作为图的一种有效存储表示方法,在邻接表中,为图的每一个顶点u建立一个单链表,链表中每个结点代表一条边<u,v>,称为边结点。这样,顶点u的单链表记录了邻接自u的全部顶点。
    边结点通常具有图2.2(a)所示的格式,其中dest域指示u的一个邻接点v,link指向u的下一个邻接点。如果是网,则增加一个cost域存储边上的权值,如图2.2(c)所示。每个单链表可设立一个存放顶点u有关信息的结点,其结构如图2.2(b)所示。其中,data域存放顶点的名称及其他信息,link指向u的第一个边顶点。我们可以将头顶点按顺序存储方式组织成一文数组,在编程实现时,习惯直接使用顶点序号来标识顶点信息,因此头结点中的data域可以省略,图1.1所示的AOV网其实际的邻接表表示结果如下页图2.3所示。
    (a) 边结点                           (b) 顶点结点
    (c) 带权的边结点
    图 2.2  临接表中各种顶点的结构
    C++具体实现如下:
    图的边结点类和顶点类分别是:
    class Edge
    {                                     //边结点类
    public:
                  int dest;                        //入边指向的顶点编号
                  int cost;                        //该边权值
                  Edge*link;                      //下一个边
    };
    class Vertex                              //顶点结点类
  1. 上一篇:混合云环境下基于失效感知的调度策略
  2. 下一篇:基于FitNium的Web关键字驱动的测试
  1. 基于VC++的GIS矢量图形系统开发

  2. VC++的高速数据采集系统的软件设计

  3. VC++局域网远程控制软件的设计

  4. VC++局域网监控系统的设计与实现

  5. VC++电能质量监测系统设计

  6. VC++网络版中国象棋的设计

  7. VC++语音的频率域特征分析

  8. 河岸冲刷和泥沙淤积的监测国内外研究现状

  9. 电站锅炉暖风器设计任务书

  10. 乳业同业并购式全产业链...

  11. 当代大学生慈善意识研究+文献综述

  12. 十二层带中心支撑钢结构...

  13. 中考体育项目与体育教学合理结合的研究

  14. 酸性水汽提装置总汽提塔设计+CAD图纸

  15. 杂拟谷盗体内共生菌沃尔...

  16. 大众媒体对公共政策制定的影响

  17. java+mysql车辆管理系统的设计+源代码

  

About

751论文网手机版...

主页:http://www.751com.cn

关闭返回