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

《数据结构有向无环图及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、有向无环图及其应用一、定义一个无环的有向图称为有向无环图，简写为DAG（directedacyclinegraph）。与有向二叉树相比，有向无环图是更一般的特殊有向图。实例：有向树有向无环图有向图教材179页给出了有向无环图的一个简单应用：用有向无环图描述算术表达式。二、拓扑排序1.引例：现有计算机课程12门，如下表所示：课程编号课程名称先修课程c1程序设计基础无c2离散数学c1c3数据结构c1,c2c4汇编语言c1c5语言的设计和分析c3,c4c6计算机组成原理c11c7编译原理c5,c3c8操作系统c3,

2、c6c9高等数学无c10线性代数c9c11普通物理c9c12数值分析c9,c10,c1c1c9c4c2c12c10c11c3c5c6c7c8二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c82.拓扑排序：偏序是指集合中仅有部分元素可比较大小(或先后)；全序是指集合中所有元素均可比较大小（或先后）。二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c82.拓扑排序：拓扑排序是指将一个偏序关系转化为全序关系的过程的特殊操作。二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c

3、83.方法：①在有向图中选择一个没有前驱（即入度为0）的顶点并输出之。②在有向图中删除刚刚输出的顶点及所有以该顶点为尾的弧。③图中若不再有入度为0的顶点，则结束；否则转①。二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c83.方法：c1拓扑序列：c2c3c4c5c7c9c10c11c6c12c8二、拓扑排序3.方法：c1拓扑序列：c2c3c4c5c7c9c10c11c6c12c8注意1：从某种意义下来说，拓扑排序的结果是不唯一的。注意2：这种以顶点表示活动的有向无环图称为活动在顶点的网，简称AO

4、V(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]0212300

5、12345二、拓扑排序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,in

6、degree[0..G.vexnum-1]{for(i=0;iadjvex;++indegree[k];p=p->nextarc;}}}//FindInDegree二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G

7、.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,则拓扑排序成功；否则图中必有环路，拓扑排序失

8、败。二、拓扑排序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