蛤蟆的数据结构笔记之十的有向无环图的应用排序.doc

47. 蛤蟆的数据结构笔记之四十七的有向无环图的应用排序 本篇名言：“君子喻于义 , 小人喻于利。 -- 孔丘” 接下去来看下有向无环图。 1. 有向无环图 一个无环的有向图称做有向无环图（directed acycline praph）。简称DAG 图。DAG 图是一类较有向树更一般的特殊有向图，图1 给出了有向树、DAG 图和有向图 有向无环图是描述含有公共子式的表达式的有效工具。例如下述表达式： ((a+b)*(b*(c+d)+(c+d)*e)*((c+d)*e) 图2 所示。仔细观察该表达式，可发现有一些相同的子表达式，如(c+d)和(c+d)*e 等，在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。例如图8.32 所示为表示同一表达式的有向无环图。 检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环；而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v 出发的遍历，在dfs(v)结束之前出现一条从顶点u 到顶点v 的回边，由于u 在生成树上是v 的子孙，则有向图必定存在包含顶点v 和u 的环。 有向无环图是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程（project）都可分为若干个称作活动（activity）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。 对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行：二是估算整个工程完成所必须的最短时间。 第一个问题就是排序，第二个问题就是关键路径。 2. AOV网 在有向图中若以顶点表示活动，用有向边表示活动之间的优先关系，则这样的有向图称为以顶点表示活动的网（Activity On Vertex Network），简称AOV网。 3. 拓扑排序 拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若u，v ∈E(G)，则u在线性序列中出现在v之前。?? 　通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。 如下图3 最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。 4. 代码实现 主要是两部分，一部分是创建图，另一部分是进行排序。 4.1 Main函数 输入1调用函数Creat_Graph1创建，输入2调用dfs_topsort进行拓扑排序，输入3结束程序。 4.2 定义结构体 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode,*Arclink; typedef struct VNode{ char data; Arclink firstarc; }VNode,AdjList[20]; typedef struct{ AdjList vertices; int vexnum,arcnum; }ALGraph,*GLink; 定义边，顶点的结构体。 点包含一个字符类型和第一条边。 边包含一个整型表示邻结的点和下一条边。 图包含点的数组，顶点数量和边数量。 4.3 Creat_Graph1 输入顶点数，输入边数，输入所有顶点，输入所有边。 创建方式是链表链接的方式。具体可以查看之前的笔记。 如下图4创建 4.4 dfs_topsort 设置两个数组visited数组，finished 数组。 数组值都设置为0. 设置一个flag值为1. 然后输入起始点编号。 从最后一个点开始，如果visited[i]==0,则调用dfs函数。 Dfs函数输入参数为图指针,i,flag。 4.5 dfs dfs函数输入参数为图,i,flag。 先输出点i的值。然后得到该点的第一个边。 然后判断该点的第一个边是否为NULL，如果为NULL，则输出该点后，直接退出。 否则，继续输出和该点链接的第一个点，同时设置该点的finished[]数组中对应值为1，表示已经排序输出了。接着递归调用dfs函数继续输出点。直到顺序输出排序。 最后输出flag为0.