北京理工大学数据结构.ppt

第7章图 第7章图 7 1图的定义和术语7 2图的存储结构7 3图的遍历7 4图的最小生成树 第3页 7 1图的定义与术语 一 图的定义1 图 Graph 图G是由两个集合V G 和E G 组成的 记为G V E 其中 V G 是顶点的非空有限集E G 是边的有限集合 边是顶点的无序对或有序对 图的分类有向图无向图 第4页 7 1图的定义与术语 2 有向图 有向图G是由两个集合V G 和E G 组成的 其中 V G 是顶点的非空有限集 E G 是有向边 也称弧 的有限集合 弧是顶点的有序对 记为 v w是顶点 v为弧尾 w为弧头 第5页 7 1图的定义与术语 例如 G1 V1 A B C D E E1 E A C B D 第6页 7 1图的定义与术语 3 无向图 无向图G是由两个集合V G 和E G 组成的 其中 V G 是顶点的非空有限集 E G 是边的有限集合 边是顶点的无序对 记为 v w 或 w v 并且 v w w v 第7页 7 1图的定义与术语 例如 G2 V2 v0 v1 v2 v3 v4 E2 v0 v1 v0 v3 v1 v2 v1 v4 v2 v3 v2 v4 V0 V4 V3 V1 V2 第8页 7 1图的定义与术语 例如 G2 V2 v0 v1 v2 v3 E2 V G1 1 2 3 4 5 6 E G1 第9页 7 1图的定义与术语 图的应用举例例1 交通图 公路 铁路 顶点 地点边 连接地点的路例2 电路图顶点 元件边 连接元件之间的线路例3 通讯线路图顶点 地点边 地点间的连线例4 各种流程图如产品的生产流程图 顶点 工序边 各道工序之间的顺序关系 第10页 7 1图的定义与术语 二 图的基本术语1 邻接点及关联边邻接点 边的两个顶点关联边 若边e v u 则称顶点v u关联边e2 顶点的度 入度 出度顶点V的度 与V相关联的边的数目在有向图中 顶点V的出度 以V为起点有向边数顶点V的入度 以V为终点有向边数顶点V的度 V的出度 V的入度设图G的顶点数为n 边数为e图的所有顶点的度数和 2 e 每条边对图的所有顶点的度数和 贡献 2度 e 第11页 7 1图的定义与术语 3 路径 回路无向图G V E 中的顶点序列v1 v2 vk 若 vi vi 1 E i 1 2 k 1 v v1 u vk 则称该序列是从顶点v到顶点u的路径 若v u 则称该序列为回路 路径 V0 V1 V2 V3回路 V0 V1 V2 V3 V0 第12页 7 1图的定义与术语 3 路径 回路有向图D V E 中的顶点序列v1 v2 vk 若 E i 1 2 k 1 v v1 u vk 则称该序列是从顶点v到顶点u的路径 若v u 则称该序列为回路 路径 V0 V2 V3回路 V0 V2 V3 V0 第13页 7 1图的定义与术语 4 连通图 强连通图 在无 有 向图G 中 若对任何两个顶点v u都存在从v到u的路径 则称G是连通图 强连通图 非连通图 连通图 强连通图 非强连通图 第14页 7 1图的定义与术语 5 子图设有两个图G V E G1 V1 E1 若V1 V E1 E 而且E1关联的顶点都在V1中 则称G1是G的子图 b c 都是 a 的子图 第15页 7 1图的定义与术语 6 连通分量 强连通分量 无 有 向图的极大 强 连通子图 极大 强 连通子图 该子图是 强 连通子图 若再将G的任何不在该子图中的顶点加入 子图就不再 强 连通 第16页 7 1图的定义与术语 强连通分量 非连通图 第17页 7 1图的定义与术语 7 生成树包含无向图G所有顶点的极小连通子图称为G生成树 极小连通子图意思是 该子图是G的连通子图 在该子图中删除任何一条边 子图不再连通 G1的生成树 章 连通所有顶点无回路 第18页 7 2图的存储结构 一 数组表示法 邻接矩阵表示 邻接矩阵 G的邻接矩阵是满足如下条件的n阶矩阵 在数组表示法中 用邻接矩阵表示顶点间的关系 第19页 7 2图的存储结构 二 邻接表 图的链式存储结构1 无向图的邻接表顶点 通常按编号顺序将顶点数据存储在一维数组中 关联同一顶点的边 用线性链表存储 第20页 typedefstructtnode 表头结点 intvexdata ArcNode firstarc VNode AdjList MAX VERTEX NUM 7 2图的存储结构 typedefstructArcNode 链表结点 intadjvex structArcNode next ArcNode typedefstruct 图 AdjListvertices intvexnum arcnum 顶点数和弧数intkind 图的种类 ALGraph 第21页 7 2图的存储结构 无向图的邻接表的特点1 在G邻接表中 同一条边对应两个结点 2 顶点v的度 等于v对应线性链表的长度 3 判定两顶点v u是否邻接 要看v对应线性链表中有无对应的结点 4 在G中增减边 要在两个单链表插入 删除结点 5 设存储顶点的一维数组大小为m m 图的顶点数n 图的边数为e G占用存储空间为 m 2 e G占用存储空间与G的顶点数 边数均有关 适用于边稀疏的图 第22页 7 2图的存储结构 2 有向图的邻接表顶点 用一维数组存储 按编号顺序 以同一顶点为起点的弧 用线性链表存储 adjvex next 类似于无向图的邻接表 所不同的是 以同一顶点为起点的弧 用线性链表存储 第23页 7 2图的存储结构 3 有向图的逆邻接表顶点 用一维数组存储 按编号顺序 以同一顶点为终点的弧 用线性链表存储 类似于有向图的邻接表 所不同的是 以同一顶点为终点弧 用线性链表存储 章 第24页 7 3图的遍历 连通图的深度遍历 DFS 从图中某顶点v出发 1 访问顶点v 2 对v的每个未被访问的邻接点wj 从wj出发 继续对图进行深度优先遍历 深度遍历 V1 V2 V4 V5 V8 V3 V6 V7 例 深度遍历 V1 V3 V6 V7 V2 V5 V8 V4 第25页 7 3图的遍历 图的深度遍历 DFS V w1 SG1 SG2 SG3 w2 w3 w2 W1 W2和W3均为V的邻接点 SG1 SG2和SG3分别为含顶点W1 W2和W3的子图 访问顶点V for W1 W2 W3 若该邻接点W未被访问 则从它出发进行深度优先搜索遍历 第26页 7 3图的遍历 图的深度遍历 DFS V w1 SG1 SG2 SG3 w2 w3 w2 从图解可见 1 从深度优先搜索遍历连通图的过程类似于树的先根遍历 解决的办法是 为每个顶点设立一个 访问标志visited w 2 如何判别V的邻接点是否被访问 第27页 7 3图的遍历 Booleanvisited MAX 访问标志数组Status VisitFunc intv 访问函数voidDFS GraphG intv 从顶点v出发 深度优先搜索遍历连通图Gvisited v TRUE VisitFunc v for w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS G w 对v的尚未访问的邻接顶点w 递归调用DFS DFS 第28页 7 3图的遍历 非连通图的深度优先搜索遍历首先将图中每个顶点的访问标志设为FALSE 之后搜索图中每个顶点 如果未被访问 则以该顶点为起始点 进行深度优先搜索遍历 否则继续检查下一顶点 第29页 7 3图的遍历 voidDFSTraverse GraphG Status Visit intv 对图G作深度优先遍历 VisitFunc Visit for v 0 v G vexnum v visited v FALSE 访问标志数组初始化for v 0 v G vexnum v if visited v DFS G v 对尚未访问的顶点调用DFS 第30页 7 3图的遍历 例如 a b c h d e k f g FFFFFFFFF T T T T T T T T T a c h d k f e b g a c h k f e d b g 访问标志 访问次序 abcdefghk 012345678 第31页 7 3图的遍历 图的深度遍历 DFS 深度遍历 V1 V3 V7 V6 V2 V4 V8 V5 第32页 7 3图的遍历 图的广度遍历 BFS 从图中的某个顶点V0出发 并在访问此顶点之后依次访问V0的所有未被访问过的邻接点 之后按这些顶点被访问的先后次序依次访问它们的邻接点 直至图中所有和V0有路径相通的顶点都被访问到 若此时图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 重复上述过程 直至图中所有顶点都被访问到为止 第33页 7 3图的遍历 图的广度遍历 BFS 从图中某顶点v出发 1 访问顶点v2 访问v的所有未被访问的邻接点w1 w2 wk3 依次从这些邻接点出发 访问它们的所有未被访问的邻接点 直到图中所有访问过的顶点的邻接点都被访问到 V1 V2 V3 V4 V8 V5 V6 V7 V1 V3 V2 V6 V7 V4 V5 V8 第34页 7 3图的遍历 voidBFSTraverse GraphG Status Visit intv for v 0 v G vexnum v visited v FALSE 初始化访问标志InitQueue Q 置空的辅助队列Qfor v 0 v G vexnum v if visited v v尚未访问 见下页 if BFSTraverse 第35页 7 3图的遍历 上页中的if 部分visited v TRUE Visit v 访问vEnQueue Q v v入队列while QueueEmpty Q DeQueue Q u 队头元素出队并置为ufor w FirstAdjVex G u w 0 w NextAdjVex G u w if visited w visited w TRUE Visit w EnQueue Q w 访问的顶点w入队列 if while 第36页 7 3图的遍历 图的广度遍历 BFS 请对照教材第170页 第37页 7 3图的遍历 图的广度遍历 BFS 第38页 7 3图的遍历 图的广度遍历 BFS 遍历序列 14325 章