第七章 图.

Presentation on theme: "第七章 图."— Presentation transcript:

1 第七章 图

2 7.1 图的定义与基本术语 7.1.1 图的定义 图（Gragh）是一种网状数据结构，其形式化定义如下：
Gragh=(V,R)//由顶点集和顶点间的关系构成 V={x|x∈DataObject} R={VR} VR={<x,y>|P(x,y)^(x,y ∈ V)}

3 有向图和无向图例 无向图 有向图 有向网 无向网 弧arc 边edge A C E F D B 15 10 11 20 6 4 3 A C

4 完全图、稀疏图、稠密图 7.1.2 基本术语 3阶有向完全图 3阶完全图 4阶完全图 稀疏图 A B C A B C A C E F D B

5 子图 有向图G2 无向图G1 G1的子图H1 G2的子图H2 A C E F D B A C E F D B A C E F D B A C

6 邻接点，度、入度和出度 若图中有n个顶点，e条边或弧，则图中的度与边数的关系为： e=( )/2
(2，1) (0，2) A C E F D B 2 A C E F D B 3 相邻 (1，1) (1，1) 2 2 (2，0) 2 (1，2) 3 而对于有向图G2， 也有类似的描述 对于无向图G1，通常采 用如下的方式描述： 若图中有n个顶点，e条边或弧，则图中的度与边数的关系为： e=( )/2 对于有向图，所有顶点的入度之和等于所有顶点的出度之和 G2={V,E} V={A,B,C,D,E,F} E={<B,A>,<C,A>,<A,F> ,<B,D>,<E,C>,(E,D>, <F,E>} G1={V,E} V={A,B,C,D,E,F} E={(A,B),(A,C),(A,F) ,(B,D),(C,E),(D,E), (E,F)}

7 路径与回路，连通图 A C E F D B A B C A C E F D B A C E F D B

8 7.2 图的存储结构 7.2.1 邻接矩阵表示法 图的邻接矩阵表示法既是图的顺序存储表示法，又称为数组表示法。通常采用两个数组来表示一个图：一个是用来存储顶点信息的一维数组，另一个是用来存储顶点之间的相邻关系的二维数组，该二维数组被称为邻接矩阵。

9 不同的图以及它们的邻接矩阵 A C E F D B 无向图G1 A C E F D B 有向图G2

10 不同的图以及它们的邻接矩阵 无向网G1 有向网G2 A C E F D B 15 10 11 20 6 4 3 A C E F D B 15

11 邻接矩阵表示法C语言描述 #define MAX_VERTEX_NUM 20/*定义最多顶点个数*/
#define INFINITY /*定义无穷大*/ /*描述图的类型，用枚举型类型来说明*/ typedef enum{DG,DN,UDG,UDN}GraphKind; /*定义顶点数据类型*/ typedef char VertexData; /*定义邻接矩阵中元素值(即边信息）的数据类型*/ typedef int ArcNode; /*定义图的邻接矩阵类型：一个顶点信息的一维数组，一个邻 接矩阵、当前图中包含的顶点数、边数以及图类型（有向图、 有向网、无向图、无向网）*/ typedef struct { VertexData vertex[MAX_VERTEX_NUM]; ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vertexnum,arcnum; GraphKind kind; } AdjMatrix;//图的邻接矩阵表示类型

12 7.2.2 邻接表表示法 图的邻接表表示法是图的链式存储表示法，比较适合存储稀疏图。在邻接表中，首先建立一个表头结点表，该表的作用类似于邻接矩阵中的顶点数组，表中存储着所有顶点的信息。将该表中的每个元素作为链表的头结点，对图中的每个顶点建立一个单链表，该单链表中的结点就是与此顶点关联的边对应的另一个顶点信息以及边的信息（比如权值等），因此称这样的结点为边结点或者弧结点。所以，图的邻接表表示也是由两部分构成：表头结点表和边链表。

13 表头结点结构、边（弧）结点结构及实例图的
表头结点结构 边（弧）结点结构 vexdata firstarc adjvex info nextarc A C D B 15 10 8 6 AB CD 0123 ^ ^ ^ ^

14 存放顶点信息的结点数组，其每个结点相当于单链表的头结点
构造图的邻接表 图中的邻接表，都包含一些什么信息呢？ 与顶点A相邻的边结点链表 存放顶点信息的结点数组，其每个结点相当于单链表的头结点 AB CD 0123 ^ ^ A C D B 15 10 8 6 ^ ^

15 邻接表存储结构 /*定义最多顶点个数*/ #defined MAX_VERTEX_NUM 20 /*枚举图的种类*/
typedef enum{DG,DN,UDG,UDN}GraghKind; /*边结点类型*/ typedef struct ArcNode{ int adjvex;//与表头顶点相邻的顶点的坐标值 int info;//存储边的信息，如权值 struct ArcNode *nextarc;//指点下一条边（弧）的指针 }ArcNode; /*定义表头结点数据类型*/ typedef strcut VertexNode{ char data; ArcNode *firstarc; }VertexNode;

16 /. 定义图的邻接表的基本状态信息. / typedef struct { /. 存放图的顶点信息的表头结点数组
/*定义图的邻接表的基本状态信息*/ typedef struct { /*存放图的顶点信息的表头结点数组*/ VertexNode vertex[MAX_VERTEX_NODE]; /*具体图的顶点数和边（弧）数*/ int vexnum,arcnum; GraghKind kind； }AdjList；//定义一个基于邻接表的图类型

17 让我们来分析一下如何正确的使用邻接表存储一个图。
第一步：初始化。在该步骤中给出图的顶点数、边 （弧）数以及表头结点组。 例如对于下图，其初始的状态为： G.vexnum=4; G.arcnum=4; AB CD 0123 ^ A C D B 15 10 8 6

18 第二步：输入边结点信息，建立与各个表头结点邻接 的边结点链表。
输入<A,B>15,<A,C>6,<C,D>8,<D,A>10后，分别建立4 个边结点结点，存储这些边结点信息，然后将这些边 结点插入到相应的表结点链表中。可是关键的问题是 如何根据输入的边结点信息找到正确的链接位置？ 利用一个定位函数（类似邻接数组的方法）， LocateVertex（G，v）得到顶点v在表头结点数组中的 位置即可。

19 7.3 图的遍历 深度优先搜索遍历DFS 图的深度优先搜索遍历是指按照深度方向的搜索（纵向搜索），类似于树的先序遍历。其基本思想是： （1）从图中某个顶点v0 出发，首先访问v0 。 （2）找出刚访问过的顶点的第一个未被访问过的邻接点，然后访问该顶点。以该顶点为新顶点，重复此步骤，直到刚访问的顶点没有未被访问的邻接点为止。 （3）返回前一个访问过的且仍有未被访问过的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。然后执行步骤（2）。

20 深度优先搜索遍历的递归算法 首先对v0 所在的连通子图的深度优先搜索用递归算法实现： （1）访问出发点v0 。 （2）依次以v0 的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与v0有路径相通的顶点都被访问。 若是非连通图，则图中一定还有顶点未被访问，需要从图中另选一个未被访问ideas顶点作为起始点，重复上述深度优先搜索过程，直到图中所有顶点均被访问过为止。

21 7.3.2 广度优先搜索遍历BFS 图的深度优先搜索遍历是指按照广度方向的搜索（横向搜索），类似于树的层次遍历。其基本思想是： （1）从图中某个顶点v0 出发，首先访问v0 。 （2）依次访问v0 的各个未被访问的邻接点。 （3）分别从这些邻接点出发，依次访问它们的各个未被访问的邻接点。重复（3）直到所有结点都被访问为止。

22 分析：下图中从顶点A出发的深度优先搜索和广度优先搜索遍历结果分别是什么？
深度优先搜索：ABCFEGDHI ADGHIEBCF ABEGDHICF …… 广度优先搜索：ABDECGFHI AEDBGCHFI ABEDCGFHI …… A B C F E D H G I

23 7.4 图的应用 7.4.1 图的连通性问题 1 无向图的连通分量 2 图中两个顶点之间的简单路径 3 生成树和最小生成树
图的连通性问题 1 无向图的连通分量 2 图中两个顶点之间的简单路径 3 生成树和最小生成树 (1) Prim算法 （2）Crusckal算法

24 7.4.1 图的连通性问题 1 无向图的连通分量 2 两个顶点之间的简单路径 从A到G的简单路径： A->B->E->G
图的连通性问题 1 无向图的连通分量 A C E F D B 2 两个顶点之间的简单路径 A B C F E D H G I 从A到G的简单路径： A->B->E->G A->D->G ……

25 3 图的生成树和最小生成树 （1）生成树：一个连通图的生成树是指一个极小 连通子图，它含有图中的全部顶点。 A B C F E D H G
I A B C F E D H G I A B C F E D H G I A B C F E D H G I

26 最小生成树：在一个连通网的所有生成树中，各边的 代价之和最小的那棵生成树称为该连通网的最小代 价生成树，简称最小生成树（MST）
A B C F E D H G I 6 5 4 3 8 7 A B C F E D H G I 4 3 8 6 5 7

27 3. 克鲁斯卡尔 (Kruskal) 算法 (1) 算法思想
27 3. 克鲁斯卡尔 (Kruskal) 算法 (1) 算法思想 假设 N = (V, {E}) 是一个连通网，则令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T = (V, { })，图中每个顶点自成一个连通分量。克鲁斯卡尔 (Kruskal)算法执行如下操作： 在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中，否则舍去此边而选择下一条代价最小的边。依此类推，直至 T 中所有顶点都在同一连通分量上为止。

28 Crusckal算法过程演示： A A E F D C B A 6 5 1 2 4 3 1 1 B B E E F F 2 D C D C

29 29 2. 普里姆 (Prim) 算法 (1) 算法思想 假设 N = ( V, {E} ) 是一个连通网，TE 是 V 上最小生成树边的集合。普里姆 (Prim) 算法从 U = { u0 } ( u0 ∈V )，TE = { } 开始。重复执行如下操作： 在所有 u ∈U，v ∈V-U 的边 (u, v) ∈E 中寻找一条代价最小的边 (u0, v0) 并入集合 TE，同时 v0 并入 U，直至 U = V 为止。此时 TE 中必有 n-1 条边，则 T = ( V, {TE} ) 为 N 的最小生成树。

30 Prim算法过程演示： A F A 1 E F D C B A 6 5 1 2 4 3 E F D C B A 6 5 1 2 4 3 E

31 31 某个源点到其他顶点的最短路径 给定带权有向图 G = (V, E)，E 中每一条弧 (w, v) 都有非负的权。指定 V 中的一个顶点 v 作为源点，找从源点 v 出发到图中所有其他各顶点的最短路径，这就是求某个源点带其他顶点的最段路径。

32 1 求一结点到其他结点的最短路问题（Dijkstra） 2 图中任意两个顶点之间的最短路径（Floyd）

33 为了求得最短路径，迪杰斯特拉 (Dijkstra) 提出了一个按路径长度递增的次序产生最短路径的算法。
33 1. 迪杰斯特拉 (Dijkstra) 算法思想 为了求得最短路径，迪杰斯特拉 (Dijkstra) 提出了一个按路径长度递增的次序产生最短路径的算法。 首先引进一个辅助向量 D，它的每个分量 D[i] 表示当前所找到的从始点 v 到每个终点的最短路径的长度。它的初态为：如果从 v 到 vi 有弧，则 D[i] 为弧上的权值；否则置 D[i] 为 ∞。显然，长度为 的路径就是从始点 v 出发的长度最短的一条最短路径。此路径为 ( v, vi )。

34 34 有向网 G 带权邻接矩阵 v0 v1 v5 v2 v4 v3 100 60 30 10 5 50 20 若对有向网 G 实施迪杰斯特拉 (Dijkstra) 算法，则所得从 v0 到其余各顶点的最短路径，以及运算过程中 D 向量的变化状况如下所示。

35 从 v0 到各终点的 D 值和最短路径的求解过程 终点 v1 v2 v3 v4 v5 vj S i = 1 i = 2 i = 3
35 从 v0 到各终点的 D 值和最短路径的求解过程 终点 v1 v2 v3 v4 v5 vj S i = 1 i = 2 i = 3 i = 4 i = 5 ∞ ∞ ∞ ∞ ∞ 10 (v0, v2) ∞ 60 50 (v0, v2, v3) (v0, v4, v3) 30 30 (v0, v4) (v0, v4) 100 100 90 60 (v0, v5) (v0, v5) (v0, v4, v5) (v0,v4,v3,v5) v2 v4 v3 v5 (v0, v2) (v0, v2, v4) (v0,v2,v3,v4) (v0,v2,v3,v4,v5)