2014/47 Ch.7图 s7.1概念 Def:图由两集合组成G=(V,E) V(G):顶点集—顶点的有穷非空集 图是一种复杂的非线性结构 E(G):边集—V中顶点俱对的有穷集 无向图：边由顶点的无序对构成。 应用：AI、工程、数学、生物、计算机 化，y)和W》表示同一条边，称为无向边： 有向图：边由顶点的有序对构成。 结点间的逻辑关系：任两个结点都可能相关 (化》和化）表示不同的有向边 话弧尾y—起点 弧头乃，—终点 S7.1概念 §7.1概念 例子： 顶点和边的关系：设=m=e G ①无向图：0se3n-/2 当e=0时，则为零图(E=D) G3 G=W,E)片=(G)=,,%,v,} 当e=(a-)/2,则称之为（无向）完全图 E=(G)=K,>,,} G=(,E)Y2=(G)=,,} 完全图中任一顶点到其他顶点均有边 E=E(G={a,)(,2,(y,y(,2.(g,)》 ②有向图： 约定：只讨论简单图 0sesn(n-1) ①不允许有反身边：即W,)或化〉es则男*可 当e=(n-),则称之为有向完全图 3 ②不允许平行边：(O中不允许有重复元赛 S7.1概念 87.1概念 顶点的度 ③稀疏图、调密图 无向图：关联于顶点的边数D),例veV(G)D)=4 边少、边多。 e<nlgn? 有向图：出度一以~为起点的边数OD() 邻接与关联（依附） D)=ID)+OD) 入度一以v为终点的边数D(y】 若g=g,)eE,则￥和y互为邻接点 v和v相绍找 之)一对有向或无向图均成立 e 2 若g=(》eE,则y邻接到y,y邻接自 子图 边6和%关联（依附）于顶点y和 设G=(W,)是图，F,EcE且E中边所关联的顶点 均在中，则G=V,E)亦为图，称之为G的子图。 不好定义前驱和后继 G-(,.,修，)》不是G的好图因为不是图
2014/4/7 1 Ch.7 图 图是一种复杂的非线性结构 1 应用：AI、工程、数学、生物、计算机 结点间的逻辑关系：任两个结点都可能相关 §7.1 概念 Def：图由两集合组成G=(V, E) V(G):顶点集——顶点的有穷非空集 E(G):边集——V中顶点偶对的有穷集 无向图：边由顶点的无序对构成。 2 无向图：边由顶点的无序对构成。 和 表示同一条边，称为无向边 有向图：边由顶点的有序对构成。 和 表示不同的有向边 弧尾 ——起点 弧头 ——终点 §7.1 概念 例子： 3 约定：只讨论简单图 ① 不允许有反身边：即或 则 ② 不允许平行边： 中不允许有重复元素 §7.1 概念 顶点和边的关系：设 ① 无向图： 当 时，则为零图 当 则称之为（无向）完全图 4 当 ，则称之为（无向）完全图 完全图中任一顶点到其他顶点均有边 ② 有向图： 当 ，则称之为有向完全图 §7.1 概念 ③ 稀疏图、稠密图. 边少、边多. 邻接与关联（依附） 若 则 和 互为邻接点 5 若 ，则 和 互为邻接点 若 ，则 邻接到 ， 邻接自 边 和 关联（依附）于顶点 和 不好定义前驱和后继 §7.1 概念 顶点的度 无向图：关联于顶点的边数 。例 有向图：出度—以 为起点的边数 入度—以 为终点的边数 对有向或无向图均成立 6 —— 子图 设 是图， ，且 中边所关联的顶点 均在 中，则 亦为图，称之为G的子图
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；
2014/47 §7.2.1邻接矩阵表示法 §7.2.2邻接表 链式存储结构 。建立无向图的邻接矩阵表示 stpl:输入顶点数、边数O四 为每个顶点的邻接关系建立一个单链表，将头结点 放在一个数组中，形成一个顶点表和一个边表。 se2:输入顶点表 o 顶点表结点： 顶点数据 step巾：初始化邻接矩阵 0w) 标+为向第一个边表结点（边表的头结点） sen4:输入边（及权值） O(e) 边表结点： 接点号 ☐→边浓站点法边仪，则端个级 边表示：（化，y》,因为”和分别存情在顶点表的th 和h分量中，故只需在y的边表中存放序号引即可。 87.2.2邻接表 S7.22邻接表 例： 123 typedef struct vnode顶点表结点 03子2 VertexType vertex;顶点数据罐 10 EdgeNode+firestedge:/边表头指针 3男一 0】A }Vertex Node,AdjList[Max VertexNum];I邻接衰类里 顶点表 说明 typedef structf typedef struct node边结点 AdjLis过t adjlist:/邻接表 int ad小vex点序号 intn,e:顶点数和边数 struct node*next指向下一个边铺点 ALGraphi 著有权，则增加一媒 EdgeNode; 87.2.2邻接表 87.2.2邻接表 无向图的邻接表 有向图的邻接表 (化，)eE,则在y的邻接表中有一a1ex=的边表结点。 表结盒，在，的邻接表中有一个时的边 在y,的邻接表中有一aex=1的边表结点。 每边表示了1次，所以共有e个边表结点。 每条边表示了两次，所以一共有2个边表结点 空间复杂度为Om+e),邻接矩阵为0。 此时的边表称为出边表。 出边表中求出度易，求入度难。 稀疏图邻接表节省空间，调密图邻接矩阵为宜。 表的近表给轰：的邻接表中有一个 逆邻接表：EE 此时的边表称为入边表。 入边表中求入度易，求出度难。 3
2014/4/7 3 §7.2.1 邻接矩阵表示法 建立无向图的邻接矩阵表示 step1：输入顶点数、边数 step2：输入顶点表 step3 初始化邻接矩阵 13 ： step4：输入边（及权值） §7.2.2 邻接表 链式存储结构 为每个顶点的邻接关系建立一个单链表，将头结点 放在一个数组中，形成一个顶点表和一个边表。 顶点表结点： 14 边表结点： 边表示： ，因为 和 分别存储在顶点表的ith 和jth分量中，故只需在 的边表中存放序号j即可。 §7.2.2 邻接表 例： 15 说明 typedef struct node{//边表结点 int adjvex；//邻接点序号 struct node * next; //指向下一个边表结点 //若有权，则增加一域 }EdgeNode； §7.2.2 邻接表 typedef struct vnode{//顶点表结点 VertexType vertex；//顶点数据域 EdgeNode * firestedge; //边表头指针 }VertexNode，AdjList[MaxVertexNum]；//邻接表类型 16 typedef struct { AdjList adjlist; //邻接表 int n, e; //顶点数和边数 }ALGraph； §7.2.2 邻接表 无向图的邻接表 , 则在 的邻接表中有一 的边表结点。 在 的邻接表中有一 的边表结点。 每条边表示了两次，所以一共有2e个边表结点。 17 空间复杂度为 ，邻接矩阵为 。 稀疏图邻接表节省空间，稠密图邻接矩阵为宜。 §7.2.2 邻接表 有向图的邻接表 , 在 的邻接表中有一个 的边 表结点。 每边表示了1次，所以共有e个边表结点。 此时的边表称为出边表 18 。 出边表中求出度易，求入度难。 逆邻接表： , 在 的邻接表中有一个 的边表结点。 此时的边表称为入边表。 入边表中求入度易，求出度难
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/47 s7.3.1深度优先遍历(dfs遍历) §7.3.1深度优先遍历(dfs遍历) void DFS(ALGraph*G,imti)【/以v为出发点对G进行ds EdgeNode*p; ●深度优先遍历序列(DFS序列) printf(“%e”,G->adjlistlil.vertex片访问顶点y Visited-TRE:标记y已访问过 遍历过程的顶点访问序列 p-G->adjlist].firstedge;/取y边衰的头指针 G的DFS序列不唯一，但初始源点给定，存储 while(p){依次搜索v的邻接点v if(Visitedlp->adjvex)嗜未访问过，j-p->adjvex 结构给定时所得序列唯一 DFS(G,p->adj小yex):/以y为出发点向纵深搜察 pp->next:考已访问过，或从y出发的d完成，则 找的下一邻接点 以邻接矩阵为存储结构自己写出DS §7.3.1深度优先遍历(df遍历) s7.3.1深度优先遍历(dfs遍历) 四 ●时间 ①对G中每个顶点恰做一次访问（外部+内部调用 源点 dfs),∴.共做n次访问 ②当访问顶点y时，时间主要花费在搜索v的邻接 点上 回（法） 合计：邻接表表示：O(+e),各个边表结点均搜索到 邻接矩阵：O(),各个元素均检索到 ) ds序列：nvLy2vv,〔假设邻接表的边表鸿增有序) §7.3.2广度优先遍历 §7.3.2广度优先遍历 类似于树的层次速历 ●特点 ◆基本思想 尽可能先对横向搜索， 故称之为广度优先搜索(BFS) ①选一顶点v为源点访问之 ②依次访问v的所有邻接点W,w2W ③然后依次访问w(1≤飞)的所有未曾访问过的邻接点 依次类推，直至图中所有和源有路径连通的顶点均已 象波BS Dfs 访问过为止 非递归，用队列作为中间 递归、回潮，用栈保存访 此时，若G是连通图，则遍历完成；否则选G的另一未 数据结构 问过的顶点 访问过的顶点做新源点继续上述授索过程，直至G中所 有顶点均已访问过为止 先访问的顶点其邻接点亦 后访问的顶点其邻接点被先 被先访问(FIFO) 访问(Lo) 5
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/47 87.32广度优先遍历 §7.3.2广度优先遍历 设x和y是两个相继访问的顶点，其邻接点分 ●算法 别记为x1X,和y1y 遍历算法类似于DFSTraverse x在y之前访问，故x,x中未访问顶点亦先 void BFS(ALGraph*G,intk){M似为源 于y1y,中未访问被访问到 InitQueue(&Q少：/队列Q初始化 ∴可用FIFO队列 printf“%e”,G->adjlistk.vertex:/访问潭y ①保存已访问过的顶点顶点入队时对其访问 Visited[kJ-TRUE; ②保存尚未访问过的顶点一顶点出队时对其访问 EnQueue(&Q,k相当于v,入队 第一种方法较好，下面用此方法实现算法 §7.3.2广度优先遍历 §7.3.2广度优先遍历 while (!QueueEmpty(&Q)){ i-DeQueue(&Q:w出队 p-G->adjlisti.firstedge::取y边囊头指针 ●BFS队列 while(p){依次搜索v的邻接点y, if(!Visitedlp->adjvexl)//v未访问过，设p>ad小yexj printf((“%e”,G->adjlist p->adj小vex.vertex)::l/访间y Visited p->adjvex]-TRUE; EnQueue(&Q,p>adjvex:)入队 ●时间 pp>next:在下一边衰结点中找下一个邻接点 每个顶点入队一次，每个边表结点搜索一次 时间与dfs相同 §7.4图的连通性问题 §7.4.1无向图的连通分量和生成树 §7.4.1无向图的连通分量和生成树 ●生成森林：各连通分量的生成树集合 1.求连通分量 ●求生成树和生成森林（使用DFS和BFS) 每外部调用一次DFS或BFS,可求一连通分 ①设G是无向图，v∈V(G)做出发点 量的顶点集 若图连通，则做一次DFS或BFS,必将G中n个 2生成树和生成森林 顶点都访问到，且只做一次访问 ●生成树 两种搜索方法中，从V搜索到y时，须经过边 (WV),故只需添加输出边的操作即可： 连通图G的极小连通子图，但包含G的所有顶点 (支树》，不唯一 n个顶点的连通图的生成树一定有n-1条边 6
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 )，故只需添加输出边的操作即可：
201447 §7.4.1无向图的连通分量和生成树 在dfs和bfs中，均在 while(p){ if(!Visited p->adjvex])f 加入打印：(i,p->adjvex). ds须在递归前加入 } 若G连通则求出的生成树，否则为生成森林 ②若G为有向图，仅当源点为有根图的根时，才能求 得生成树，否则为生成森林 7
2014/4/7 7 §7.4.1 无向图的连通分量和生成树 在dfs和bfs中，均在 while(p) { if( !Visited[p->adjvex] ) { 加入打印：（i，p->adjvex） 37 加入打印 ，p j //dfs须在递归前加入 } 若G连通则求出的生成树，否则为生成森林 ②若G为有向图，仅当源点为有根图的根时，才能求 得生成树，否则为生成森林
