数据结构域算法设计-第7章数据结构中的图 课件

《数据结构域算法设计-第7章数据结构中的图 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第7章数据结构中的图 课件（75页珍藏版）》请在金锄头文库上搜索。

1、数据结构与应用马石安马石安 魏文平魏文平 编著编著1内容简介 本教材采用本教材采用面向对象面向对象的观点讨论数据结构技术，并以的观点讨论数据结构技术，并以 C+C+类模板类模板作为算法描述工具。作为算法描述工具。教材在简要回顾教材在简要回顾C+C+程序设计概念的基础上，全面系统程序设计概念的基础上，全面系统 地介绍了地介绍了线性表、栈和队列、串、数组和广义表、树线性表、栈和队列、串、数组和广义表、树 和二叉树及图和二叉树及图等数据结构，讨论了常用的等数据结构，讨论了常用的查找和排序查找和排序 技术，对每一种数据结构，除了详细阐述其逻辑结构技术，对每一种数据结构，除了详细阐述其逻辑结构 、存储结

2、构和相关算法外，还对所有算法进行了、存储结构和相关算法外，还对所有算法进行了C+C+语语 言实现和评价，并给出了应用实例。言实现和评价，并给出了应用实例。教材附录给出了上机实验内容。教材附录给出了上机实验内容。2教材目录第第0 0章章 C+C+程序设计语言预备知识程序设计语言预备知识0.1 0.1 一个简单一个简单C+C+语言程序语言程序 0.2 0.2 指针与引用指针与引用 0.3 0.3 动态存贮分配动态存贮分配 0.4 0.4 函数函数 0.5 0.5 类与对象类与对象 0.6 0.6 运算符重载运算符重载 0.7 0.7 模板模板3第第1 1章章 绪论绪论 1.1 1.1 数据结构的产

3、生和发展数据结构的产生和发展 1.2 1.2 数据结构研究的内容数据结构研究的内容 1.3 1.3 基本概念和术语基本概念和术语 1.4 1.4 算法算法 第第2 2章 线性表章 线性表 2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构 2.3 2.3 线性表的链式存储结构线性表的链式存储结构 2.4 2.4 顺序表和链表的比较顺序表和链表的比较 2.5 2.5 线性表的应用线性表的应用4第章 栈和队列第章 栈和队列 3.1 3.1 栈栈 3.2 3.2 队列队列 3.3 3.3 栈的应用栈的应用第第4 4章章 串串 4.1 4.1 串

4、的逻辑结构串的逻辑结构 4.2 4.2 串的顺序存储结构串的顺序存储结构 4.3 4.3 串的链式存储结构串的链式存储结构 4.4 4.4 串的应用串的应用 5第第5 5章章 数组和广义表数组和广义表5.1 5.1 数组数组 5.2 5.2 矩阵的压缩存储矩阵的压缩存储 5.3 5.3 广义表广义表 5.4 5.4 多维数组的应用多维数组的应用6第第6 6章章 树和二叉树树和二叉树6.1 6.1 树的逻辑结构树的逻辑结构 6.2 6.2 树的顺序存储结构树的顺序存储结构 6.3 6.3 二叉树的逻辑结构二叉树的逻辑结构 6.4 6.4 二叉树的存储结构二叉树的存储结构 6.5 6.5 线索二叉

5、树线索二叉树 6.6 6.6 树、森林与二叉树的转换树、森林与二叉树的转换 6.7 6.7 树的应用树的应用7第第7 7章章 图图7.1 7.1 图的逻辑结构图的逻辑结构 7.2 7.2 图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历 7.4 7.4 生成树和最小生成树生成树和最小生成树 7.5 7.5 最短路径最短路径 7.6 DAG7.6 DAG图及其应用图及其应用8第第8 8章章 排序排序8.1 8.1 概述概述 8.2 8.2 插入排序插入排序 8.3 8.3 交换排序交换排序 8.4 8.4 选择排序选择排序 8.5 8.5 归并排序归并排序 8.6 8.6 基数排序基数

