数据结构第七章图

1、17.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的其他运算图的其他运算7.5 7.5 图的应用图的应用第第7 7章章 图图2数据结构数据结构课程的内容课程的内容多对多多对多（m:n)教学重点教学重点（1 1）图的基本术语；）图的基本术语；（2 2）图的各种存储表示；）图的各种存储表示；（3 3）图的两种遍历的思想及算法；）图的两种遍历的思想及算法；（4 4）图的各种应用。）图的各种应用。3 教学难点教学难点（1 1）最小生成树算法；）最小生成树算法；（2 2）最短路径算法；）最短路径算法；（3 3）拓扑排序算法；）拓扑排序算法

2、；457.1 7.1 图的基本术语图的基本术语 其中：其中：V V 是是G G 的顶点集合，是有穷非空集；的顶点集合，是有穷非空集； E E 是是G G 的边集合，是有穷集。的边集合，是有穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。V=vertex E=edge图：记为图：记为 G G( ( V V, , E E ) )v1v2v3v5v4v4v1v2v3v467.1 7.1 图的基本术语图的基本术语有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每条边都是有方向的；

3、中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；v若若 n n 个顶点的无向图有个顶点的无向图有 n n( (n n-1)/2 -1)/2 条边条边, , 称为无向完全图称为无向完全图v若若 n n 个顶点的有向图有个顶点的有向图有n n( (n-n-1) 1) 条边条边, , 称为有向完全图称为有向完全图7例：判断下列例：判断下列4 4种图形各属什么类型？种图形各属什么类型？无向图无向图无向图无向图(树树)有向图有向图有向有向完全图完全图G1G1的顶点集合为的顶点集合为V(G1)=0,1,

4、2,3V(G1)=0,1,2,3边集合为边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)8证明证明证明：若是完全有向图，则证明：若是完全有向图，则n n个顶点中的每个个顶点中的每个顶点都有一条弧指向其它顶点都有一条弧指向其它n-1n-1个顶点个顶点, , 因此总边因此总边数数= =n n( (n n-1)-1)证明：从可以直接推论出无向完全图的边数证明：从可以直接推论出无向完全图的边数因为无方向，两弧合并为一边，所以边数减半，因为无方向，两弧合并为一边，所以边数减半，总边

5、数为总边数为n n( (n n-1)/2-1)/2。 完全有向图有完全有向图有n n( (n n-1)-1)条边条边。123412349设有两个图设有两个图 G G( (V V, , E E) ) 和和 GG( (VV, , EE) )。若若 V V V V 且且 E E E E, , 则称则称 图图G G 是是 图图G G 的子图的子图。子子 图：图：稀疏图：稀疏图：边较少的图。通常边数远少于边较少的图。通常边数远少于稠密图：稠密图：边很多的图。边很多的图。无向图中，边数接近无向图中，边数接近有向图中，边数接近有向图中，边数接近图的基本术语图的基本术语( (续续) )10带权图：带权图：即边

6、上带权的图。其中权是指每条边即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与可以标上具有某种含义的数值（即与边相关的数）。边相关的数）。连通图：连通图：在无向图中在无向图中, , 若从顶点若从顶点v v1 1到顶点到顶点v v2 2有路径有路径, , 则称顶点则称顶点v v1 1与与v v2 2是连通的。如果图中任意一对顶点都是连通是连通的。如果图中任意一对顶点都是连通的的, , 则称此图是连通图。则称此图是连通图。非连通图的极大连通子图叫做连通分量。非连通图的极大连通子图叫做连通分量。带权图带权图网网 络：络：图的基本术语图的基本术语( (续续) )11图的基本术语图的基本术

7、语( (续续) )在有向图中在有向图中, , 若对于每一对顶点若对于每一对顶点v vi i和和v vj j, , 都存在一条都存在一条从从v vi i到到v vj j和从和从v vj j到到v vi i的路径的路径, , 则称此图是强连通图。则称此图是强连通图。强连通图：强连通图：DEABCFJLMGHIK非强连通图非强连通图的极大强连通子图的极大强连通子图叫做强连通叫做强连通分量。分量。12有两类图形不在本章讨论之有两类图形不在本章讨论之列列13生成树：生成树：是一个极小连通子图，它含有图中是一个极小连通子图，它含有图中全部全部n n个顶点，但只有个顶点，但只有n n-1 -1条边。条边。若

