可视化计算图论基础与应用ppt课件.pptx

《可视化计算图论基础与应用ppt课件.pptx》由会员分享，可在线阅读，更多相关《可视化计算图论基础与应用ppt课件.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能学习目标什么是图论?图论有哪些基本的概念?图论可以用来解决那些问题?如何在RAPTOR中保存图的数据结构？图算法有哪些重要应用?如何用RAPTOR体现图类算法的可视性？1第1页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图论基础图(Graph)，它有若干个不同的点v1，v2，vn，在其中一些点之间用直线或曲线连接2第2页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,

2、充分发挥中小学图书室育人功能图论基础（2）图中的这些点被称为顶点(vertex)或结点，连接顶点的曲线或直线称为边(edge)3第3页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图论基础（3）(a)图(无向图)的顶点集合为：V v1，v2，v3，v4边集合为：E（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）4第4页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图论基础（3）(b)图中（有向图）的顶点集合为：V v1

3、，v2，v3，v4边集合为：E ，5第5页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的常用术语（1）（c)图中的v1点本身也有边相连，这种边称为环有限图：顶点与边数均为有限的图，如上三个图均属于有限图6第6页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的常用术语（2）简单图：没有环且每两个顶点间最多只有一条边相连的图，如(a)图（无环无向）7第7页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,

4、充分发挥中小学图书室育人功能图的常用术语（4）邻接与关联：当（v1，v2）E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（adjacent），同时称（v1，v2）是与顶点v1、v2相关联的边8第8页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的常用术语（5）顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度9第9页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的常用术语（6）连通图：对

5、于图中任意两个顶点vi、vj V，vi、vj之间有道路相连，则称该图为连通图(connected graph)，如(a)图终端顶点：有向图中把出度为 0的顶点称为终端顶点，如(b)图的v310第10页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的常用术语（7）带权图：给各图的边上附加一个代表性数据(比如表示长度、流量或其他)，则称其为带权图网络/网图：带权的连通图11第11页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的主要应用图的历遍:走

6、遍所有节点，(BFS/DFS)生成树的概念最小生成树构建某些城市之间的最省的公路通道网络中的最短/最省的路径:Dijkstra算法地图着色:所谓的四色”定理”最小支配集问题:城镇商业网点的配置12第12页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能使用Raptor构建图算法的要点基本图形的资料库有向图；有向网；无向图；无向网数据的存储方式邻接矩阵邻接表主要难点：图类数据中边（edges）的输入为测试方便，建议使用文件保存“边”的数据13第13页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全

7、国教育大会精神,充分发挥中小学图书室育人功能图的数据储存图的数据储存有两种常用方式邻接表(+占用空间少，适合计算大型图应用)邻接矩阵(+直观；-占用空间大(n2)14第14页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能有向图与邻接矩阵15第15页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能无向图与邻接矩阵16第16页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能有向网与邻

8、接矩阵17第17页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Raptor中的图的创建主要步骤：输入顶点数（可以通过文件输入）输入边数（可以通过文件输入）顶点字符串初始化邻接矩阵/邻接表初始化输入边（两个顶点编号）可以通过文件输入18第18页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能用RAPTOR为无向图建邻接矩阵26个顶点，44条边19第19页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发

9、挥中小学图书室育人功能用RAPTOR为无向图建邻接矩阵为无向图建邻接矩阵为无向图建邻接矩阵20第20页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能用RAPTOR为无向网建邻接矩阵6个顶点10条边三个数据描述一条边21第21页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能用RAPTOR为有向图建邻接矩阵为无向网建邻接矩阵为无向网建邻接矩阵22第22页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥

10、中小学图书室育人功能用RAPTOR为无向图建邻接表26个顶点，44条边23第23页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能用RAPTOR为无向图建邻接表为无向图建邻接表为无向图建邻接表24第24页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次这一过程就叫做图的遍历(Traversing Graph)图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础通常有两条遍历图的

11、路径：深度优先搜索和广度优先搜索它们对无向图和有向图都适用图的遍历25第25页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的遍历：深度优先搜索例子26第26页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能RAPTOR实现DFSDFS子图27第27页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能RAPTOR实现DFSTraverse子程序子程序28第28页/共35页为深入学

12、习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图的遍历：广度优先搜索例子29第29页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能广度优先搜索的特点在广度优先搜索中，若顶点v在顶点u之前访问，则v的邻接点也将在u的邻接点之前访问由此，一般算法都采用队列来暂存那些刚访问过并且可能还有未访问的邻接点的顶点30第30页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能RAPTOR实现BFS-main子图

13、31第31页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能RAPTOR实现BFSBFS子图32第32页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能RAPTOR实现BFSTravers子图33第33页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能RAPTOR实现BFSRecursion子图34第34页/共35页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能End of ch7-135第35页/共35页