6、排序 8.7 8.7 各种内排序方法的比较和选择各种内排序方法的比较和选择9第第9 9章章 查找查找9.1 9.1 概述概述 9.2 9.2 线性表的查找线性表的查找 9.3 9.3 树表的查找树表的查找 9.4 9.4 散列表的查找散列表的查找附录附录 实验内容实验内容10第7章 图117.1 图的逻辑结构7.2 图的存储结构图的存储结构7.3 图的遍历图的遍历本章主要内容本章主要内容7.4 生成树和最小生成树生成树和最小生成树7.5 最短路径最短路径7.6 DAGDAG图及其应用图及其应用127.1.1图的定义7.1 7.1 图的逻辑结构图的逻辑结构图G由结点的有穷非空集合V和边的有穷集合

7、 E组成，记为G=(V，E)。在图结构中，将结 点称为顶点，以便与树形结构加以区别，边 则是顶点的偶对，若两个顶点之间存在一条 边，就表示这两个顶点具有相邻关系。通常 ，也将图G的顶点集和边集分别记为V(G)和 E(G)。E(G)可以是空集，若E(G)为空，则图 G只有顶点而没有边。 137.1.2 图的基本术语 1. 有向图和无向图 如果G中的每条边都是有方向的，则称G为 有向图。在有向图中，一条有向边是由两个顶点组 成的有序对，通常用尖括号表示。例如，表示一条有向边，vi是边的 始点，vj是边的终点。14若图G中的每条边都是没有方向的，则称G为 无向图。无向图中的边均是顶点的无序对，通常用

8、圆 括号表示。无序对(vi,vj)和(vj,vi)表示同 一条边。 15无向图G1，在该图中：V(G1)=v1，v2，v3，v4，v5E(G1)=(v1,v2)，(v1,v4)，(v2,v3)， (v2,v5) ，(v3,v4)，(v3,v5) 16有向图G2，该图的顶点集和边集分别为：V(G2)=v1，v2，v3，v4，v5E(G2)， 172. 稠密图和稀疏图 3. 边和顶点的关系 若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接 点(adjacent)，或称vi和vj相邻接，并称(vi,vj)依 附或关联(incident)于顶点vi和vj或称(vi,vj)与顶 点vi和vj相关

9、联。若是一条有向边，则称此边是顶点vi的一 条出边，同时也是顶点vj的一条入边；称顶点vi 邻接到(或邻接于)顶点vj，并称边关联于 vi和vj，或称与顶点vi和vj相关联。 184. 顶点的度 无向图中顶点v的度是关联于该顶点的边的数 目，记为D(v)。在有向图中，以顶点v为终点的边的数目称为 v的入度，记为ID(v)；以顶点v为始点的边的 数目称为v的出度，记为OD(v)。顶点v的度定 义为该顶点的入度和出度之和，即 D(v)=ID(v)+OD(v)。 195. 子图 设G=(V，E)是一个图，若V是V的子集， E是E的子集，且E的边所关联的顶点均 在V中，则G=(V，E)也是一个图，并

10、称其为G的子图。 206. 路径 设G是图，若存在一个顶点序列vp，v1， v2，vq-1，vq使得 (vp,v1)，(v1,v2)， ，(vq-1,vq)属于E，则称vp到vq存在一条路 径(path)，其中vp为起点，vq为终点。路径的长度是该路径上边的数目。 217. 有根图和图的根 8. 无向图的连通图和连通分量 9. 有向图的强连通图和强连通分量 10. 网络 227.1.3 图的基本操作 图的基本操作: 图的初始化：Create() 销毁图：Destory()删除图中所有元素，回收图所占空间。 取顶点：GetVex(i)取图中的第i 个顶点的数据信息。23 插入顶点：InsertV

11、ex(v)在图中插入顶点v。 删除顶点：DeleteVex(v)删除图中顶点v。 插入边或弧：Insert(v,w)在图中插入一条边(v,w)或弧，如是无 向图，还应增加对称边(w, v)。 删除边或弧：Delete(v,w)247.2 7.2 图的存储结构图的存储结构 图的存储表示方法很多，邻接矩阵表示法和邻 接表表示法是两种最常用的方法。 7.2.1邻接矩阵 邻接矩阵是一种表示顶点之间相邻关系的矩 阵。设G=(V，E)是具有n个顶点的图，则G的 邻接矩阵A是具有如下性质的n阶方阵： 25对于无向图，若从顶点vi到vj有一条无向边 (vi,vj)，则aij=1，aji=1;否则 aij=0，