8、干棵生成树的集合，含全部顶点，但构成若干棵生成树的集合，含全部顶点，但构成这些树的边或弧是最少的。这些树的边或弧是最少的。图的基本术语图的基本术语( (续续) )v1v2v3v4v如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定构成一个环。v若图中有若图中有n n个顶点，却少于个顶点，却少于n n-1 -1条边，必为非连通图。条边，必为非连通图。生成森林：生成森林：14邻接点：邻接点：有向边有向边( (u u, , v v) )称为弧，边的始点称为弧，边的始点u u 叫弧叫弧尾，终点尾，终点v v 叫弧头。叫弧头。顶点顶点 v v 的入度是以的入度是以 v v 为终点

9、的有向边的条数为终点的有向边的条数, , 记作记作 ID(v); ID(v); 顶点顶点 v v 的出度是以的出度是以 v v 为始点的有向边的条数为始点的有向边的条数, , 记作记作 OD(v)OD(v)。若若 (u, v) (u, v) 是是 E E(G) (G) 中的一条边，则中的一条边，则称称 u u 与与 v v 互为邻接顶点。互为邻接顶点。弧头和弧头和弧尾：弧尾：入度和入度和出度：出度：uv度：度：顶点顶点v v 的度是与它相关联的边的条数。记作的度是与它相关联的边的条数。记作TD(v)TD(v)。在有向图中在有向图中, , 顶点的度等于该顶点的入度与出度之和。顶点的度等于该顶点的

10、入度与出度之和。图的基本术语图的基本术语( (续续) )15树是一种特殊的图树是一种特殊的图答：是树！而且是一答：是树！而且是一棵有向树！棵有向树！问：当有向图中仅问：当有向图中仅1 1个顶点的入度为个顶点的入度为0, 0,其余顶点的入度其余顶点的入度均为均为1 1，此时是何形状？，此时是何形状？16路径：路径：在图在图 G G( (V V, , E E) ) 中中, , 若从顶点若从顶点 v vi i 出发出发, , 沿一些边经过沿一些边经过一些顶一些顶点点 v vp p1 1, , v vp p2 2, , , , v vpmpm，到达顶点到达顶点v vj j。则称顶点序列。则称顶点序列

11、( ( v vi i v vp p1 1 v vp p2 2 . . v vpm pm v vj j ) ) 为从顶点为从顶点v vi i 到顶点到顶点 v vj j 的路径。它经过的边的路径。它经过的边( (v vi i, , v vp p1 1) )、( (v vp p1 1, , v vp p2 2) )、. .、( (v vpmpm, , v vj j) )应当是属于应当是属于E E的边。的边。路径长度：路径长度：非带权图的路径长度是指此路径上边的条数；非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。图的术语（续）

12、图的术语（续）17简单路径：简单路径： 路径上各顶点路径上各顶点 v v1 1,v ,v2 2,.,v,.,vm m 均不互相重复。均不互相重复。回路：回路：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，重合，则称这样的路径为回路或环。则称这样的路径为回路或环。图的术语（续）图的术语（续）18ADT Graph ADT Graph 数据对象数据对象V V：数据关系数据关系 R R：基本操作基本操作P P：ADT Graph ADT Graph 图的抽象数据类型图的抽象数据类型V V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的

13、数据元素的集合，称为顶点集。R=VRR=VR；VR=|v,wV VR=|v,wV 且且 P(v,w), P(v,w), 表示从表示从v v到到w w的弧，的弧， 谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息 CreatGraph CreatGraph ( & &G, V,VR); ; 初始条件：初始条件：V V是图的顶点集，是图的顶点集，VRVR是图中弧的集合。是图中弧的集合。 操作结果：按操作结果：按V V和和VRVR的定义构造图的定义构造图G G。注意：注意：V V 的大小写的大小写含义不同！含义不同！InsertVex InsertVex (

14、& &G, v v); ; 初始条件：图初始条件：图G G存在，存在，v v 和图中顶点有相同特征。和图中顶点有相同特征。 操作结果：在图操作结果：在图G G中添加新顶点。中添加新顶点。 （参见教材（参见教材P156-157P156-157）197.2 7.2 图的存储结构图的存储结构图的特点：图的特点：顺序存储结构：顺序存储结构： 难！难！（多个顶点，无序可言，无法仅以顶点（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）坐标表达相互关系）但可用数组描述元素间关系。但可用数组描述元素间关系。非线性结构（非线性结构（m :nm :n）邻接矩阵邻接矩阵207.2 7.2 图的存

