数据结构详细教案——图

第0页数据结构教案第七章图数据结构教案第7章图第0页第7章图【学习目标】1．领会图的类型定义。2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。3．熟练掌握图的两种遍历算法。4．理解各种图的应用问题的算法。【重点和难点】图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。【知识点】图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径【学习指南】离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。【课前思考】1.你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的五叉路口交通管理示意图相类似的图？2.如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)数据结构教案第7章图第0页目录第7章图..............................................................................................................................................17.1图的定义和基本术语.............................................................................................................17.2图的存储和创建.....................................................................................................................27.2.1图的存储表示..............................................................................................................27.2.2图的创建......................................................................................................................47.3图的遍历.................................................................................................................................57.3.1深度优先搜索..............................................................................................................57.3.2广度优先搜索..............................................................................................................67.4遍历算法的应用.....................................................................................................................77.4.1应用问题概述..............................................................................................................77.4.2求一条包含图中所有顶点的简单路径.......................................................................87.4.3求距v0的各顶点中最短路径长度最长的一个顶点.................................................97.5图的连通性问题...................................................................................................................107.5.1无向图的连通分量和生成树....................................................................................107.5.2最小生成树................................................................................................................117.6有向无环图及其应用...........................................................................................................12数据结构教案第7章图第1页1第7章图7.1图的定义和基本术语1、图的特征任意两个数据元素之间都可能相关。结点之间的关系是多对多的。G=(V,{E})2、基本术语结点：顶点结点间的关系：无向图：边(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)的有向图)稀疏图(enlogn)、稠密图(enlogn)3）连通性：无向图：连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林有向图：强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林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，则返回该顶点在图中位置，否则返回其它信息数据结构教案第7章图第2页2GetVex(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的邻接顶点操作结果：返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”InsertVex(&G,v)初始条件：图G存在，v和G中顶点有相同特征操作结果：在图中增添新顶点vDeleteVex(&G,v)初始条件：图G存在，v是G中某个顶点操作结果：删除G中顶点v及其相关的弧InsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点操作结果：在图G中增添弧v,w，若G是无向的，则还应增添对称弧w,vDeleteArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点操作结果：删除G中的弧v,w，若G是无向的，则还应删除对称弧DFSTraverse(G,v,visit())初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败BFSTraverse(G,v,visit())初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败}ADTGraph7.2图的存储和创建7.2.1图的存储表示1、图的存储表示分析∵顶点之间的关系是多对多的(m:n)，由于m和n都是不定的，无法给出一个这种多对多的关系向线性关系的映射公式∴图中的关系不能通过顺序映像(即通过顶点之间的存储位置反映顶点之间的逻辑关系)反映；必须另外引入存储空间反映顶点之间的邻接关系。图的存储结构：1）顶点信息；2）边(弧)信息；3）整体信息：顶点数、边(弧)数、图的种类(有向图、无向图、有向网、无向网)顶点集的存储：∵图的应用中，顶点集动态变化的几率十分小数据结构教案第7章图第3页3∴顶点集可以采用顺序表存储，按预先估计的最大顶点数分配空间（顺序表和链表：若数据元素集是静态的，采用顺序表要好(随机存取)；若数据元素集是动态的，则采用链表要好(动态分配与释放)）#defineMAX_VERTEX_NUM20/*最大顶点数*/注意：顺序表与顺序映像之间的区别关系集的存储：在顶点确定的情况下，边或弧的数目也是不定的；且在实际应用中，可能会改变图中顶点之间的关系。邻接矩阵表示法：矩阵中的第i行第j列的元素反映图中第i个顶点到第j个顶点是否存在弧；若存在，其附加的信息是什么。邻接表表示法：将每一顶点的邻接点位置串成一个链，称为邻接表。对于有向图/网来说，该邻接表反映的是顶点的出边表。typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图，有向网，无向图，无向网}*/2、邻接矩阵表示法（数组表示法）无向图/网：对称矩阵有向图/网：非必是对称矩阵图：邻接关系用1/0表示网：邻接关系需要进一步反映权值，用INFINITY表示无穷大，反映顶点之间无邻接关系#defineINT_M