1可视化计算图论基础与应用图论基础图(Graph)，它有若干个不同的点v1，v2，…，vn，在其中一些点之间用直线或曲线连接2第2页/共35页第1页/共35页图论基础（2）图中的这些点被称为顶点(vertex)或结点，连接顶点的曲线或直线称为边(edge)3第3页/共35页第2页/共35页图论基础（3）(a)图(无向图)的顶点集合为：V＝｛v1，v2，v3，v4｝边集合为：E＝｛（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）｝4第4页/共35页第3页/共35页图论基础（3）(b)图中（有向图）的顶点集合为：V＝｛v1，v2，v3，v4｝边集合为：E＝｛<v1，v2>，<v1，v3>，<v1，v4>，<v2，v1>，<v4，v2>}5第5页/共35页第4页/共35页图的常用术语（1）（c)图中的v1点本身也有边相连，这种边称为环有限图：顶点与边数均为有限的图，如上三个图均属于有限图6第6页/共35页第5页/共35页图的常用术语（2）简单图：没有环且每两个顶点间最多只有一条边相连的图，如(a)图（无环无向）7第7页/共35页第6页/共35页图的常用术语（4）邻接与关联：当（v1，v2）∈E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（adjacent），同时称（v1，v2）是与顶点v1、v2相关联的边8第8页/共35页第7页/共35页图的常用术语（5）顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度9第9页/共35页第8页/共35页图的常用术语（6）连通图：对于图中任意两个顶点vi、vj∈V，vi、vj之间有道路相连，则称该图为连通图(connectedgraph)，如(a)图终端顶点：有向图中把出度为0的顶点称为终端顶点，如(b)图的v310第10页/共35页第9页/共35页图的常用术语（7）带权图：给各图的边上附加一个代表性数据(比如表示长度、流量或其他)，则称其为带权图网络/网图：带权的连通图11第11页/共35页第10页/共35页图的主要应用图的历遍:走遍所有节点，(BFS/DFS)生成树的概念最小生成树—构建某些城市之间的最省的公路通道网络中的最短/最省的路径:Dijkstra算法地图着色:所谓的四色”定理”最小支配集问题:城镇商业网点的配置12第12页/共35页第11页/共35页使用Raptor构建图算法的要点基本图形的资料库有向图；有向网；无向图；无向网数据的存储方式邻接矩阵邻接表主要难点：图类数据中边（edges）的输入为测试方便，建议使用文件保存“边”的数据13第13页/共35页第12页/共35页图的数据储存图的数据储存有两种常用方式邻接表(+占用空间少，适合计算大型图应用)邻接矩阵(+直观；-占用空间大(n2))14第14页/共35页第13页/共35页有向图与邻接矩阵15第15页/共35页第14页/共35页无向图与邻接矩阵16第16页/共35页第15页/共35页有向网与邻接矩阵17第17页/共35页第16页/共35页Raptor中的图的创建主要步骤：输入顶点数（可以通过文件输入）输入边数（可以通过文件输入）顶点字符串初始化邻接矩阵/邻接表初始化输入边（两个顶点编号）可以通过文件输入18第18页/共35页第17页/共35页用RAPTOR为无向图建邻接矩阵26个顶点，44条边19第19页/共35页第18页/共35页用RAPTOR为无向图建邻接矩阵为无向图建邻接矩阵20第20页/共35页第19页/共35页用RAPTOR为无向网建邻接矩阵6个顶点10条边三个数据描述一条边21第21页/共35页第20页/共35页用RAPTOR为有向图建邻接矩阵为无向网建邻接矩阵22第22页/共35页第21页/共35页用RAPTOR为无向图建邻接表26个顶点，44条边23第23页/共35页第22页/共35页用RAPTOR为无向图建邻接表为无向图建邻接表24第24页/共35页第23页/共35页从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次这一过程就叫做图的遍历(TraversingGraph)图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础通常有两条遍历图的路径：深度优先搜索和广度优先搜索它们对无向图和有向图都适用图的遍历25第25页/共35页第24页/共35页图的遍历：深度优先搜索例子26第26页/共35页第25页/共35页RAPTOR实现DFSDFS子图27第27页/共35页第26页/共35页RAPTOR实现DFSTraverse子程序28第28页/共35页第27页/共35页图的遍历：广度优先搜索例子29第29页/共35页第28页/共35页广度优先搜索的特点在广度优先搜索中，若顶点v在顶点u之前访问，则v的邻接点也将在u的邻接点之前访问由此，一般算法都采用队列来暂存那些刚访问过并且可能还有未访问的邻接点的顶点30第30页/共35页第29页/共35页RAPTOR实现BFS-main子图31第31页/共35页第30页/共35页RAPTOR实现BFSBFS子图32第32页/共35页第31页/共35页RAPTOR实现BFSTravers子图33第33页/共35页第32页/共35页RAPTOR实现BFSRecursion子图34第34页/共35页第33页/共35页Endofch7-135第35页/共35页第34页/共35页
本文档为【可视化计算图论基础与应用】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483