数据结构六.ppt

第六章 图（Graph） 6·1 图的概念 6.1.1 图的定义 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 图的术语(1) 顶点--图中的数据元素。 边--连接图中顶点的连线，表示两个顶点之间的某种关系。可以用顶点对来表示，如图6.1.1(a)中顶点V1和V2之间的关系可以用(V1,V2)表示，图6.1.1(b)中顶点V1到顶点V2之间的关系可以用V1,V2来表示。 弧--连接图中顶点的有向连线，表示两个顶点之间的某种关系。可以用顶点对来表示，图6.1(b)中顶点V1到顶点V2之间的关系可以用顶点对V1,V2来表示。 图的术语(2) 弧头--弧的终止顶点。 弧尾--弧的开始顶点。 无向图--由顶点和边组成，边不具备方向性。 有向图--由顶点和弧组成。 术语(3) 无向完全图--图中的任意两个顶点之间都存在一条边。n个顶点的无向图有n(n-1)/2条边（最大边数是n(n-1)/2） 有向完全图--图中的任意两个顶点之间都存在一对相反方向的弧。有n(n-1)条边（最大边数是n(n-1) ） 稀疏图--具有很少边或弧的图。 稠密图--具有很多边或弧的图。 权--与图中的边或者弧相关的数。 网--带权图。带权的有向图叫有向网，带权的无向图叫无向网 术语(4) 子图--如果存在这样的两个图： G={V,E} G’={V’,E’} 那么称图G’是图G的子图。 术语(5) 路径--从起始顶点到终止顶点所经过的顶点的序列。 路径长度--路径上边或者弧的数量。 简单路径--没有重复顶点的路径。 回路(环)——第一个顶点和最后一个顶点相同的路径 简单回路(简单环)——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路 术语(3) 邻接--如果(Vi,Vj)是E(G)中的一条无向边,那么顶点Vi和顶点Vj是邻接的；如果Vi,Vj是E(G)中的一条有向边,那么顶点Vi邻接到（至）Vj,顶点Vj邻接自Vi的。 关联--如果(Vi,Vj)是E(G)中的一条无向边,那么边(Vi,Vj)是和顶点Vi、Vj相关联的；如果Vi,Vj是E(G)中的一条有向边, 那么边Vi,Vj是和顶点Vi、Vj相关联的。 术语(3) 连通图与连通分量— 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。 如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 术语(4) 度：无向图中，和某顶点相关联的边的数量，称为这个顶点的度。 入度：有向图中，以某个顶点为弧头的弧的数量，称为这个顶点的入度。 出度：有向图中，以某个顶点为弧尾的弧的数量，称为这个顶点的出度。 ADT Graph｛ Dset： 非空有限顶点集合V。 Rset： 非空有限顶点由多条边连接起来，构造成的顶点和边的关系。 OPSet： CreateGraph(G); 建立图的算法 DestroyGraph(G); 删除图的算法 LocateVex(G,v); 在图中查找顶点v GetVex(G,v); 获取顶点v的值 PutVex(G,v,value); 修改顶点v的值 DFSTraverse(G,v); 从顶点v开始，对图进行深度优先搜索 BFSTraverse(G,v); 从顶点v开始，对图进行宽度优先搜索｝ 6.2 图的存储结构 6．2．1 邻接矩阵表示法 对于有n个顶点的图，就定义一个n阶矩阵，把各个顶点之间存在的、不存在的边都穷举出来。对于不存在的边，带权图和不带权图的实现上有所差别。 无向图邻接矩阵分析: 邻接矩阵是对称的； 顶点i 的度＝第 i 行 (列) 中1 的个数； 特别：完全图的邻接矩阵中，对角元素为0，其余全1。 ∞ ∞ 10 ∞ 20 5 ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ ∞ 6 ∞ 9 ∞ ∞ ∞ 11 ∞ ∞ ∞ 2．邻接矩阵的实现 基于邻接矩阵表示的图的建立算法CreateGraph(Graph g) cout请输入边的数量; cing.edge_num; cout请输入顶点的数量; cing.vertex_num; g.data = new int *[g.vertex_num]; for(n=0;ng.vertex_num;n++) g.data[n] = new int[g.vertex_num]; for(first=0;firstg.vertex_num;first++)