Ch.7 图 图是一种复杂的非线性结构 应用：AI、工程、数学、生物、计算机 结点间的逻辑关系：任两个结点都可能相关

Presentation on theme: "Ch.7 图 图是一种复杂的非线性结构 应用：AI、工程、数学、生物、计算机 结点间的逻辑关系：任两个结点都可能相关"— Presentation transcript:

1 Ch.7 图 图是一种复杂的非线性结构 应用：AI、工程、数学、生物、计算机 结点间的逻辑关系：任两个结点都可能相关
1

2 §7.1 概念 Def：图由两集合组成G=(V, E) V(G):顶点集——顶点的有穷非空集 E(G):边集——V中顶点偶对的有穷集
无向图：边由顶点的无序对构成。 和 表示同一条边，称为无向边 有向图：边由顶点的有序对构成。 和 表示不同的有向边 弧尾 ——起点 弧头 ——终点 2 2

3 §7.1 概念 例子： 约定：只讨论简单图 不允许有反身边：即 或 则 不允许平行边： 中不允许有重复元素 3 3

4 §7.1 概念 顶点和边的关系：设 无向图： 当 时，则为零图 当 ，则称之为（无向）完全图 完全图中任一顶点到其他顶点均有边 有向图：
当 时，则为零图 当 ，则称之为（无向）完全图 完全图中任一顶点到其他顶点均有边 有向图： 当 ，则称之为有向完全图 4 4

5 §7.1 概念 稀疏图、稠密图. 边少、边多. 邻接与关联（依附） 若 ，则 和 互为邻接点 若 ，则 邻接到 ， 邻接自
若 ，则 和 互为邻接点 若 ，则 邻接到 ， 邻接自 边 和 关联（依附）于顶点 和 不好定义前驱和后继 5 5

6 §7.1 概念 顶点的度 无向图：关联于顶点的边数 。例 子图 有向图：出度—以 为起点的边数 入度—以 为终点的边数
无向图：关联于顶点的边数 。例 有向图：出度—以 为起点的边数 入度—以 为终点的边数 ——对有向或无向图均成立 子图 设 是图， ，且 中边所关联的顶点均在 中，则 亦为图，称之为G的子图。 6 6

7 §7.1 概念 路径 若存在一顶点序列 使 则称从 到 存在一条路径。 所经过的边数称为路径长度。 有向路径类似定义。 简单路径：
若存在一顶点序列 使 则称从 到 存在一条路径。 所经过的边数称为路径长度。 有向路径类似定义。 简单路径： 除起点和终点外，其余顶点均不相同的路径. 简单回路（环）： 起点和终点相同的简单路径。 7 7

8 §7.1 概念 有根图： 在有向图G中，若存在 ，从 到其他顶点均有路径可达，则 称为根，G为有根图。 连通、连通图、联通分量 设G为无向图
无向图中极大连通子图称为连通分量。 连通图只有一个连通分量，即自身。 8 8

9 §7.1 概念 强连通图 设G是有向图， ，若 到 及 到 都有路径，则是强连通图 n个顶点的强连通图至少有几条边？ 有向完全图是强连通图？
强连通分量： 有向图的极大强连通子图，称为强连通分量。 强连通图只有一个强连通分量。 例：G1不是强连通图，它有两个强连通分量。 加权图： 顶点、边上带权。 9 9

10 §7.2 图的存储结构 没有前驱和后继的关系，任两结点均可能有“邻接”关系 无向图中，邻接点互为对称，分不清谁是前驱和后继。
有向图中，边的起点为前驱，终点为后继，但有向环又如何表达？ 设G中， 多种表示法，重点介绍常用的两种。 10 10

11 §7.2.1 邻接矩阵表示法 邻接矩阵：表示顶点（数据元素）相邻关系的矩阵。 若顶点信息无关紧要，则用二维数组 表示， 对于加权图：
若顶点信息无关紧要，则用二维数组 表示， 对于加权图： 无向图的邻接矩阵是对称的 邻接矩阵表示法： 若顶点信息重要，则应将其组织成一个顺序表： 边表（邻接矩阵） 顶点表 11 11

12 §7.2.1 邻接矩阵表示法 类型说明 typedef int EdgeType; //边类型
#define MaxVertexNum //最大顶点数 typedef int EdgeType; //边类型 typedef char VertexType; //顶点类型 typedef struct{ VertexType vexs[MaxVertexNum]; //顶点表 EdgeType edges[MaxVertexNum][MaxVertexNum]; //边表，邻接矩阵 int n, e; //顶点数，边数 }MGraph； 12 12

