第7章 图论基础与应用 PART A 《可视化计算》

学习目标 什么是图论? 图论有哪些基本的概念? 图论可以用来解决那些问题? 如何在RAPTOR中保存图的数据结构？ 图算法有哪些重要应用?

图论基础 图 (Graph)，它有若干个不同的点v1，v2， …，vn，在其中一些点之间用直线或曲线连接

图论基础（2） 图中的这些点被称为顶点 (vertex)或结点，连接顶点的曲线或直线称为边 (edge) 通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图，顶点通常被称作是图中的数据元素。 在图1中 ⑴图中的边没有方向，这类图称为无向图 (undirected graph)。在记录无向图时， (v1，v2 )等价于 (v2，v1)。 在图1中 ⑵图中的边上有一个箭头，它表示边的方向，这类图称为有向图 (directed graph)。在记录有向图时， <v1，v2 >与 <v2，v1 >是两条不同的边。 4

图论基础（3） (a)图(无向图)的顶点集合为： V ＝｛v1，v2，v3，v4｝ 边集合为： E ＝｛（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）｝ 图1中 ⑴图的顶点集合为： V ＝｛v1，v2，v3，v4｝ 边集合为： E ＝｛（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）｝ 图1中 ⑵图的顶点集合为： E ＝｛ <v1，v2 >， <v1，v3 >， <v1，v4 >， <v2，v1 >， <v4，v2 >} 5

图论基础（3） (b)图中（有向图）的顶点集合为： V ＝｛v1，v2，v3，v4｝ 边集合为： E ＝｛ <v1，v2 >， <v1，v3 >， <v1，v4 >， <v2，v1 >， <v4，v2 >} 图1中 ⑴图的顶点集合为： V ＝｛v1，v2，v3，v4｝ 边集合为： E ＝｛（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）｝ 图1中 ⑵图的顶点集合为： E ＝｛ <v1，v2 >， <v1，v3 >， <v1，v4 >， <v2，v1 >， <v4，v2 >} 6

图的常用术语（1） （c)图中的v1点本身也有边相连，这种边称为环 有限图：顶点与边数均为有限的图，如上三个图均属于有限图

图的常用术语（2） 简单图：没有环且每两个顶点间最多只有一条边相连的图，如(a)图（无环无向）

图的常用术语（4） 邻接与关联：当（v1，v2） ∈E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（ adjacent），同时称（v1，v2）是与顶点v1、v2相关联的边

图的常用术语（5） 顶点的度数 (degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度

图的常用术语（6） 连通图：对于图中任意两个顶点vi、vj ∈V，vi、vj之间有道路相连，则称该图为连通图 (connected graph)，如 (a)图 终端顶点：有向图中把出度为 0的顶点称为终端顶点，如 (b)图的v3

图的常用术语（7） 带权图：给各图的边上附加一个代表性数据 (比如表示长度、流量或其他 )，则称其为带权图 网络/网图：带权的连通图

图的主要应用 图的历遍: 走遍所有节点，(BFS/DFS) 生成树的概念 网络中的最短/最省的路径:Dijkstra算法 最小生成树—构建某些城市之间的最省的公路通道 网络中的最短/最省的路径:Dijkstra算法 地图着色: 所谓的四色”定理” 最小支配集问题: 城镇商业网点的配置

使用Raptor构建图算法的要点 基本图形的资料库 数据的存储方式 主要难点：图类数据中边（edges）的输入 有向图；有向网；无向图；无向网 数据的存储方式 邻接矩阵 邻接表 主要难点：图类数据中边（edges）的输入 为测试方便，建议使用文件保存“边”的数据

图的数据储存 图的数据储存有两种常用方式 邻接表(+占用空间少，适合计算大型图应用) 邻接矩阵(+直观； -占用空间大(n2))

有向图与邻接矩阵

无向图与邻接矩阵

有向网与邻接矩阵

Raptor中的图的创建 主要步骤： 输入顶点数（可以通过文件输入） 输入边数（可以通过文件输入） 顶点字符串初始化 邻接矩阵/邻接表初始化 输入边（两个顶点编号） 可以通过文件输入

用RAPTOR为无向图建邻接矩阵 26个顶点，44条边

用RAPTOR为无向图建邻接矩阵 为无向图建邻接矩阵

用RAPTOR为无向网建邻接矩阵 6个顶点 10条边 三个数据描述一条边

用RAPTOR为有向图建邻接矩阵 为无向网建邻接矩阵

用RAPTOR为无向图建邻接表 26个顶点，44条边

用RAPTOR为无向图建邻接表 为无向图建邻接表

图的遍历 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次这一过程就叫做图的遍历(Traversing Graph) 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础 通常有两条遍历图的路径：深度优先搜索和广度优先搜索 它们对无向图和有向图都适用

图的遍历：深度优先搜索例子

RAPTOR实现DFS DFS子图

RAPTOR实现DFS Traverse子程序

图的遍历：广度优先搜索例子

广度优先搜索的特点 在广度优先搜索中，若顶点v在顶点u之前访问，则v的邻接点也将在u的邻接点之前访问 由此，一般算法都采用队列来暂存那些刚访问过并且可能还有未访问的邻接点的顶点

RAPTOR实现BFS-main子图

RAPTOR实现BFS BFS子图

RAPTOR实现BFS Travers子图

RAPTOR实现BFS Recursion子图

End of ch7-1