有向无环图及其应用

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

1、7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径￡7.5有向无环图及其应用￡7.5.1有向无环图有向无环图（directedacyclinegraph）：无环的有向图，简称DAG图。DAG图是一类较有向树更一般的特殊有向图。图7.15有向树、DAG图和有向图一例例如，图7.15示例了有向树、DAG图和有向图的例子。（2）表达式子式共享例如，下述表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)，用二叉树表示如图7.16所示，用有向无环图表示如图7.17所示。图7.16用二叉树描述表达式*+***+e++

2、+*abbccddecd图7.17描述表达式的有向无环图*+eabcd*+*+*表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)￡7.5.2拓扑排序全序关系：R是集合X上的偏序，若对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。（1）定义拓扑排序（TopologicalSort）：简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。偏序关系：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。（2）AOV-网AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网（Acti

3、vityOnVertexNetwork），简称AOV-网。在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱；j是i的后继。若是网中的一条弧，则i是j的直接前驱；j是i的直接后继。例如，一个软件专业的学生必须学习一系列基本课程(如图7.18所示)，其中有些课程是基础课，它独力于其他课程，如《高等数学》；而另一些课程必须在学完作为它的基础的先修课程才能开始。如，在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先（优先）关系。这个关系可以用有向图7.19清楚的表示。图7.18软件专业的学生必须学习的课程课程编号课程名称先决条件C

4、1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原理C3，C5C8操作系统C3，C6C9高等数学无C10线性代数C9C12数值分析C9，C10，C1C11普通物理C9图7.19表示课程之间优先关系的有向图C4C5C1C2C3C7C12C8C6C9C10C11图7.19中，顶点表示课程，有向边（弧）表示先决条件。若课程i是课程j的先决条件，则图中有弧。如下，为图7.19中的有向图的拓扑有序序列的其中两个序列：1．(C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8)2．(C9,

5、C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8)（3）拓扑排序①算法思想：1．在有向图中选一个没有前驱的顶点且输出之。2．从图中删除该顶点和所有以它为尾的弧。3．重复上述两步，直至全部顶点均已输出，或者当前图中步存在无前驱的顶点为止。②算法实现：针对上述操作，采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree）。入度为0的顶点即为没有前驱的顶点，删除顶点及以它为弧的操作，则可换以弧头顶点的入度减1来实现。StatusTopologicalSort(ALGraphG){//有向图G采用邻接表存储结构。//若G无回路，则输出G的顶点的

6、一个拓扑序列，并返回OK，否则ERROR。FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum－1]InitStack(S);for(i=0;inextarc){

7、k=p－>adjvex;//对i号顶点的每个邻接点的入度减1if(!(――indegree[k]))Push(S,k);//若入度减为0，则入栈}//for}//whileif(count