数据结构详细教案——图.doc

数据结构教案第七章图第7章图【学****目标】 。 ,了解各种存储结构的特点及其选用原则。 。 。【重点和难点】图的应用极为广泛,而且图的各种应用问题的算法都比较经典,因此本章重点在于理解各种图的算法及其应用场合。【知识点】图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径【学****指南】离散数学中的图论是专门研究图性质的一个数学分支,但图论注重研究图的纯数学性质,而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构,因此和线性表、树不同,虽然在遍历图的同时可以对顶点或弧进行各种操作,但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法,在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难,应多对照具体图例的存储结构进行学****而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似,应将两者的算法对照学****以便提高学****的效益。【课前思考】,即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图?,那么从图看出哪些路可以同时通行?同时可通行的路为:(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)目录第7章图 12图图的定义和基本术语图的特征任意两个数据元素之间都可能相关。结点之间的关系是多对多的。G=(V,{E})基本术语结点: 顶点结点间的关系:无向图:边(v,w),v与w互为邻接点,边(v,w)依附于顶点v,w,边(v,w)和顶点v,w相关联v的度:和v相关联的边的数目。有向图:弧<v,w>,v弧尾,w弧头,顶点v邻接到顶点w,顶点w邻接自顶点v,弧<v,w>和顶点v,w相关联。v的入度:以v为弧头的弧的数目;v的出度:以v为弧尾的弧的数目;v的度:v的入度与出度之和。路径、回路(环)、简单路径、简单回路(简单环)连通性:若从顶点v到顶点v’有路径,则称v和v’是连通的图的规模:顶点数n、边(弧)数e、顶点的度(有向图:入度/出度)子图:G’=(V’,{E’}),G=(V,{E}),若V’ÍV且E’ÍE,则称G’是G的子图。图的分类:1)关系的方向性(无向/有向)、关系上是否有附加的数——权(图/网)有向图、无向图、有向网、无向网2)边(弧)数:完全图(边数=n(n-1)/2的无向图)、有向完全图(弧数=n(n-1)的有向图)稀疏图(e<nlogn)、稠密图(e>nlogn)3)连通性:无向图:连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林有向图:强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林抽象数据类型定义ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。数据关系R:R={VR}VR={<v,w>|v,wÎV且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作:CreateGraph(&G,V,VR)初始条件:V是图的顶点集,VR是图中弧的集合操作结果:按V和VR的定义构造图GDestroyGraph(&G)初始条件:图G存在操作结果:销毁图GLocateVex(G,u)初始条件:图G已存在,u和G中顶点有相同特征操作结果:若G中存在顶点u,则返回该顶点在图中位置,否则返回其它信息GetVex(G,v)初始条件:图G存在,v是G中某个顶点操作结果:返回v的值PutVex(&G,v,value)初始条件:图G存在,v是G中某个顶点操作结果:对v赋值valueFirstAdjVex(G,v)初始条件:图G存在,v是G中某个顶点操作结果:返回v的第一个邻接顶点。若顶点在G中没有邻接顶点,则返回“空”NextAdjVex(G,v,w)初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点操