数据结构第7章剖析.ppt

第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 一、图的定义(Graph) 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E ) 其中V = {x | x?数据对象}是顶点的有穷非空集合 E是顶点之间关系的有穷集合。 二、图的术语 图可分为有向图和无向图 若x,y∈ E，则x,y表示从x到y的一条弧(Arc)，且称x为弧尾，y为弧头。此时的图称为有向图。 二、图的术语 二、图的术语 如果无向图有n(n-1)/2条边，则称无向图为完全图。 对于无向图G=（V,E) 邻接点：如果(x,y)?E,称x,y互为邻接点，即x,y相邻接 依附：边(x,y)依附于顶点x,y 相关联：边(x,y)与x,y相关联 顶点的度：和顶点相关联的边的数目，记为TD(x) 对于有向图G=（V,E) 邻接：如果x,y?E,称x邻接到y,或y邻接自x 相关联：弧x,y与x,y相关联 入度：以顶点为头的弧的数目，记为ID(x) 出度：以顶点为尾的弧的数目，记为OD(x) 度：TD(x)=ID(x)+OD(x) 路径：是一个从顶点x到y的顶点序列(x, vi1, vi2,…, vin, y) 其中，(x,vi1),…(vij-1,vij),…(vin,y)皆属于E 路径的长度：路径上的边或弧的数目 回路或环：路径的开始顶点与最后一个顶点相同，即路径中(x, vi1, vi2,…, vin, y)，x=y 简单路径：路径的顶点序列中，顶点不重复出现 简单回路或简单环：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路 在无向图中： 连通：如果顶点x到y有路径，称x和y是连通的 连通图：图中所有顶点都连通 连通分量：无向图中的极大连通子图 在有向图中： 强连通图：对于每一对顶点vi、vj，从vi到vj和从vj到vi都存在路径。 强连通分量: 有向图的极大强连通子图 一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 一、数组表示法（邻接矩阵） 用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。 例：无向图的邻接矩阵为：　有向图的邻接矩阵为： 对于带权的图（网），两个顶点如果不邻接，则被视为距离为无穷大；如果邻接，则两个顶点之间存在一个距离值(即权值) wi,j 如果(i,j)?E 或 i,j?E A[i][j] = ∞ 其它 例： #define INFINITY = INT_MAX; 　　　　// 最大值∞ #define MAX_VERTEX_NUM = 20;　　　　// 最大顶点个数 typedef enum {DG, DN, AG, AN} GraphKind; 　　　　　　　　 typedef struct ArcCell { 　　　　// 弧的定义 VRType adj; 　　　　　　 // VRType是顶点关系类型。InfoType *info; 　　　　　　// 该弧相关信息的指针} ArcCell ,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { 　　　　　　　// 图的定义VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息AdjMatrix arcs; 　　　　　　　　// 表示顶点之间关系的二维数组int vexnum, arcnum; 　　　　　　// 图的当前顶点数和弧(边)数GraphKind kind; 　　　　　　　　// 图的种类标志} MGraph; 二、邻接表(Adjacency List) 邻接表是图的一种链式存储结构。在邻接表中，每个顶点设置一个单链表，其每个结点都是依附于该顶点的边（或以该顶点为尾的弧） 例2：有向图 例3：网 图的邻接表存储表示 三、十字链表(Orthogonal List) 十字链表是有向图的另一种存储结构，是将有向图的邻接表和逆邻接表结合起来的一种存储结构。 四、邻接多重表(Adjacency Multilist) 邻接多重表是无向图的另一种存储结构， 在邻接表中，一条边要用2个结点表示(分别从2个顶点的角度看)；在邻接多重表中，一条边只用一个结点表示。 例4：邻接