中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）Ch7 图（1/3）.pdf_大学文库

201447 §7.1概念 s7.1概念路径有根田：若存在一顶点序列y,a,a…v,使在有向图G中，若存在v∈V,从y到其他顶点均有 (w,ahaa…,(y.y,)eE(G 路径可达，则称为根，G为有根图。则称从到，存在一条路径。”，0 连通、连通图、联通分量所经过的边数称为路径长度。设G为无向图有向路径类似定义。 ①G中，若y和y有路径，则称y和连通。若y,yeV(Gy,和V,均连通，则G为连通图. 简单路径：无向图中极大连通子图称为连通分量。除起点和终点外，其余顶点均不相同的路径，连通图只有一个连通分量，即自身。葡单回路（环）：起点和终点相同的筒单路径。 S7.1概念 §7.2图的存储结构强连通图没有前驱和后继的关系，任两结点均可能有“邻终盟⊙，苦到及y到有接”关系个顶点的强连通图至少有几条边？无向图中，邻接点互为对称，分不清淮是前驱和有向完全图是强连通图？后继。强连通分量：有向图中，边的起点为前驱，终点为后继，但有有向图的极大强连通子图，称为强连通分量。向环又如何表达？强连通图只有一个强连通分量。设G中，V(G=o,…,} 例：G不是强连通图，它有两个强连通分量。多种袁示法，重点介绍常用的两种。加权图：顶点、边上带权。 87.2.1邻接矩阵表示法 87.2.1邻接矩阵表示法邻接矩阵：表示项点（数据元素）相邻关系的矩库。类型说明若项点值意无关赛要，则用二维数组人，表示，n=Y(G #define MaxVertex Num1oo象大顶点数 44刀-.h或<光O 否则 typedef int EdgeType;边类里对于加权图： typedef char VertexType;项点类型 n-.以减oao typedef struct 123 Vertex Type vexsMaxVertexNum:/顶点w n10 无向图的邻接矩阵是对称的 EdgeType edges Max VertexNumMaxVertexNuml; 邻接矩阵表示法：边表，矩阵若顶点信惠量要，则应将其组织成一个顺序表： int血，c:顶点数，边数边表（邻接矩阵） →邻接矩阵表示法 )MGraphi 顶点表 2

2014/4/7 2 §7.1 概念  路径若存在一顶点序列使则称从到存在一条路径。 7 所经过的边数称为路径长度。有向路径类似定义。  简单路径：除起点和终点外，其余顶点均不相同的路径.  简单回路（环）：起点和终点相同的简单路径。 §7.1 概念  有根图：在有向图G中，若存在，从到其他顶点均有路径可达，则称为根，G为有根图。  连通、连通图、联通分量设G为无向图 8 ① G中，若和有路径，则称和连通。 ② 若，和均连通，则G为连通图。 ③ 无向图中极大连通子图称为连通分量。连通图只有一个连通分量，即自身。 §7.1 概念  强连通图设G是有向图，，若到及到都有路径，则是强连通图 n个顶点的强连通图至少有几条边？有向完全图是强连通图？强连通分量 9  ：有向图的极大强连通子图，称为强连通分量。强连通图只有一个强连通分量。例：G1不是强连通图，它有两个强连通分量。  加权图：顶点、边上带权。 §7.2 图的存储结构没有前驱和后继的关系，任两结点均可能有“邻接”关系  无向图中，邻接点互为对称，分不清谁是前驱和后继。  有向图中边的起点为前驱终点为后继但有 10  有向图中，边的起点为前驱，终点为后继，但有向环又如何表达？设G中，多种表示法，重点介绍常用的两种。 §7.2.1 邻接矩阵表示法  邻接矩阵：表示顶点（数据元素）相邻关系的矩阵。若顶点信息无关紧要，则用二维数组表示，对于加权图： 11 无向图的邻接矩阵是对称的  邻接矩阵表示法：若顶点信息重要，则应将其组织成一个顺序表：边表（邻接矩阵）顶点表 §7.2.1 邻接矩阵表示法  类型说明 #define MaxVertexNum 100 //最大顶点数 typedef int EdgeType; //边类型 typedef char VertexType; //顶点类型 t d f t t{ 12 typedef struct{ VertexType vexs[MaxVertexNum]; //顶点表 EdgeType edges[MaxVertexNum][MaxVertexNum]; //边表，邻接矩阵 int n, e; //顶点数，边数 }MGraph；

201447 §7.2.2邻接表 §7.3图的遍历建立邻接表 ①时间：O(n+e),邻接矩阵On) ◆是图上运算的基础 ②唯一性：不唯一，不同轴入次序。结果不同。但邻 ·没有开始结点，如何访问？任两点可能相邻，故近矩阵雕一。访问某点后可能顺回路又回到该点，为避免重复访运算问，须标记已访问过的顶点 ①判(，)是香为边？邻接矩阵O),邻接表O) ●Visited0.n-1]布尔数组，初值为false ②求顶点度数：二者差不多O() ◆常用的方法有两种 @检测边数：邻接矩阵O(),邻接表O(n+) §7.3.1深度优先遍历(dfs遍历) s7.3.1深度优先遍历(ds遍历) 类似于树的前序遍历 ●基本思想 ·特点：遍历定义是递归的，特点是尽可能先对纵深方向搜索，故称为深度优先搜索设G初态是所有顶点均未曾访问，寸vV(G)为初始出发点（源点），则深度优先遍历可定义为： (dfs),搜索过程首先访问出发点v,将其标记为已访问：然后依次从v出发搜索y的每个邻接点W,若未曾已访问过回溯“” 访问过，则以为出发点继续深度优先遍历：直至图中所有和v有路径相通的顶点均已被访问为止；碰壁回头（典型的回溯法）若此时图中仍有未访问过的顶点，则另选一尚未访问过的顶点作为新源点重复上述过程，直至国中所有顶点均已访问为止。 s7.31深度优先遍历(dfs遍历) s7.3.1深度优先遍历(dfs遍历) ·算法实现设x是当前访问顶点： typedef enum (FALSE,TRUE)Boolean; ①若y1,Y3,Y均未被访阋过，则以Y,为出发点向纵深搜索，不能前进后回溯到×，继续 Boolean Visited Max VertexNum:/全局量丛ygY3出发，当y2,y3为出发点搜索完成 void DFSTraverse(ALGraph*G){以邻接接表示图后回湖至x,因为×的所有邻接点均已访问过 for (i-0;in;i++) ,故继续回潮至x之前被访问的顶点； Visited时-FALSE:初始化 ②若y1,y2,y均访问过，表示一定是从x之前 for (i-0;in;i++) 限2智芝动抽 if:Visited未访问过 DS(G,i:以y为源点开始ds搜寮点。 /图连通仅有1次外都调用

2014/4/7 4 §7.2.2 邻接表  建立邻接表 ① 时间：，邻接矩阵 ② 唯一性：不唯一，不同输入次序，结果不同。但邻近矩阵唯一。运算 19  ① 判是否为边？邻接矩阵，邻接表 ② 求顶点度数：二者差不多 ③ 检测边数：邻接矩阵，邻接表 §7.3 图的遍历  是图上运算的基础  没有开始结点，如何访问？任两点可能相邻，故访问某点后可能顺回路又回到该点，为避免重复访问，须标记已访问过的顶点 20  Visited[0…n-1]布尔数组，初值为false  常用的方法有两种 §7.3.1 深度优先遍历（dfs遍历）类似于树的前序遍历  基本思想设G初态是所有顶点均未曾访问，∀v∈V(G)为初始出发点（源点），则深度优先遍历可定义为：首先访问出发点v，将其标记为已访问； 21 首先访问出发点然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w为出发点继续深度优先遍历，直至图中所有和v有路径相通的顶点均已被访问为止；若此时图中仍有未访问过的顶点，则另选一尚未访问过的顶点作为新源点重复上述过程，直至图中所有顶点均已访问为止。 §7.3.1 深度优先遍历（dfs遍历）  特点：遍历定义是递归的，特点是尽可能先对纵深方向搜索，故称为深度优先搜索（dfs），搜索过程： 22 §7.3.1 深度优先遍历（dfs遍历）设x是当前访问顶点： ① 若v1，v2，v3均未被访问过，则以v1为出发点向纵深搜索，不能前进后回溯到x，继续从v2，v3出发，当v2，v3为出发点搜索完成后回溯至x，因为x的所有邻接点均已访问过故继续回溯至之前被访问的顶点 23 ， 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; in; i++) 24 Visited[i] = FALSE; //初始化 for (i=0; in; i++) if (! Visited[i]) //vi 未访问过 DFS(G,i); //以vi 为源点开始dfs搜索 //图连通仅有1次外部调用 }

2014/4/7 5 §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 25 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序列不唯一，但初始源点给定，存储结构给定时所得序列唯 26 一 §7.3.1 深度优先遍历（dfs遍历） 27 §7.3.1 深度优先遍历（dfs遍历） 时间 ① 对G中每个顶点恰做一次访问（外部+内部调用 dfs），∴共做n次访问 ②当访问顶点vi 时，时间主要花费在搜索vi 的邻接 28 ②当访问顶点vi 时，时间主要花费在搜索vi 的邻接点上合计：邻接表表示：〇(n+e)，各个边表结点均搜索到邻接矩阵：〇(n2)，各个元素均检索到 §7.3.2 广度优先遍历类似于树的层次遍历  基本思想 ①选一顶点v为源点访问之 ②依次访问v的所有邻接点w1,w2…wt 29 ③然后依次访问wi (1≤i≤t)的所有未曾访问过的邻接点依次类推，直至图中所有和源v有路径连通的顶点均已访问过为止此时，若G是连通图，则遍历完成；否则选G的另一未访问过的顶点做新源点继续上述搜索过程，直至G中所有顶点均已访问过为止 §7.3.2 广度优先遍历  特点尽可能先对横向搜索，故称之为广度优先搜索（BFS） 30 非递归，用队列作为中间递归、回溯，用栈保存访数据结构问过的顶点先访问的顶点其邻接点亦后访问的顶点其邻接点被先被先访问（FIFO）访问（LIFO）

2014/4/7 6 §7.3.2 广度优先遍历设x和y是两个相继访问的顶点，其邻接点分别记为x1,…,xs和y1,…,yt ∵x在y之前访问，故x1,…,xs中未访问顶点亦先于y1,…,yt 中未访问被访问到 31 ∴可用FIFO队列 ①保存已访问过的顶点顶点入队时对其访问 ②保存尚未访问过的顶点顶点出队时对其访问第一种方法较好，下面用此方法实现算法 §7.3.2 广度优先遍历 算法遍历算法类似于DFSTraverse void BFS(ALGraph *G, int k) { //以vk为源 InitQueue(&Q); //队列Q初始化 32 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 33 p( , j [p j ] ); 访问 j Visited[p->adjvex]=TRUE; EnQueue(&Q, p->adjvex); //vj 入队 } p=p->next; //在下一边表结点中找vi 下一个邻接点 } } } §7.3.2 广度优先遍历 BFS队列 34 时间每个顶点入队一次，每个边表结点搜索一次时间与dfs相同 §7.4 图的连通性问题 §7.4.1 无向图的连通分量和生成树 1.求连通分量每外部调用一次DFS或BFS，可求一连通分量的顶点集 35 2.生成树和生成森林 生成树连通图G的极小连通子图，但包含G的所有顶点（支撑树），不唯一 n个顶点的连通图的生成树一定有n-1条边 §7.4.1 无向图的连通分量和生成树 生成森林：各连通分量的生成树集合 求生成树和生成森林（使用DFS和BFS） ①设G是无向图，∀v∈V(G)做出发点若图连通则做一次DFS或BFS 必将G中n个 36 若图连通，则做次DFS或BFS，必将G中n个顶点都访问到，且只做一次访问两种搜索方法中，从vi 搜索到vj时，须经过边 (vi ,vj )，故只需添加输出边的操作即可：