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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§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之前的结点。

§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次外部调用 }

§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

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

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

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

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

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

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

§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入队

§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下一个邻接点

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

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

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

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