可视化计算图论基础与应用

学习目标什么是图论?图论有哪些基本的概念?图论可以用来解决那些问题?如何在RAPTOR中保存图的数据结构？图算法有哪些重要应用?如何用RAPTOR体现图类算法的可视性？1第1页/共35页图论基础图(Graph)，它有若干个不同的点v1，v2，…，vn，在其中一些点之间用直线或曲线连接2第2页/共35页图论基础（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，v2，v3，v4｝边集合为：E＝｛v1，v2，v1，v3，v1，v4，v2，v1，v4，v2}5第5页/共35页图的常用术语（1）（c)图中的v1点本身也有边相连，这种边称为环有限图：顶点与边数均为有限的图，如上三个图均属于有限图6第6页/共35页图的常用术语（2）简单图：没有环且每两个顶点间最多只有一条边相连的图，如(a)图（无环无向）7第7页/共35页图的常用术语（4）邻接与关联：当（v1，v2）∈E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（adjacent），同时称（v1，v2）是与顶点v1、v2相关联的边8第8页/共35页图的常用术语（5）顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度9第9页/共35页图的常用术语（6）连通图：对于图中任意两个顶点vi、vj∈V，vi、vj之间有道路相连，则称该图为连通图(connectedgraph)，如(a)图终端顶点：有向图中把出度为0的顶点称为终端顶点，如(b)图的v310第10页/共35页图的常用术语（7）带权图：给各图的边上附加一个代表性数据(比如表示长度、流量或其他)，则称其为带权图网络/网图：带权的连通图11第11页/共35页图的主要应用图的历遍:走遍所有节点，(BFS/DFS)生成树的概念最小生成树—构建某些城市之间的最省的公路通道网络中的最短/最省的路径:Dijkstra算法地图着色:所谓的四色”定理”最小支配集问题:城镇商业网点的配置12第12页/共35页使用Raptor构建图算法的要点基本图形的资料库有向图；有向网；无向图；无向网数据的存储方式邻接矩阵邻接表主要难点：图类数据中边（edges）的输入为测试方便，建议使用文件保存“边”的数据13第13页/共35页图的数据储存图的数据储存有两种常用方式邻接表(+占用空间少，适合计算大型图应用)邻接矩阵(+直观；-占用空间大(n2))14第14页/共35页有向图与邻接矩阵15第15页/共35页无向图与邻接矩阵16第16页/共35页有向网与邻接矩阵17第17页/共35页Raptor中的图的创建主要步骤：输入顶点数（可以通过文件输入）输入边数（可以通过文件输入）顶点字符串初始化邻接矩阵/邻接表初始化输入边（两个顶点编号）可以通过文件输入18第18页/共35页用RAPTOR为无向图建邻接矩阵26个顶点，44条边19第19页/共35页用RAPTOR为无向图建邻接矩阵为无向图建邻接矩阵20第20页/共35页用RAPTOR为无向网建邻接矩阵6个顶点10条边三个数据描述一条边21第21页/共35页用RAPTOR为有向图建邻接矩阵为无向网建邻接矩阵22第22页/共35页用RAPTOR为无向图建邻接表26个顶点，44条边23第23页/共35页用RAPTOR为无向图建邻接表为无向图建邻接表24第24页/共35页从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次这一过程就叫做图的遍历(TraversingGraph)图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础通常有两条遍历图的路径：深度优先搜索和广度优先搜索它们对无向图和有向图都适用25第25页/共35页26第26页/共35页RAPTOR实现DFSDFS子图27第27页/共35页RAPTOR实现DFSTraverse子程序28第28页/共35页29第29页/共35页广度优先搜索的特点在广度优先搜索中，若顶点v在顶点u之前访问，则v的邻接点也将在u的邻接点之前访问由此，一般算法都采用队列来暂存那些刚访问过并且可能还有未访问的邻接点的顶点30第30页/共35页RAPTOR实现BFS-main子图31第31页/共35页RAPTOR实现BFSBFS子图32第32页/共35页RAPTOR实现BFSTravers子图33第33页/共35页RAPTOR实现BFSRecursion子图34第34页/共35页Endofch7-135第35页/共35页