大学数据结构课件--第7章 图.pptx

第7章 图? 7.1 基本术语? 7.2 存储结构? 7.3 图的遍历? 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径bacdbacdv4e7.1 图的基本术语V=vertex E=edge图：记为 G＝( V, E ) 其中：V 是G的顶点集合，是有穷非空集； E 是G的边集合，是有穷集。问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。G1=(V1,E1)，其中V1={a,b,c,d}, E1={a,b,a,c,c,d,d,a}G2=(V2,E2), 其中V2={a,b,c,d,e},E2={(a,b),(a,d),(b,c),(b,e),(c,e) ,(c,d) ,(d,e)}7.1 图的基本术语有向图：无向图：图G中的每条边都是有方向的；图G中的每条边都是无方向的；若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图证明：①无向完全图有n(n-1)/2 条边。证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，…，顶点n-1有1条边,顶点n有0条边.总边数＝ n-1＋ n-2＋…＋1＋0=（n-1+0)n/2= n(n-1)/2 ②有向完全图有n(n-1)条边。证明：若是完全有向图，则顶点1必与所有其他顶点各有2条连线，即有2(n-1)条边， 顶点2有2(n-2)条边，…，顶点n-1有2条边,顶点n有0条边.总边数＝2( n-1＋ n-2＋…＋1＋0)=2(n-1+0)n/2= n(n-1)7.1 图的基本术语例：判断下列4种图形各属什么类型？有向图有向完全图无向完全图无向图(树)n(n-1) 条边n(n-1)/2 条边7.1 图的基本术语稀疏图：稠密图：边较少的图。通常边数n2边很多的图。无向图中，边数接近n(n-1)/2 ； 有向图中，边数接近n(n-1) 设有两个图 G＝(V, E) 和 G’＝(V’, E’)。若 V’ ? V 且 E’ ?E, 则称 图G’ 是 图G 的子图。子 图：bacdbacdv4e7.1 图的基本术语网 络：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。邻接点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接点。顶点和边(u, v)相关联。弧头和弧尾：有向边u, v称为弧，边的始点u叫弧尾，终点v叫弧头度、入度和出度： 顶点v的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为头的弧的数目, 记作 ID(v); 顶点 v 的出度是以 v 为尾的弧的数目,记作 OD(v)。bacdv4e7.1 图的基本术语路 径：在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)应当是属于E的边。非带权图的路径长度是指此路径上边的条数；带权图(网络)的路径长度是指路径上各边的权之和。路径长度：简单路径：路径上各顶点 v1,v2,...,vm 均不互相重复。回 路：若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。有两类图形不在本章讨论之列：例：AAABCBABBCDDCCDEDEF7.1 图的基本术语连通图：在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图：在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。7.1 图的基本术语生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。生成森林：若干棵生成树的集合，含全部顶点，但构成这些树的边或弧是最少的。7.2图的存储结构图的特点：非线性结构（m :n ）顺序存储结构：无！（多个顶点，无序可言）但可用数组描述元素间关系。链式存储结构：可用多重链表设计为邻接矩阵邻接表邻接多重表十字链表邻接矩阵(数组)表示法邻接表(链式)表示法重点介绍：1，如果i,j∈E或者(i,j) ∈E0，否则A.Edge[i][j]=7.2图的存