电子科技大学软件技术基础课件 图结构.ppt

图的定义、术语 4.1图的定义和术语 图是由非空的顶点组成的有限集和边的有限集组成。 二元组 G = （ V，E） V：顶点集合 E：边的集合，即顶点间的关系 图结构中的关系可以是任意的，甚至可以是空集 图是一种对结点的前驱和后继个数不加限制的数据结构 图的术语 1）有向图与无向图 由有向边组成的图，称为有向图 有向边以 X，Y 表示，又称为弧 X：弧尾 Y：弧头 有向边X，Y与Y，X不是同一条边 由无向边组成的图，称为无向图 无向边以（X，Y）表示 无向边（X，Y）与（Y，X）是同一条边 图的术语 2）权与网 图中边或弧所具有的相关数称为权 一般用于表明从一个顶点到另一个顶点的距离或耗费 带权的图称为网 3）邻接与顶点的度 对于（X，Y）∈E 则X ，Y互为邻接 对于 X，Y ∈E 则Y是X的邻接结点 图的术语 顶点的度 课堂练习，给出以下顶点的度 图的术语 4）路径与回路 路径：图中沿着各条边，从X到Y所经历的顶点序列称为路径 路径：X ， b ， a ， Y 环：第一顶点与最后一个顶点相同的路径称为环 环：X，a，Y，b，X 回路： 序列中不出现重复的路径称为简单路径 有重复的路径称为回路 回路：X，a，b，a，Y 图的术语 5）连通、连通图与连通分量 连通：在图中若X与Y之间有路径，则称X，Y是连通的 连通图：任意两个顶点都连通的图称为连通图 没有孤立顶点 连通分量：指无向图中极大连通子图，即有多少个连通子图 图的存储 邻接矩阵 4.2 图的存储 4.2.1 邻接矩阵法 （1）给顶点编号 （2）建立邻接（关系）矩阵 图的存储 邻接矩阵 4.2.1 邻接矩阵法 若边 顶点2 则邻接矩阵为稀疏矩阵。 邻接矩阵的优点：增减边的操作简单 邻接矩阵的缺点： 增减顶点的操作需要搬移大量的元素， 浪费存储空间 图的存储 邻接矩阵的实现 图的邻接矩阵实现 图的存储 邻接表 4.2.2 邻接表法 一个邻接表由两种结构组成 存放各顶点元素的数组，头结点 各顶点各自的邻接链表，邻接结点 图的存储（课堂练习） 请写出下面这副图的邻接表 1、给顶点编号 2、建立顶点数组 3、建立各顶点的邻接链表 注意，此图为有向图 图的存储 邻接表的实现 邻接表的定义 头结点的定义 邻接结点的定义 图的存储 邻接表 图邻接表的定义 图的存储 邻接表 图的存储 图的邻接表存储法的特点 优点 节省存储空间 边的插入和删除操作比较简便 缺点 结构复杂 具有两种不同的基本组成单元 图的存储 4.2.3边带权值的图的存储 1）在邻接矩阵中的实现 图的存储 4.2.3边带权值的图的存储 2）在邻接表中的实现 在邻接结点结构中增加一个权值域 图的遍历 4.3图的遍历 问题： 1、对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。 2、图中有回路，遍历算法可能产生死循环。 图的遍历 深优 4.3.1 深度优先遍历 （1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。 （2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。 （3）对于前两个步骤是递归的 图的遍历 深优 4.3.1 深度优先遍历 （1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。 （2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。 （3）对于前两个步骤是递归的 图的遍历 深优 深度优先遍历的特点 “深度”：总是访问顶点的一个相邻顶点，好像是沿着图中的一条路径走到“底”，然后后退一点，再选一条路。如此“进进退退”，直到所有顶点都被访问 对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访问了。 即栈空时 图的遍历 深优 算法实现分析 （1）需要记录结点的访问状态。 int visited [ 顶点号 ]; （2）需要进行回溯。 lstack_type stack （3）图以邻接表的方式存储 graph_l graph ; （4）算法框架 （5）核心算法 图的遍历 深优 （4）算法框架 利用栈，不断将顶点的相邻顶点入栈、访问、出栈 算法以栈空结束 框架： 图的遍历 深优 （5）核心算法 图的遍历 深优 用递归调用实现深度优先遍历算法 图的遍历 广优 4.3.2、广度优先遍历 访问顶点v后，接着依次访问v的所有邻接顶点，再依次访问这些邻接顶点的邻接顶点。直到所有的顶点都被访问过。 图的遍历 广优 广度优先遍历的特点 “广度”：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，