数据结构-07 图(2).ppt

《数据结构-07 图(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4生成树7.5有向无环图及其应用7.6最短路径结点之间关系任意，任何两点之间都可能相关，每个结点可有多个前趋和多个后继（多对多）。所有数据结构中最一般的形式，树形结构、线性结构和集合都可看成形式受限的图。7.5有向无环图及其应用有向无环图（DirectedAcyclicGraph或DAG）：无回路的有向图描述一项工程或系统进行过程：（1）整个工程能否顺利进行？（2）完成整个工程的最短时间是多少？哪些活动是影响整个工程进度关键？7.5.1拓扑排序拓扑排序

2、（TopologicalSort）由某个集合上的一个偏序得到该集合上的一个全序。偏序关系：自反的、反对称的、传递的，集合中仅有部份成员之间可以比较；全序关系：是偏序关系，且集合中所有成员之间可以比较；V1V2V4V3V2V1V3V4例某工程分为V1、V2、V3、V4、V5、V6、V7子工程，工程流程可用如下AOV网表示。顶点：表示子工程（活动）弧：表示子工程间的顺序关系。7.5.1拓扑排序顶点活动网（ActivityOnVertexnetwork，AOV网）：顶点表示活动，边表示活动之间先后关系的有向图V6V4V3

3、V1V2V5V7如何安排施工计划？例课程流程图某校计算机专业课程流程可AOV网表示。其中顶点：表示课程（活动），弧：表示课程间的先修关系；c1c2c3c4c5c6c7C8c9c10c11c12程序设计离散数学数据结构汇编语言算法分析计算机体系编译方法操作系统高等数学线性代数电子电路数值分析无c1c1,c2c1c3,c4c11c5,c3c3,c6无c9c9c9,c10,c1课程编号课程名称先决条件c4c1c2c3c12c9c10c11c6c7c3c5如何安排教学计划？一个可行施工计划：V1,V2,V3,V5,V4,V

4、6,V7,一个可行学习计划：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8可行计划的特点：若在流程图中顶点v是顶点u的前趋，则在计划序列中顶点v也是u的前趋。c4c1c2c3c12c9c10c11c6c7c3c5V6V4V3V1V2V5V7拓扑序列：有向图的一个顶点序列，满足：若顶点vi到vj有路径，则在序列中vi排在vj之前，否则vi与vj的次序任意。拓扑排序：就是将有向图中顶点排成拓扑序列。拓扑排序（TopologicalSorting）：构造拓扑序列的操作任何DAG图（有向无环

5、图）都可进行拓扑排序。有回路意味着：某些活动的开工将以自己的完成为先决条件，这种现象称为死锁，此项工程是不可行的。可用拓扑排序检查有向图是否存在回路（1）从图中选择一个入度为0的顶点且输出之。（2）从图中删掉此顶点及其所有出边。反复执行这两步，直至所有顶点都已输出，此时整个拓扑排序完成；或者直到图中剩余顶点的入度都不为0时终止，此时图中存在回路，拓扑排序不能再进行下去。为避免每次重复找入度为0的点，设置栈保存入度为0的点，则选入度为零的点时，从栈顶取出；排序中出现新的入度为0的点，就将其入栈。拓扑排序前，对顶点表扫

6、描一遍，所有初始入度为零的点入栈为便于考察入度，顶点表中增加入度域in，指示当前各点入度初始入度值在邻接表的生成过程中累计得到。也可用队列保存当前入度为0的点如果每次输出出度为0的点，则得到逆向的拓扑排序。方便在逆邻接表上进行：每个点增加出度域，也可用栈或队列保存当前出度为0的点。1c71c62c52c41c30c20c1^73^44^5^5^6datainfirst1234567nonext顶点表边表c1c2c7c6c3c4c5voidTopoSort(graphg){扫描顶点表，建立入度为零的顶点栈;while

7、(栈不空){弹出栈顶v并输出之;检查v的出边表，将其每条出边的终点w的入度减1，若变为零，则w入栈;}若输出的顶点数小于n，则输出“有回路”，否则拓扑排序正常结束;}1c71c62c52c41c30c20c1^73^44^5^5^6datainfirst1234567nonext顶点表边表c1c2c7c6c3c4c5stackc1c21c71c62c52c41c30c20c1^73^44^5^5^6datainfirst1234567nonext顶点表边表c1c2c7c6c3c4c5stackc1c2c2c201c

8、71c62c52c40c30c20c1^73^44^5^5^6datainfirst1234567nonext顶点表边表c1c2c7c6c3c4c5stackc1c2c31c71c62c52c40c30c20c1^73^44^5^5^6datainfirst1234567nonext顶点表边表c1c2c7c6c3c4c5stackc1c2c311c71c62