(16)有向无环图及其应用

有向无环图及其应用一、定义一个无环的有向图称为有向无环图，简写为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.方法：注意1:从某种意义下来说，拓扑排序的结果是不唯一的。注意2:这种以顶点表示活动的有向无环图称为活动在顶点的网,简称AOV(ActivityOnVertexNetwork)网。C1拓扑序列：C2C3C4C5C7C9C10C11C6C12C8二、拓扑排序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(ALGraphG){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);printf(G.vertices[i].data);++count;for(p=