12、aji=0，故无向图的邻接矩阵 是一个对称矩阵。对于有向图，若从顶点vi到 vj有一条有向边，则aij=1；否则 aij=0。 262728基于邻接矩阵存储结构的图的类模板定义cx7_1.h 29邻接矩阵的基本操作及其实现:1求顶点在图中的位置 2创建图 3顶点的增删 4弧的增删 5输出邻接矩阵 6销毁有向图 307.2.2 邻接表 邻接表表示法是图的一种链接存储结构，类似于树的 孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的 顶点链成一个单链表，这个单链表就称为顶点vi的邻 接表，邻接表中每个结点有两个域：其一是邻接点域 (adjvex)，用以存放与vi相邻接的顶点vj的

13、序号j； 其二是链域(next)，用来指示与vi相邻接的下一顶点 ，从而将邻接表的所有表结点链在一起。31为每个顶点vi的邻接表设置一个头结点，头结 点中包含两个域，其中一个是顶点域vertex， 用来存放顶点vi的数据信息；另一个是指针域 firstedge，它指向vi的邻接表的开始结点，相 当于vi的邻接表的头指针。为了便于随机访问 任一顶点的邻接表，将所有头结点顺序存储在 一个一维数组中，称为顶点表，将其中的头结 点称为顶点表结点。这样就构成了图的邻接表 表示。 323334邻接表的基本操作及其实现: 求顶点在图中的位置 创建有向图 顶点的增删 弧的增删 输出邻接表 销毁有向图 357.

14、2.3 邻接矩阵和邻接表的比较 367.3 7.3 图的遍历图的遍历 图的遍历是指从图中某一顶点出发，对图中所 有顶点访问一次且仅访问一次的操作。 377.3.1 深度优先搜索遍历 深度优先搜索(DFS) 遍历类似于树的先序遍历 。假定给定图G的初态是所有顶点均未曾访问 过。则从图中某顶点v出发进行深度优先搜索 遍历的基本思想是：(1) 访问顶点v；(2) 从v的未被访问的邻接点中选取一个顶 点w，从w出发进行深度优先搜索遍历；(3) 重复上述两步，直至图中所有和v有路 径相通的顶点都被访问到。38从图中某顶点v出发，基于邻接矩阵表示的深度 优先搜索的递归过程如程序sf7_13.cpp所示。从

15、图中某顶点v出发，基于邻接表表示的深度优 先搜索的递归过程如程序sf7_15.cpp所示。 39无向图G12和它的深度优先搜索遍历:得到的顶点访问序列为：v0 v1 v2 v5 v4 v6 v3 v7 407.3.2 广度优先搜索遍历 广度优先搜索 (breadth first serch，BFS) 遍历类 似于树的层序遍历。 从图中某顶点v出发进行广度优先遍历的基本思想是 ： (1) 访问顶点v； (2) 依次访问v的各个未被访问的邻接点v1，v2， ，vk； (3) 分别从v1，v2，vk出发依次访问它们未被访 问的邻接点，并使“先被访问顶点的邻接点”先于“ 后被访问顶点的邻接点”被访问，

16、直至图中所有与顶 点v有路径相通的顶点都被访问到。41无向图G12的广度优先搜索遍历:v0 v1 v3 v4 v2 v6 v5 v7427.4 7.4 生成树和最小生成树生成树和最小生成树 在图论中，常常将一个无回路的连通图定义为 树。没有确定谁是根的图称为自由树。 7.4.1 生成树与生成森林 如果连通图G的一个子图是一棵包含G中所有顶 点的树，则该子图称为G的生成树。 43由深度优先搜索得到的生成树称为深度优先生 成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生 成树，简称为BFS生成树。 4445图的生成树不唯一。从不同的顶点出发进行遍 历，可以得到不同的生成树。 467.4.2 最小生成树 带权的连通图也称连通网，其生成树也是带 权的，我们把生成树各边的权值总和称为该 生成树的权。图的生成树不唯一，从不同的