第七章 图.ppt

第七章图,7.1 图的定义和基本术语 7.2 图的存储结构 7.2.1数组表示法 7.2.2邻接表 7.2.3十字链表 7.2.4邻接多重表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 7.4.2 最小生成树 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点间的最短路径,在日常生活中，常用图来表示一些问题或概念，如IC设计、城市间交通道路规划、作业调度等。图和树一样，也是一种非线性数据结构。图和树的最大差异在于：树描述的是数据元素(结点)之间的层次关系，每一层上的数据元素可能和下一层中多个元素(即孩子结点)相关，但只能和上一层中一个元素相关，而图结构研究两顶点之间是否相连的关系，在图中，结点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。图结构提供了简单的方式来描述一个问题、系统或状况等。,7.1 图的定义和基本术语,图是由一个顶点集 V 和一个弧集 VR构成的数据结构。Graph=(V,VR)其中，VR|v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。谓词 P(v,w)定义了弧 的意义或信息。,图的结构定义:,由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。,AB E C D,例如:,G1=(V1,VR1),其中V1=A,B,C,D,EVR1=,若VR 必有VR,则称(v,w)为顶点v 和顶点 w 之间存在一条边。,B CA D F E,由顶点集和边集构成的图称作无向图。,例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),名词和术语,网、子图,完全图、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、强连通图、强连通分量,生成树、生成森林,A,B,E,C,F,A,E,F,B,B,C,设图G=(V,VR)和图 G=(V,VR),且 VV,VRVR,则称 G 为 G 的子图。,15,9,7,21,11,3,2,弧或边带权的图分别称作有向网或无向网。,假设图中有 n 个顶点，e 条边，则,含有 e=n(n-1)/2 条边的无向图称作完全图；,含有 e=n(n-1)条弧的有向图称作 有向完全图；,若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。,假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，,A,C,D,F,E,例如:,TD(B)=3,TD(A)=2,边(v,w)和顶点v 和w 相关联。和顶点v 关联的边的数目定义为点V的度。,B,顶点的出度:以顶点v为弧尾的弧的数目；,A,B,E,C,F,对有向图来说，,顶点的入度:以顶点v为弧头的弧的数目。,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B)=2,OD(B)=1,TD(B)=3,设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径。路径上边的数目称作路径长度。,A,B,E,C,F,如:长度为3的路径A,B,C,F,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的路径。,若图G中任意两个顶点之间都有路径相通，则称此图为连通图；,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,B,A,C,D,F,E,B,A,C,D,F,E,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,A,B,E,C,F,A,B,E,C,F,对有向图，,否则，其各个强连通子图称作它的强连通分量。,对于下图a中的非强连通图，它的强连通分量见图b。,6,3,5,4,2,1,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,B,A,