15、储结构图的存储结构一、顺序存储法一、顺序存储法1 1、邻接矩阵邻接矩阵( (数组数组) )表示法表示法各种表示法成立的原则：各种表示法成立的原则：存入电脑后能惟一复原存入电脑后能惟一复原二、链式存储结构：二、链式存储结构：1. 1. 邻接表邻接表( (链式链式) )表示法表示法2. 2. 十字链表十字链表表示法表示法3. 3. 邻接多重表邻接多重表表示法表示法21 建立一个顶点表和一个邻接矩阵。建立一个顶点表和一个邻接矩阵。1. 1. 邻接矩阵（数组）表示法邻接矩阵（数组）表示法 , ),( , ,.否否则则或或者者如如果果01AEjiEjijiEdge记录各个顶点信息记录各个顶点信息表示各个

16、顶点之间关系表示各个顶点之间关系 设图设图 A = (A = (V V, , E E) ) 有有 n n 个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数组组 A A.Edge.Edge n n n n ，定义为：，定义为：22邻接矩阵：邻接矩阵：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v5分析分析1 1：无向图的邻接矩阵是对称的；：无向图的邻接矩阵是对称的；分析分析2 2：顶点顶点i i 的度的度第第 i i 行行 ( (列列) ) 中中1 1 的个数的个数；特别：完全图的邻接矩阵中，对角元素为特别：完全图的邻接矩阵中，对角元素为0 0，其余全

17、，其余全1 1。顶点表：顶点表：无向图的邻接矩阵如何表示？无向图的邻接矩阵如何表示？v1v2v3v5v4v40 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 01. 1. 邻接矩阵（数组）表示法邻接矩阵（数组）表示法23例例2 2 ：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。顶点顶点v vi i的出度的出度= =第第i i行元素之和，行元素之和，OD(OD(v vi i )= )= A.Edg

18、e i j A.Edge i j 顶点顶点v vi i的入度的入度= =第第i i列元素之和。列元素之和。ID(ID(v vi i )= )= A.Edge j i A.Edge j i 顶点的度顶点的度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和, , 即：即：TD( TD( v vi i ) = OD( vi ) + ID( vi ) = OD( vi ) + ID( vi )v1v2v3v4邻接矩阵：邻接矩阵：A.A.EdgeEdge = =( v1 v2( v1 v2 v3 v4 )v3 v4 )v1v1v2v2v3v3v4v40 0 0 00 0 0 0

19、0 0 0 0 0 0 0 0 在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧( (即出度边）；即出度边）； 第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧( (即入度边）。即入度边）。顶点表：顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 24例例3 3 ：有权图（即网络）的邻接矩阵如何表示？：有权图（即网络）的邻接矩阵如何表示？定义：定义：A.Edge i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）v1

20、v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：邻接矩阵： N.Edge =( v1 v2 v3 v4 v5 v6 )顶点表：顶点表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v625 邻接矩阵法优点：邻接矩阵法优点：邻接矩阵法缺点：邻接矩阵法缺点：对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。容易实现图的操作，如：求某顶点的度、判断顶点之间是容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。否有边（弧）、找顶点的邻接点等等。n n个顶点需要个顶点需要个单元存储边

21、个单元存储边( (弧弧); );空间效率为空间效率为O(nO(n ) )。邻接矩阵法优缺点邻接矩阵法优缺点26注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数typedef enum DG, DN, AG, AN GraphKind; /有向有向/ /无向图，有向无向图，有向/ /无向网无向网图的邻接矩阵在机内如何表示？（教材图的邻接矩阵在机内如何表示？（教材P161 P161 重点）重点）typedef struct

22、 ArcCell /弧（边）结点的定义弧（边）结点的定义 VRType adj; /顶点间关系，无权图取顶点间关系，无权图取1 1或或0 0；有权图取权值类型；有权图取权值类型 InfoType *info; /该弧相关信息的指针该弧相关信息的指针ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;typedef struct /图的定义图的定义VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可顶点表，用一维向量即可(n)(n)AdjMatrix arcs; /邻接矩阵邻接矩阵n n* *n nint Ve

23、rnum, arcnum; /顶点总数顶点总数n n，弧（边）总数，弧（边）总数e eGraphKind kind; /图的种类标志图的种类标志Mgraph; 对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n=O(n2 2) )27Status CreateUDN(Mgraph &G) /无向网的构造，用邻接矩阵表示无向网的构造，用邻接矩阵表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /输入总顶点数输入总顶点数n n、总弧数、总弧数e e和信息和信息for(i=0;iG.vexnum,;+i) scanf

24、(&G.vexsi );/输入输入n n个顶点值，存入一维向量个顶点值，存入一维向量例：用邻接矩阵生成无向网的算法（参见教材例：用邻接矩阵生成无向网的算法（参见教材P162P162）for(i=0; iG.vexnum; +i) /对邻接矩阵对邻接矩阵n n* *n n个单元初始化，个单元初始化，adj=,info=NULLfor(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL; 28对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率 = O(n+n= O(n+n2 2+e+e* *n)n)for(k=0;kG.arcnum

25、;+k) /给邻接矩阵有关单元赋初值给邻接矩阵有关单元赋初值( (循环次数弧数循环次数弧数e e scanf(&v1, &v2, &w); /输入弧的两顶点以及对应权值输入弧的两顶点以及对应权值 i=LocateVex(G,v1); j=LocateVex(G,v2); /找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n(n次次) ) G.arcsij.adj=w; /输入对应权值输入对应权值 If(IncInfo) Input(*G.); /如果弧有信息则填入如果弧有信息则填入 G.arcsij = G.arcs j i； /无向网是对称矩阵

26、无向网是对称矩阵 return OK; / Create/ CreateUDN 例：用邻接矩阵生成无向网的算法（参见教材例：用邻接矩阵生成无向网的算法（参见教材P162P162）292. 2. 邻接表（链式）表示法邻接表（链式）表示法 对每个顶点对每个顶点v vi i 建立一个单链表，把与建立一个单链表，把与v vii有关联的边的信息（即有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为度或出度边）链接起来，表中每个结点都设为3 3个域个域: : 每个单链表还应当附设一个头结点（设为每个单链表还应当附设一个头结点（设为2个域），存个域），存vi信息；信息；adjvexinfonext

27、arcdatafirstarc邻接点域，邻接点域，表表示示v vi i 邻接点邻接点的位置的位置链域，链域，指向指向下一个边或下一个边或弧的结点弧的结点数据域，数据域，与与边有关信息边有关信息（如权值）（如权值）数据域，存数据域，存储顶点储顶点vi 信信息息链域，链域，指向指向单链表的第单链表的第一个结点一个结点 每个单链表的头结点另外用顺序存储结构存储。每个单链表的头结点另外用顺序存储结构存储。30例例1 1：无向图的邻接表如何表示？：无向图的邻接表如何表示？v1v2v3v5v4v4邻邻接接表表0123413341420请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。请注意：邻接表不惟

28、一！因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v v1 1邻接点邻接点v v4 4的位置的位置此无权图未开第此无权图未开第3 3分量分量31例例2 2：有向图的邻接表如何表示？：有向图的邻接表如何表示？v1v2v3v4V4V3V2V12301邻接表邻接表( (出边出边) )V4V3V2V13020逆邻接表逆邻接表( (入边入边) )32例例3 3：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！33分析分析1: 1:对于对于n n个顶点个顶点e

29、e条边的无向图，邻接表中除了条边的无向图，邻接表中除了n n个头结点外，个头结点外，只有只有2e2e个表结点个表结点, ,空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(en2 2) )，则比邻接矩阵表示法，则比邻接矩阵表示法O(nO(n2 2) )省空间。省空间。邻接表存储法的特点邻接表存储法的特点它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？怎样计算无向图顶点的度？TD(Vi)TD(Vi)= =单链表中链接的结点个数单链表中链接的结点个数34分析分析2: 2:在有向图中，邻接表中除了在有向图中，邻接表中除了n n个头结点外

30、，只有个头结点外，只有e e个表个表结点结点, ,空间效率为空间效率为O(n+e)O(n+e)。若是稀疏图，则比邻接矩阵表示法。若是稀疏图，则比邻接矩阵表示法合适。合适。怎样计算有向图顶点的出度？怎样计算有向图顶点的出度？ OD(Vi)OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？ I D( Vi ) I D( Vi ) 邻接点为邻接点为ViVi的弧个数的弧个数怎样计算有向图顶点怎样计算有向图顶点ViVi的度：的度： TD(Vi) = OD( Vi ) + I D( Vi )TD(Vi) = OD( Vi ) + I D( Vi

31、 )邻接表存储法的特点：邻接表存储法的特点：35邻接表的缺点：邻接表的缺点：邻接表的优点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。单链表，没有邻接矩阵方便。邻接表存储法的特点邻接表存储法的特点36讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1. 1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。结点个数等于一行中非零

32、元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2), ),而邻接表的空间复杂度为而邻接表的空间复杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)

33、)37图的邻接表在机内如何表示？图的邻接表在机内如何表示？ （参见教材（参见教材P163P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数空间效率为空间效率为O(n+2e)O(n+2e)或或O(n+e)O(n+e)时间效率为时间效率为O(n+eO(n+e* *n)n)typedef struct VNode /顶点结构顶点结构 VertexType data; /顶点信息顶点信息 ArcNode * firstarc; /指向依附该顶点的第一条弧的指针指向依附该顶点的第一条弧的指针VNode, AdjList MAX_VERTEX_NUM ; ty

34、pedef struct /图结构图结构 AdjList vertics ; /应包含邻接表应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph; typedef struct ArcNode /弧结构弧结构 int adjvex; /该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针该弧相关信息的指针 ArcNode；图的邻

35、接表图的邻接表生成算法作生成算法作为自测题为自测题387.3 7.3 图的遍历（图的遍历（2 2课时）课时）遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的基本运算。图的基本运算。遍历实质：找每个顶点的邻接点的过程。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回顶点相通，在访问完某个顶点

36、之后可能会沿着某些边又回到了曾经访问过的顶点到了曾经访问过的顶点39怎样避免重复访问？怎样避免重复访问？解决思路：解决思路：可设置一个可设置一个辅助数组辅助数组 visitedvisited n n ，用来标记每个被访，用来标记每个被访问过的顶点。它的初始状态为问过的顶点。它的初始状态为0 0，在图的遍历过程中，一，在图的遍历过程中，一旦某一个顶点旦某一个顶点i i 被访问，就立即改被访问，就立即改 visitedvisited i i 为为1 1，防止它被，防止它被多次访问。多次访问。7.3 7.3 图的遍历图的遍历40图常用的遍历图常用的遍历一、一、深度优先搜索深度优先搜索二、二、广度优先

37、搜索广度优先搜索 41一、深度优先搜索一、深度优先搜索( ( DFSDFS ) )基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。Depth_First Searchv1v2v3v8v7v6v4v5起点起点起点起点遍历步骤遍历步骤应退回到应退回到V8V8，因为，因为V2V2已有标记已有标记42深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：简单归纳简单归纳：1. 1. 访问起始点访问起始点 v; v;2. 2. 若若v v的第的第1 1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；3. 3. 若当前邻接点已访问过，再找若当前邻接点已访问过，再找v v的

38、第的第2 2个邻接点重新个邻接点重新遍历。遍历。43深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点 v v 后，由后，由 v v 出发，访问它的任一出发，访问它的任一邻接顶点邻接顶点 w w1 1；E再从再从 w w1 1 出发，访问与出发，访问与 w w1 1邻接但还未被访问过的顶点邻接但还未被访问过的顶点 w w2 2；E然后再从然后再从 w w2 2 出发，进行类似的访问，出发，进行类似的访问， E如此进行下去，直至到达所有的邻接顶点都被访问过的顶如此进行下去，直至到达所有的邻接顶点都被访问过的顶点点 u u 为止。

39、为止。E接着，退回一步，退到前一次刚访问过的顶点，看是否还接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点。有其它未被访问的邻接顶点。 如果有，则访问此顶点，之后再从此顶点出发，进行与前如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；述类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。连通图中所有顶点都被访问过为止。441234561000000000000300000040000005000000600000000000012345601000010000

40、1000010101邻邻接接矩矩阵阵A辅助数组辅助数组 visited n 起点起点开辅助数组开辅助数组 visited n ！例：例：12345610000000300004000050000600000请注意逐级回退是递归概念请注意逐级回退是递归概念45for( j=1; jlink) /while(p-link) /当存在起点的第一个邻接点时当存在起点的第一个邻接点时 p=p-link; p=p-link; v=p-data; v=p-data; if(!visitedv) DFS(List,v,p); / if(!visitedv) DFS(List,v,p); /进行递归进行递归 r

41、eturn; return; 邻接表非递归深度遍历算法邻接表非递归深度遍历算法4849DFS DFS 算法效率分析算法效率分析（设图中有（设图中有 n n 个顶点，个顶点，e e 条边）条边）n如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为扫描该顶点所在行，因此遍历全部顶点所需的时间为O(O(n n2 2) )。n如果用邻接表来表示图，虽然有如果用邻接表来表示图，虽然有 2 2e e 个表结点，但只需扫描个表结点，但只需扫描 e e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n

42、n个头结点的时间，因此个头结点的时间，因此遍历图的时间复杂度为遍历图的时间复杂度为O(O(n n+ +e e) )。DFS DFS 算法效率分析算法效率分析结结 论：论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。5051二、广度优先搜索二、广度优先搜索( ( BFSBFS ) )基本思想：基本思想：仿树的层次遍历过程仿树的层次遍历过程。Breadth_First Searchv1v2v3v8v7v6v4v5起点起点遍历步骤遍历步骤起点起点52广度优先搜索（遍历）步骤：广度优先搜索（遍历）步骤：简单

43、归纳：简单归纳：在访问了起始点在访问了起始点v v之后，依次访问之后，依次访问 v v的邻接点；的邻接点；然后再依次（顺序）访问这些点（下一层）中未被访然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；问过的邻接点；直到所有顶点都被访问过为止。直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一步可广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，因此，广度优先搜索不是一个递归的过程广度优先搜索不是一个递归的过程，其算法也不，其算法也不是递归的。是递归的。53讨

44、论讨论1 1：计算机如何实现：计算机如何实现BFSBFS？邻接表邻接表宽度优先搜索要借助队列！宽度优先搜索要借助队列！例：例：起点起点辅助队列辅助队列 visited n 仍需要仍需要v2已访问过了已访问过了V2入队入队54while(rear!=front) /队不空时队不空时 front=(front+1)%n; v=qfront; /访问过的顶点出队访问过的顶点出队 p=Listv.firstarc; /P/P指向第指向第1 1个邻接点个邻接点 while(!p) if(! Visitedadjvex(p) )/未到表尾，且邻接域未访问过，未到表尾，且邻接域未访问过， Visit(adj

45、vex(p); Visitedadjvex(p)=1;/则先输出再改标记，则先输出再改标记， rear=(rear+1)%n; qrear= adjvex(p) /最后再入队最后再入队 p=nextarc(p); /指向单链表中下一个邻接点指向单链表中下一个邻接点 return / BFS1/ BFS1讨论讨论2 2： BFSBFS算法如何编程？算法如何编程？BFS1(List, n, v) BFS1(List, n, v) /List/List为邻接表，为邻接表，v v为起点，为起点，qnqn为辅助队列为辅助队列 Visit(v); Visitedv=1; Visit(v); Visited

46、v=1; /访问（例如打印）顶点访问（例如打印）顶点v v并修改标志并修改标志 层次遍历应当用队列！层次遍历应当用队列！（教材上（教材上BFSBFS算法见算法见P170P170）front=n-1;rear=0; /队列指针初始化队列指针初始化qrear=v; /起始点入队起始点入队55BFS BFS 算法效率分析算法效率分析 空间复杂度相同，都是空间复杂度相同，都是O(n)(O(n)(借用堆栈或队列装借用堆栈或队列装n n个顶点）；个顶点）； 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。搜索路径无关。 如果使用邻接表来

47、表示图，则如果使用邻接表来表示图，则BFSBFS循环的总时间代价为循环的总时间代价为 d d0 0 + d + d1 1 + + d+ + dn n-1 -1 = O( = O(e e) )，其中的，其中的 d di i 是顶点是顶点 i i 的度。的度。 如果使用邻接矩阵，则如果使用邻接矩阵，则BFSBFS对于每一个被访问到的顶点，都要对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（循环检测矩阵中的整整一行（ n n 个元素），总的时间代价为个元素），总的时间代价为O(O(n n2 2) )。（）567.4 7.4 图的连通性问题图的连通性问题1. 求图的生成求图的生成树树2. 求最

48、小生成树求最小生成树 571.1.求图的生成树（或生成森林）求图的生成树（或生成森林）生成树：是一个极小连通子图，它含有图中全部顶点，生成树：是一个极小连通子图，它含有图中全部顶点，但只有但只有n-1n-1条边。条边。生成森林：由若干棵生成树组成，含全部顶点，但构生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。成这些树的边是最少的。1. 1.求图的生成树（或生成森林）求图的生成树（或生成森林）思考思考1 1：若对连通图进行遍历，得到的是什么？：若对连通图进行遍历，得到的是什么？ 得到的将是一个极小连通子图，即图的生成树！得到的将是一个极小连通子图，即图的生成树！ 由深度优先

49、搜索得到的生成树，称为深度优先搜索由深度优先搜索得到的生成树，称为深度优先搜索 生成树。生成树。 由广度优先搜索得到的生成树，称为广度优先搜索由广度优先搜索得到的生成树，称为广度优先搜索 生成树。生成树。思考思考2 2：若对非连通图进行遍历，得到的是什么？：若对非连通图进行遍历，得到的是什么？ 得到的将是各连通分量的生成树，即图的生成森林！得到的将是各连通分量的生成树，即图的生成森林！58591. 1. 求图的生成树求图的生成树生成树的特征生成树的特征n n 个顶点的连通网络的生成个顶点的连通网络的生成树有树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。求生成树的方法求生成树的方法D

50、FSDFS（深度优先搜索）和（深度优先搜索）和BFSBFS（广度优先搜索）（广度优先搜索）60例例1 1 ：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFSBFS生生成成树树v0v1v3v2v4无向连通图无向连通图61其实由邻接矩阵或邻接表其实由邻接矩阵或邻接表也能直接画出生成森林也能直接画出生成森林DEABCFJLMGHIK例例2 2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）求解步骤：求解步骤：Step1:Step1:先求出邻接矩阵或邻接表；

51、先求出邻接矩阵或邻接表；Step2:Step2:写出写出DFSDFS或或BFSBFS结果序列；结果序列；Step3:Step3:画出对应子图或生成森林。画出对应子图或生成森林。这是一个无向非连通图这是一个无向非连通图（参见教材（参见教材P170-171P170-171例）例）下面选用邻接表方式来求深度优先搜索生成森林下面选用邻接表方式来求深度优先搜索生成森林生成森林的定义（对有向或无向图均生成森林的定义（对有向或无向图均适用）：是若干棵生成树的集合，含适用）：是若干棵生成树的集合，含全部顶点，但构成这些树的边或弧是全部顶点，但构成这些树的边或弧是最少的。最少的。62 解题步骤解题步骤1、先写出

52、邻接表（或邻接矩阵）、先写出邻接表（或邻接矩阵）2、再写出、再写出DFS结果结果ABMJLCF DE GHKI3、画出对应子图或生成森林。、画出对应子图或生成森林。63115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子图子图1：ABCFJLM子图子图2：子图子图3：最小连通！最小连通！例例2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）64DEGHIK子图子图(或连通分量或连通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林例例2 2

53、：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）65讨论：如何求得最小生成树？讨论：如何求得最小生成树？最小生成树（最小生成树（MSTMST）的）的 性质如下：性质如下：若若U U集是集是V V的一个非空子集，若的一个非空子集，若(u (u0 0, v, v0 0) )是一条最小权值的边，是一条最小权值的边，其中其中u u0 0 U U，v v0 0 V-UV-U；则：；则：(u (u0 0, v, v0 0) )必在最小生成树上。必在最小生成树上。 设想一下：先把权值最小的边归入生成设想一下：先把权值最小的边归入生成树内，逐个递增，舍去回路边，则得到树内，逐个递增

54、，舍去回路边，则得到的很可能就是最小生成树！的很可能就是最小生成树！2. 2. 求求最小生成树最小生成树662. 2. 求最小生成树求最小生成树首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的连通网络的生成树肯定有个顶点的连通网络的生成树肯定有 n n 个顶点和仅仅个顶点和仅仅n-n-1 1 条边。条边。即有权图即有权图目标：在网络的多个生成树中，寻找一个各边权值之和目标：在网络的多个生成树中，寻

55、找一个各边权值之和最小的生成树。最小的生成树。 2. 2. 求最小生成树求最小生成树构造最小生成树的准则构造最小生成树的准则v必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1 -1条边来联结网络中的条边来联结网络中的n n个顶个顶点；点；v不能使用产生回路的边。不能使用产生回路的边。6768欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条线路；但因为条线路；但因为每条线路都会有对应的经济成本，而每条线路都会有对应的经济成本，而n n个城市可能有个城市可能有n(n-1)/

56、2 n(n-1)/2 条线路，那么，如何选择条线路，那么，如何选择n1n1条线路使总费用最少？条线路使总费用最少？典型用途：典型用途：69典型用途：典型用途：先建立数学模型：先建立数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n1n1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间的通信网。个城市间的通信网。显然此连通网显然此连通网是一棵生成树！是一棵生成树！问题抽象：问题抽象： n n个顶点的生成树很多，需要从中选一棵代价最小个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此

57、树便称为最小生的生成树，即该树各边的代价之和最小。此树便称为最小生成树成树MSTMST。Minimum cost Spanning Tree702. 2. 求最小生成树求最小生成树目标：在网的多个生成树中，寻找一个各边权值之和最目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树。小的生成树。应用：应用： n n个城市建网，如何选择个城市建网，如何选择n1n1条线路，使总费用最少？条线路，使总费用最少？vKruskalKruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法vPrimPrim（普里姆普里姆）算法）算法 算法：算法：归并边归并边归并顶点归并顶点71KruskalKruskal（克鲁

58、斯卡尔）算法（克鲁斯卡尔）算法例例 ：72计算机内怎样实现计算机内怎样实现KruskalKruskal算法？算法？ 特点特点：将边归并：将边归并适于求适于求稀疏网稀疏网的最小生成树。的最小生成树。 故采用邻接表作为图的存储表示。故采用邻接表作为图的存储表示。73（1 1）初始状态：）初始状态： U =uU =u0 0 , ,（ u u0 0 V V ），）， TE= ,TE= ,（2 2）从）从E E中选择顶点分别属于中选择顶点分别属于U U、V-UV-U两个集合、且权值最小两个集合、且权值最小的边（的边（ u u0 0, v, v0 0) )，将顶点将顶点v v0 0归并到集合归并到集合U

59、U中，边（中，边（u u0 0, v, v0 0) )归归并到并到TETE中中；（3 3）直到）直到U=VU=V为止。此时为止。此时TETE中必有中必有n-1n-1条边，条边， T T（V V，TETE）就是最小生成树。）就是最小生成树。设：设：N =N =（V , EV , E）是个连通网，）是个连通网，另设另设U U为最小生成树的顶点集，为最小生成树的顶点集，TETE为最小生成树的边集。为最小生成树的边集。构造步骤构造步骤: :普利姆（普利姆（PrimPrim）算法）算法( (重点、考点）重点、考点）74例：用例：用PRIMPRIM算法实现最小生成树算法实现最小生成树 注注 ：在最小生成树

60、的生成过程中，所选的边都是：在最小生成树的生成过程中，所选的边都是 一端在一端在V-UV-U中，另一端在中，另一端在U U中。中。75 增设一辅助数组增设一辅助数组Closedge n Closedge n ， 每个数组分量都有两个域：每个数组分量都有两个域：要求：使要求：使Colsedge i.lowcost = min( ( u ,vi ) ) u U 计算机内怎样实现计算机内怎样实现PrimPrim（普里姆）算法？（普里姆）算法？ PrimePrime算法特点算法特点: : 将顶点归并，与边数无关，适于稠密网。将顶点归并，与边数无关，适于稠密网。 故采用邻接矩阵作为图的存储表示。故采用邻接矩阵作为图的存储表示。v vi i 在在U U中的邻点中的邻点u uColsedge