数据结构课件第7章节.pptVIP

数据结构课程的内容; ;基本内容： 7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径; ;ADT Graph { 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。 数据关系 R：R={VR}； VR={v,w|v,w∈V 且 P(v,w), v,w表示从v到w的弧， 谓词P(v,w)定义了弧v,w的意义或信息. };7.1.2 图的基本术语;2. 边、无向图; ;4.子图;5. 完全图、稀疏图、稠密图;例：判断下列4种图形各属什么类型？;6. 邻接点、度、入度、出度;7. 路径、路径长度、简单路径、简单回路;; ; 9．强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 ;10. 生成树、生成森林;A; ;7.2 图的存储结构;一、邻接矩阵（数组）表示法;分析1：无向图的邻接矩阵是对称的； 分析2：对于无向图来说，顶点i 的度＝第 i 行 (列) 中1 的个数； 特别：完全图的邻接矩阵中，对角元素为0，其余全1。;例2 ：有向图的邻接矩阵;邻接矩阵：; 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。;二、邻接表（链式）表示法;例1：已知某网的邻接（出边）表，请画出该网络。;例1：无向图的邻接表;分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。;讨论：邻接表与邻接矩阵有什么异同之处？;三、十字链表（适用于有向图）; 它是有向图的另一种链式结构。 思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。 1、每条弧对应一个结点(称为弧结点，设5个域） 2、每个顶点也对应一个结点（称为顶点结点，设3个域）;0;v1;0;一、深度优先有哪些信誉好的足球投注网站 二、广度优先有哪些信誉好的足球投注网站 ;一、深度优先有哪些信誉好的足球投注网站( DFS );深度优先有哪些信誉好的足球投注网站（遍历）步骤：;讨论1：计算机如何实现DFS？;讨论2： DFS算法如何编程？;v1;讨论3：在图的邻接表中如何进行DFS？;DFS 算法效率分析:;二、广度优先有哪些信誉好的足球投注网站( BFS );广度优先有哪些信誉好的足球投注网站（遍历）步骤：;讨论1：计算机如何实现BFS？;讨论2： BFS算法如何编程？;v1;7.4 图的连通性问题;A L M J B F C;  D E; G K H I; ;2. 无向图的生成树 ;起始点; 由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度优先生成树。这样的生成树是由遍历时访问过的n个顶点和遍历时经历的n-1条边组成。 对于非连通图,每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树,各个连通分量的生成树组成非连通图的生成森林。;深度优先生成森林;7.4.3 求最小生成树;最小生成树有如下重要性质(MST性质)：  设 N=(V, {E}) 是一连通网，U 是顶点集V的一个非空子集。 若（u , v）是一条具有最小权值的边， 其中u∈U， v∈V-U， 则存在一棵包含边（u , v）的最小生成树。 ; 用反证法来证明这个MST性质：  假设不存在这样一棵包含边（u , v）的最小生成树。 任取一棵最小生成树T，将（u , v）加入T中。根据树的性质，此时T中必形成一个包含（u , v）的回路， 且回路中必有一条边（u′, v′）的权值大于或等于（u , v）的权值。 删除（u′, v′），则得到一棵代价小于等于T的生成树T′，且T′为一棵包含边（u , v）的最小生成树。 这与假设矛盾， 故该性质得证。  利用MST性质来生成一个连通网的最小生成树。 普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法便是利用了这个性质。 ; 普里姆算法 (Prim算法,又称边割法) 1957年由Prim提出 假设N=(V, {E})是连通网，TE为最小生成树中边的集合。 Step1: 初始U={u0} (u0∈V), TE=φ；  Step2: 在所有u∈U, v∈V-U的边中选一条代价最小的边(u0