数据结构 7图A.ppt

数据结构课程的内容 第7章 图 7.1 图的基本术语 例：判断下列4种图形各属什么类型？ 带权图： 邻接点： 简单路径： 小结：概念及术语 图G=(V, {E})；有向边和无向边 有向完全图（稀疏？稠密？）、网、子图 邻接(Adjacent) 度、入度和出度 路径、路径长度、回路/环、简单路径 连通图、连通分量、生成树 强连通图、强连通分量 7.2 图的存储结构 图的特点：非线性结构（m :n ） 一、邻接矩阵（数组）表示法 例2 ：有向图的邻接矩阵 特别讨论 ：网（即有权图）的邻接矩阵 图的邻接矩阵存储表示（参见教材P161） 例：用邻接矩阵生成无向网的算法（参见教材P162） 二、邻接表（链式）表示法：邻接表=头结点表+单链表 例1：无向图的邻接表 图的邻接表存储表示（参见教材P163） 例3：已知某网的邻接（出边）表，请画出该网络。 邻接表存储法的特点： 讨论：邻接表与邻接矩阵有什么异同之处？ 自学 三、十字链表/Orthogonal List（适用于有向图） 四、邻接多重表/Adjacency Multilist（适用于无向图） 三、十字链表（自学） 十字链表存储结构描述： 例：画出有向图的十字链表。 四、邻接多重表（自学） 例：画出无向图的邻接多重表 * 多对多 （m:n) 7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 图的其他运算 7.5 图的应用 图：记为 G＝( V, {E} )，其中： V 是G的顶点集合，是有穷非空集； E 是G的边集合，是有穷集。 问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。 有向图： 无向图： 完全图： 图G1中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任意两个顶点都有一条边相连接； 若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 稠密图 vs. 稀疏图 v1 v2 v3 v4 G1 v1 v2 v3 v5 v4 v4 G2 无向 无向图(树) 有向图 有向 n(n-1)/2 条边 n(n-1) 条边 G1的顶点集合为V={0,1,2,3} 边集合为E={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} 完全图 完全图 设有两个图 G＝(V, {E}) 和 G＝(V, {E})。若 V ? V 且 E ?E, 则称 图G 是 图G 的子图。 子 图： 即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。 ＝带权图 网 络： 有向边u, v 是G中的一条边，则称 u 邻接到 v。 顶点v的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。 顶点数vi和边数e的关系：无论是有向图还是无向图，其边数等于各个顶点度数总和的一半。 若 (u, v) 是G中的一条边，则称 u 与 v 互为邻接顶点 邻接到： 度、入度和出度： v1 v2 v3 v4 G1 v1 v2 v3 v5 v4 v4 G2 v1,v2 v1,v3 v4,v1 TD(v1)=1+2 (v1,v2) (v1,v4) TD(v1)=2 路径上各顶点 v1,v2,...,vm 均不互相重复。 回 路： 若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。 路径长度： 非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。 有两类图形不在本章讨论之列： 路径： 在图 G＝(V, {E}) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)应当是G的边(属于E)。 v1 v2 v3 v4 G1 v1 v2 v3 v5 v4 v4 G2 摸底：课堂提问 邻接表 邻接多重表 十字链表 设计为邻接矩阵 链式存储结构： 顺序存储结构： 无！ （多个顶点，无序可言） 但可用数组描述元素间关系。 可用多重链表 重点介绍： 邻接矩阵(数组)表示法 邻接表(链式)表示法 建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（