13 §7.2.1 邻接矩阵表示法 建立无向图的邻接矩阵表示 step1：输入顶点数、边数 step2：输入顶点表 step3：初始化邻接矩阵
13 13

14 §7.2.2 邻接表 链式存储结构 为每个顶点的邻接关系建立一个单链表，将头结点放在一个数组中，形成一个顶点表和一个边表。 顶点表结点：
边表结点： 边表示： ，因为 和 分别存储在顶点表的ith和jth分量中，故只需在 的边表中存放序号j即可。 14 14

15 §7.2.2 邻接表 例： 说明 typedef struct node{//边表结点 int adjvex；//邻接点序号
struct node * next; //指向下一个边表结点 //若有权，则增加一域 }EdgeNode； 15 15

16 §7.2.2 邻接表 typedef struct vnode{//顶点表结点 VertexType vertex；//顶点数据域
EdgeNode * firestedge; //边表头指针 }VertexNode，AdjList[MaxVertexNum]；//邻接表类型 typedef struct { AdjList adjlist; //邻接表 int n, e; //顶点数和边数 }ALGraph； 16 16

17 §7.2.2 邻接表 无向图的邻接表 , 则在 的邻接表中有一 的边表结点。 在 的邻接表中有一 的边表结点。
, 则在 的邻接表中有一 的边表结点。 在 的邻接表中有一 的边表结点。 每条边表示了两次，所以一共有2e个边表结点。 空间复杂度为 ，邻接矩阵为 。 稀疏图邻接表节省空间，稠密图邻接矩阵为宜。 17 17

18 §7.2.2 邻接表 有向图的邻接表 , 在 的邻接表中有一个 的边表结点。 每边表示了1次，所以共有e个边表结点。 此时的边表称为出边表。
, 在 的邻接表中有一个 的边表结点。 每边表示了1次，所以共有e个边表结点。 此时的边表称为出边表。 出边表中求出度易，求入度难。 逆邻接表： , 在 的邻接表中有一个 的边表结点。 此时的边表称为入边表。 入边表中求入度易，求出度难。 18 18

19 §7.2.2 邻接表 建立邻接表 运算 时间： ，邻接矩阵 唯一性：不唯一，不同输入次序，结果不同。但邻近矩阵唯一。
时间： ，邻接矩阵 唯一性：不唯一，不同输入次序，结果不同。但邻近矩阵唯一。 运算 判 是否为边？ 邻接矩阵 ，邻接表 求顶点度数： 二者差不多 检测边数：邻接矩阵 ，邻接表 19 19

20 §7.3 图的遍历 是图上运算的基础 没有开始结点，如何访问？任两点可能相邻，故访问某点后可能顺回路又回到该点，为避免重复访问，须标记已访问过的顶点 Visited[0…n-1]布尔数组，初值为false 常用的方法有两种

21 §7.3.1 深度优先遍历（dfs遍历） 类似于树的前序遍历 基本思想
设G初态是所有顶点均未曾访问，∀v∈V(G)为初始出发点（源点），则深度优先遍历可定义为： 首先访问出发点v，将其标记为已访问； 然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w为出发点继续深度优先遍历，直至图中所有和v有路径相通的顶点均已被访问为止； 若此时图中仍有未访问过的顶点，则另选一尚未访问过的顶点作为新源点重复上述过程，直至图中所有顶点均已访问为止。

22 §7.3.1 深度优先遍历（dfs遍历） 特点：遍历定义是递归的，特点是尽可能先对纵深方向搜索，故称为深度优先搜索（dfs），搜索过程：

23 §7.3.1 深度优先遍历（dfs遍历） 设x是当前访问顶点：
若v1，v2，v3均未被访问过，则以v1为出发点向纵深搜索，不能前进后回溯到x，继续从v2，v3出发，当v2，v3为出发点搜索完成后回溯至x，因为x的所有邻接点均已访问过，故继续回溯至x之前被访问的顶点； 若v1，v2，v3均访问过，表示一定是从x之前被访问的顶点出发的搜索曾到达过v1，v2，v3，故访问x之后返回（回溯）至x之前的结点。

24 §7.3.1 深度优先遍历（dfs遍历） 算法实现 typedef enum {FALSE, TRUE} Boolean;
Boolean Visited[MaxVertexNum]; //全局量 void DFSTraverse(ALGraph *G) { //以邻接表表示图 for (i=0; i<G->n; i++) Visited[i] = FALSE; //初始化 if (! Visited[i]) //vi未访问过 DFS(G,i); //以vi为源点开始dfs搜索 //图连通仅有1次外部调用 }

25 §7.3.1 深度优先遍历（dfs遍历） void DFS (ALGraph *G, int i) { //以vi为出发点对G进行dfs
EdgeNode *p; printf (“%c”, G->adjlist[i].vertex); //访问顶点vi Visited[i]=TRUE; //标记vi已访问过 p=G->adjlist[i].firstedge; //取vi边表的头指针 while (p) { //依次搜索vi的邻接点vj if (!Visited[p->adjvex]) //若vj未访问过，j=p->adjvex DFS(G,p->adjvex); //以vj为出发点向纵深搜索 p=p->next; //若vj已访问过，或从vj出发的dfs完成，则 //找vi的下一邻接点 } 以邻接矩阵为存储结构自己写出DFS

26 §7.3.1 深度优先遍历（dfs遍历） 深度优先遍历序列（DFS序列） 遍历过程的顶点访问序列 G的DFS序列不唯一，但初始源点给定，存储
结构给定时所得序列唯一

27 §7.3.1 深度优先遍历（dfs遍历）

28 §7.3.1 深度优先遍历（dfs遍历） 时间 对G中每个顶点恰做一次访问（外部+内部调用dfs），∴共做n次访问
当访问顶点vi时，时间主要花费在搜索vi的邻接点上 合计：邻接表表示：〇(n+e)，各个边表结点均搜索到 邻接矩阵：〇(n2)，各个元素均检索到

29 §7.3.2 广度优先遍历 类似于树的层次遍历 基本思想 选一顶点v为源点访问之 依次访问v的所有邻接点w1,w2…wt
然后依次访问wi(1≤i≤t)的所有未曾访问过的邻接点 依次类推，直至图中所有和源v有路径连通的顶点均已访问过为止 此时，若G是连通图，则遍历完成；否则选G的另一未访问过的顶点做新源点继续上述搜索过程，直至G中所有顶点均已访问过为止

30 §7.3.2 广度优先遍历 特点 尽可能先对横向搜索，故称之为广度优先搜索（BFS） 非递归，用队列作为中间 递归、回溯，用栈保存访
非递归，用队列作为中间 递归、回溯，用栈保存访 数据结构 问过的顶点 先访问的顶点其邻接点亦 后访问的顶点其邻接点被先 被先访问（FIFO） 访问 （LIFO）

31 §7.3.2 广度优先遍历 设x和y是两个相继访问的顶点，其邻接点分别记为x1,…,xs和y1,…,yt
∴可用FIFO队列 保存已访问过的顶点 顶点入队时对其访问 保存尚未访问过的顶点 顶点出队时对其访问 第一种方法较好，下面用此方法实现算法

32 §7.3.2 广度优先遍历 算法 遍历算法类似于DFSTraverse
void BFS(ALGraph *G, int k) { //以vk为源 InitQueue(&Q); //队列Q初始化 printf(“%c”, G->adjlist[k].vertex); //访问源vk Visited[k]=TRUE; EnQueue(&Q, k); //相当于vk入队

33 §7.3.2 广度优先遍历 while ( !QueueEmpty(&Q) ) { i=DeQueue(&Q); //vi出队
p=G->adjlist[i].firstedge; //取vi边表头指针 while(p) { //依次搜索vi的邻接点vj if(!Visited[p->adjvex]) //vj未访问过，设p->adjvex=j printf(“%c”,G->adjlist[p->adjvex].vertex); //访问vj Visited[p->adjvex]=TRUE; EnQueue(&Q, p->adjvex); //vj入队 } p=p->next; //在下一边表结点中找vi下一个邻接点

34 §7.3.2 广度优先遍历 BFS队列 时间 每个顶点入队一次，每个边表结点搜索一次 时间与dfs相同

35 §7.4 图的连通性问题 §7.4.1 无向图的连通分量和生成树 1.求连通分量 每外部调用一次DFS或BFS，可求一连通分量的顶点集
2.生成树和生成森林 生成树 连通图G的极小连通子图，但包含G的所有顶点（支撑树），不唯一 n个顶点的连通图的生成树一定有n-1条边

36 §7.4.1 无向图的连通分量和生成树 生成森林：各连通分量的生成树集合 求生成树和生成森林（使用DFS和BFS）
设G是无向图，∀v∈V(G)做出发点 若图连通，则做一次DFS或BFS，必将G中n个顶点都访问到，且只做一次访问 两种搜索方法中，从vi搜索到vj时，须经过边(vi,vj)，故只需添加输出边的操作即可：

37 §7.4.1 无向图的连通分量和生成树 在dfs和bfs中，均在 while(p) {
if( !Visited[p->adjvex] ) { 加入打印：（i，p->adjvex） //dfs须在递归前加入 } 若G连通则求出的生成树，否则为生成森林 若G为有向图，仅当源点为有根图的根时，才能求得生成树，否则为生成森林