数据结构-有向无环图及其应用

有向无环图及其应用一、定义一个无环的有向图称为有向无环图，简写为DAG（directedacyclinegraph）。与有向二叉树相比，有向无环图是更一般的特殊有向图。实例：有向树有向无环图有向图教材179页给出了有向无环图的一个简单应用：用有向无环图描述算术表达式。二、拓扑排序1.引例：现有计算机课程12门，如下表所示：课程编号课程名称先修课程c1程序设计基础无c2离散数学c1c3数据结构c1,c2c4汇编语言c1c5语言的设计和分析c3,c4c6计算机组成原理c11c7编译原理c5,c3c8操作系统c3,c6c9高等数学无c10线性代数c9c11普通物理c9c12数值分析c9,c10,c1c1c9c4c2c12c10c11c3c5c6c7c8二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c82.拓扑排序：偏序是指集合中仅有部分元素可比较大小(或先后)；全序是指集合中所有元素均可比较大小（或先后）。二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c82.拓扑排序：拓扑排序是指将一个偏序关系转化为全序关系的过程的特殊操作。二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c83.方法：①在有向图中选择一个没有前驱（即入度为0）的顶点并输出之。②在有向图中删除刚刚输出的顶点及所有以该顶点为尾的弧。③图中若不再有入度为0的顶点，则结束；否则转①。二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c83.方法：c1拓扑序列：c2c3c4c5c7c9c10c11c6c12c8二、拓扑排序3.方法：c1拓扑序列：c2c3c4c5c7c9c10c11c6c12c8注意1：从某种意义下来说，拓扑排序的结果是不唯一的。注意2：这种以顶点表示活动的有向无环图称为活动在顶点的网，简称AOV(ActivityOnVertexNetwork)网。二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^datafirstarcadjvexnextarc另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]021230012345二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]021230012345求indegree一维数组初值的程序：FindInDegree(ALGraphG,indegree[0..G.vexnum-1]{for(i=0;iG.vexnum;++i){p=G.vertices[i].firstarc;while(p){k=p-adjvex;++indegree[k];p=p-nextarc;}}}//FindInDegree二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]021230012345拓扑排序算法思想：①设一个栈S，入度为0的顶点的序号进栈。如0，5进栈。count=0(打印顶点个数计数器)。②当栈S不空时，出栈一个元素并打印相应顶点；count加1。该顶点的所有邻接点的入度减1，减1后入度为0的顶点的序号进栈。③重复第二步，直至栈空时转④。④若count=G.vexnum,则拓扑排序成功；否则图中必有环路，拓扑排序失败。二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]02123001234550s二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]0212300123450s5打印G.vertices[5].data4号和3号顶点的入度分别减1二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]0211200123450s二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]021120012345s0打印G.vertices[0].data3号、2号、1号顶点的入度分别减1二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]01002001234523s二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]01002001234523s二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]0100200123453s2打印G.vertices[2].data4号、1号顶点的入度分别减1二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]00001001234513s二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]0000100123453s1打印G.vertices[1].data二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]0000100123453s二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]000010012345s3打印G.vertices[3].data4号顶点的入度减1二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]0000000123454s二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组indegree:indegree[0..5]000000012345s4打印G.vertices[4].data最后输出的拓扑序列为：v6v1v3v2v4v5二、拓扑排序4.程序：StatusTopologicalSort(ALGraph){FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;++i)if(!indegree[i])Push(S,i);//入度为0的顶点的序号进栈count=0;while(!StackEmpty(S)){Pop(S,i);coutiG.vertices[i].data;++count;for(p=G.verti