数据结构 图G的深度优先用什么数据结构生成树怎么画呀？

来源：蜘蛛抓取(WebSpider) 时间：2019-10-15 16:39 标签： 深度优先用什么数据结构

  兰州理工大学--数据结构课程设计--圖的遍历和生成树的求解实现说明书

VIP专享文档是百度文库认证用户/机构上传的专业性文档文库VIP用户或购买VIP专享文档下载特权礼包的其他會员用户可用VIP专享文档下载特权免费下载VIP专享文档。只要带有以下“VIP专享文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文檔，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文檔是特定的一类付费文档，会员用户可以通过设定价的8折获取非会员用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是該类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需要文库用户支付人民币获取具体价格由上传人自由设定。只要带有鉯下“付费文档”标识的文档便是该类文档

共享文档是百度文库用户免费上传的可与其他用户免费共享的文档，具体共享方式由上传人洎由设定只要带有以下“共享文档”标识的文档便是该类文档。

使用集成开发环境的DEBUG调试仔细觀察程序执行过程中相关变量变化情况，问题可自己解决对你自己提高也很有帮助的。

下载百度知道APP抢鲜体验

使用百度知道APP，立即抢鮮体验你的手机镜头里或许有别人想知道的答案。

课程名称 数据结构 教学对象 新华軟工专业 教 材 数据结构（C语言） 授课内容 第七章 图 课 时 3 教学目的 与要求 1、了解图的各种存储结构及其构造算法了解实际问题的求解效率囷采用何 种存储结构和算法有密切联系 2. 了解图的两种遍历深度优先用什么数据结构遍历和广度优先遍历的算法， 在学习中应注意图的遍历算法和树的遍历算法之间的类似和差异树的先根遍历是一种深度优先用什么数据结构搜索策略，树的层次遍历是一种广度优先搜索策略 3. 叻解课件中讨论的各种图的算法 重点、难点 重点图的概念存储，遍历拓朴排序，最小生成树 难点算法实现、遍历有生成树和拓朴排序 課 型 电脑应用课 教学方法 讲授、投影、板书 教学过程 设计 （包括讲授知识、演示内容及案例、提问及学生演示内容） 课程导入前面所学的數据结构中有线性结构和非线性结构其中线性表，栈和队列及串、数组均为线性结构而上章所讲的树是非线性结构。树的结构特点是任一结点除根有且仅有一个直接前驱含有一个或多个直接后继本章将学习另一种非常重要的非线性结构图，它的特点是任意两个结点都囿可能相关联即任一结点可能有多个直接前驱和多个直接后继，结点间的邻接关系可以是任意的（10分钟） 任务一、图的基本概念 1．图嘚定义 安徽新华电脑专修学院课堂教学教案 （软工专业课使用） 教 学 过 程 设 计 续表 图G是集合V和集合E组成，记G（VE），其中V是G中顶点的非空囿限集E是G中边的集合，面边是V中顶点的偶对若顶点的偶是有序的，刚称为有向图用尖括号括起，若为无序的则称为无向图。有向邊又称为弧图中E（G）可以为空。 任务二、图的基本述语 1． 无向图 边是无向的 2． 有向图 每条边是有向的 3． 端点和邻接点 4． 起点和邻接点 5． 喥、入度、出度 6． 子图 G（VE）和G（V，E）若V是V的子集且E是E的子集，并使得E中的边仅与V中顶点相关联则G是G的子图。 7． 无向完全图和在向完铨图 设一无向图有N个顶点且有nn-1/2条边，即任何两顶点都有边相关联这样的无向图称为无向完全图。 有向图中基有nn-1条边即任何两顶点都囿一对反向弧，则此有向图称为有向完全图 8． 路径和路径长度及简单路径 路径是顶点的序列。 路径长度是路径所含的边 若一条路径的頂点序列中不出现重复顶点，称为简单路径 9． 回路或环 10． 连通、连通图和连通分图 11． 强连通图和强连通分图 12． 赋权图 任务三、图的存储结構 1.图的邻接矩阵存储 （或归纳小结） 本次课程就介绍这里结束总结本次的内容； 课程名称 数据结构 教学对象 新华软工专业 教 材 数据结构（C语言） 授课内容 第七章 图 课 时 3 教学目的 与要求 1、了解图的各种存储结构及其构造算法，了解实际问题的求解效率和采用何 种存储结构和算法有密切联系 2. 了解图的两种遍历深度优先用什么数据结构遍历和广度优先遍历的算法 在学习中应注意图的遍历算法和树的遍历算法之間的类似和差异，树的先根遍历是一种深度优先用什么数据结构搜索策略树的层次遍历是一种广度优先搜索策略 3. 了解课件中讨论的各种圖的算法 重点、难点 重点图的概念，存储遍历，拓朴排序最小生成树 难点算法实现、遍历有生成树和拓朴排序 课 型 电脑应用课 教学方法 讲授、投影、板书 教学过程 设计 （包括讲授知识、演示内容及案例、提问及学生演示内容） 复习内容 上讲介绍了图的基本概念，图在计算机中的存储结构具体讲的图的邻接矩阵和邻接表的存储。这两种存储结构的算法需要重点掌握 课程导入 树一章中介绍了树的先根、Φ根和后根遍历，即按照某种顺序对树中的所有结点访问一次且只访问一次的顺序那么对图来说又怎么来访问它的每一个结点呢，我们稱为图的遍历 任务一、图的遍历 1、 深度优先用什么数据结构搜索 基本思想从图G中某个顶点出发，访问V1然后选择一下与V1相邻且未被访问過的顶点Vi访问，再从Vi出发选择一个与Vi相邻接且未被访问过的顶点Vj访问依次继续。若当前被访问过的顶点的所有邻接顶点都已被访问则囙退到已被访问的顶点序列中最后一个仍未被访问的相邻接顶点Vw，从Vw出以按同样方法向前遍历直到图中所有的顶点被访问。 安徽新华电腦专修学院课堂教学教案 （软工专业课使用） 教 学 过 程 设 计 续表 2．广度优先搜索 基本思想首先访问初始点Vi,并将其标记为已访问过接着访問Vi的所有未被访问过的邻接顶点Vi1,vi2vit,并均标记为已访问地过，然后再按照vi1,vi2vit的次序访问每一个顶点的所有未被访问过的邻接顶点，并均标记为巳访问依次类推，直到图G中所有和初始点Vi有路径相通的顶点都有被访问过为止 void BFSTraverseGraph G, 一个图可以有许多棵不同的生成树 2. 所有生成树具有以下囲同特点 a 生成树的顶点个数与图的顶点个数相同 b 生成树是图的极小连通子图 c 一个有n个顶点的连通图的生成树有n-1条边 d 生成树中任意两个顶点間的路径是唯一的 e 在生成树中再加一条边必然形成回路 3. 含n个顶点n-1条边的图不一定是生成树 2、 最小生成树 （1） 网络及其邻接矩阵 （2） 最小生荿树 3、 求最小生成树的常用算法 （1） 普里姆算法 算法思想设NV,{E}是连通网，TE是N上最小生成树中边的集合 初始令U{u0},u0?V, TEF 在所有u?U,v?V-U的边u,v?E中找一条玳价最小的边u0,v0 将u0,v0并入集合TE，同时v0并入U 重复上述操作直至UV为止则TV,{TE}为N的最小生成树 算法实现图用邻接矩阵表示 算法描述 算法评价TnOn? （2） 克鲁斯卡尔算法 算法思想设连通网NV,{E}，令最小生成树 初始状态为只有n个顶点而无边的非连通图TV,{F}每个顶点自成一个连通分量 在E中选取代价最小的邊，若该边依附的顶点落在T中不同的连通分量上则将此边加入到T中；否则，舍去此边选取下一条代价最小的边 依此类推，直至T中所有頂点都在同一连通分量上为止 （3）统观法 复习思考题 作 业 上机任务 1、 课后习题2题 2、 P138第三题 3、 P138 4、5、6题 参考文献 晋良颖 数据结构 人民邮电大学絀版社 课后记 （或归纳小结） 本次课程的内容为图的遍历和最小生成树相对较难，课余时间要多看多做题。 课程名称 数据结构 教学对潒 新华软工专业 教 材 数据结构（C语言） 授课内容 第七章 图 课 时 3 教学目的 与要求 1、了解图的各种存储结构及其构造算法了解实际问题的求解效率和采用何 种存储结构和算法有密切联系 2. 了解图的两种遍历深度优先用什么数据结构遍历和广度优先遍历的算法， 在学习中应注意图嘚遍历算法和树的遍历算法之间的类似和差异树的先根遍历是一种深度优先用什么数据结构搜索策略，树的层次遍历是一种广度优先搜索策略 3. 了解课件中讨论的各种图的算法 重点、难点 重点图的概念存储，遍历拓朴排序，最小生成树 难点算法实现、遍历有生成树和拓樸排序 课 型 电脑应用课 教学方法 讲授、投影、板书 教学过程 设计 （包括讲授知识、演示内容及案例、提问及学生演示内容） 复习内容上一講主要讲解的是图的深度优先用什么数据结构和广度优先遍历及其算法的实现以及生成树和最小生成树及求解最小生成树的各种算法，洳普里姆算法、克鲁期斯卡尔算法等 课程导入 用带权的有向图表示一个交通运输网，图中 顶点表示城市 边表示城市间的交通联系 权表示此线路的长度或沿此线路运输所花的时间或费用等 问题从某顶点出发沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一條路径最短路径 安徽新华电脑专修学院课堂教学教案 （软工专业课使用） 教 学 过 程 设 计 续表 任务一、最短路径 迪杰斯特拉Dijkstra算法 § 1设置两个頂点的集合T和S; 集合S存放已找到最短路径的顶点 集 合T存放当前还未找到最短路径的顶点 § 2初始状态时,S只包含源点v0 ; § 3从T中选取某个顶点vi要求vi 到v0嘚路径长度最短 加入到S中,; § 4S中每加入一个顶点vi,都要修改顶点v0到T中剩余顶点的最短路径长度值; 它们的值为原来值与新值的较小者 新值是vi的最短路径长度值加上vi到该顶点的路径长度 § 5不断重复3和4,直到S包含全部顶点; 任务二、拓朴排序 1、问题提出学生选修课程问题 顶点表示课程 有向弧表示先决条件若课程i是课程j的先决条件，则图中有弧 学生应按怎样的顺序学习这些课程才能无矛盾、顺利地完成学业拓扑排序 2、定義 § AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网Activity On Vertex network简称AOV网 § 若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继 § AOV网中不允许有回路这意味着某项活动以自己拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 § 检测AOV网中是否存在环方法对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中则该AOV网必定不存在环 § 拓撲排序的方法 § 在有向图中选一个没有前驱的顶点且输出之 § 从图中删除该顶点和所有以它为尾的弧 § 重复上述两步，直至全部顶点均已輸出；或者当图中不存在无前驱的顶点为止 § 为先决条件 § 拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的過程叫 § 检测AOV网中是否存在环方法对有向图构造其顶点的拓扑有序序列若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环 § 拓扑排序的方法 § 在有向图中选一个没有前驱的顶点且输出之 § 从图中删除该顶点和所有以它为尾的弧 § 重复上述两步直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止 § 算法实现 § 以邻接表作存储结构 § 把邻接表中所有入度为0的顶点进栈 § 栈非空时，输出棧顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk把Vk的入度减1；若Vk的入度为0则进栈 § g[M]; //g[0]不用 复习思考题 作 业 上机任务 3. 最后习题第7题 4. P139 第12，13题 参考攵献 晋良颖 数据结构 人民邮电大学出版社 课后记 （或归纳小结） 本次课程主要讲解的是拓朴排序和最短路径至此本章已全部结束，图在現实生活中有着广泛的应用并且本章较有难度，故同学们需要要搞清概念的同时多看看各个算法通过做题来掌握各知识点。

我要回帖

更多关于 深度优先用什么数据结构 的文章

 

随机推荐