VC++有向无环图所有拓扑序列的生成(5)
时间:2017-06-09 23:08 来源:毕业论文 作者:毕业论文 点击:次
实际上，本文所提出的全拓扑排序算法实质上是拓扑排序算法思想用编程语言实现在计算机上求出所有可能的拓扑序列，这是因为现有的基于栈结构的拓扑排序算法的实现只能求得其中一个拓扑序列。 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 //顶点结点类 (责任编辑：qin) |