71图的定义和术语课件.ppt

1、第七章第七章 图图v图图(Graph)由一个由一个顶点集顶点集V V和一个和一个边集边集E E构成的数构成的数据结构。据结构。Graph=(V,E)其中，其中，V V=x x|x x 某个数据对象某个数据对象 是非空有限的顶点集合；是非空有限的顶点集合；E E=(=(x x,y y)|)|x x,y y V V 或或 E E=y|x x,y y V V&PathPath(x x,y y)是有限的顶点之间关系的集合，是有限的顶点之间关系的集合，(x,y)x,y)也叫做也叫做边边(edge)edge)集集合合,它是无方向的它是无方向的;PathPath(x x,y y)表示从表示从 x x 到到

2、y y 的一条单向的一条单向通路通路,它是有方向的它是有方向的,所以所以 x,y也叫做也叫做弧弧(arc)arc)的集合的集合,x x称称为弧尾或始点为弧尾或始点,y y称为弧头或终点称为弧头或终点.v有向图有向图有向图有向图G G是由两个集合是由两个集合V(G)V(G)和和E(G)E(G)组成的组成的其中：其中：V(G)V(G)是顶点的非空有限集是顶点的非空有限集 E(G)E(G)是有向边（也称是有向边（也称弧弧）的有限集合，弧是顶点的）的有限集合，弧是顶点的有序对，记为有序对，记为 v,w，v,wv,w是顶点，是顶点，v v为弧尾，为弧尾，w w为弧头为弧头v无向图无向图无向图无向图G G

3、是由两个集合是由两个集合V(G)V(G)和和E(G)E(G)组成的组成的 其中：其中：V(G)V(G)是顶点的非空有限集是顶点的非空有限集 E(G)E(G)是边的有限集合，边是顶点的无序对，是边的有限集合，边是顶点的无序对，记为（记为（v,wv,w）或（或（w,v)w,v)，并且（并且（v,w)=(w,v)v,w)=(w,v)例例7.1245136G1图图G1中：中：V(G1)=1,2,3,4,5,6 E(G1)=,例例7.2157324G26图图G2中：中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)v

4、无向完全图无向完全图(Completed graph)n个顶点的无向图有个顶点的无向图有n(n-1)/2条边（条边（最大边数是最大边数是n(n-1)/2）v有向完全图有向完全图n个顶点的有向图，有个顶点的有向图，有n(n-1)条边（条边（最最大边数是大边数是n(n-1)）v稀疏图稀疏图(sparse graph)sparse graph)：边或弧很少的图边或弧很少的图,通常边数通常边数 nlognlog2 2n nv稠密图稠密图(Dense graph)Dense graph)无向图中，边数接近无向图中，边数接近有向图中，边数接近有向图中，边数接近有向完全图有向完全图无向图无向图(树树)有向图

5、有向图完全图完全图无向无向 完全图完全图v权权与图的边或弧相关的数与图的边或弧相关的数v网网带权的带权的有向有向图叫有向网，带权的无向图图叫有向网，带权的无向图叫无向网叫无向网v子图子图如果图如果图G(V,E)和图和图G(V,E),满足：满足：V V，E E 则称则称G为为G的子图的子图关联关联v顶点的度（于树的度不同）顶点的度（于树的度不同）无向图中，顶点的度为与每个顶点相连的边数无向图中，顶点的度为与每个顶点相连的边数,记记作作TD(v)有向图中，顶点的度分成入度与出度有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目入度：以该顶点为头的弧的数目,记为记为ID(v)出度：以该顶点

6、为尾的弧的数目出度：以该顶点为尾的弧的数目,记为记为OD(v)一个顶点的度数等于该顶点的入度与出度之和一个顶点的度数等于该顶点的入度与出度之和,即即TD(v)=OD(v)+ID(v)niivTDe1)(21v路径路径路径是顶点的序列路径是顶点的序列V=Vi0,Vi1,V=Vi0,Vi1,VinVin，满足满足(V Vij-1ij-1,V,Vijij)E E 或或 E,(1jE,(1j n)n)v路径长度路径长度沿路径边的数目或沿路径各边权值之沿路径边的数目或沿路径各边权值之和和v简单路径简单路径序列中顶点不重复出现的路径序列中顶点不重复出现的路径v回路回路(环环)第一个顶点和最后一个顶点相同的

7、路第一个顶点和最后一个顶点相同的路径径v简单回路简单回路(简单环简单环)除了第一个顶点和最后一个除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路顶点外，其余顶点不重复出现的回路V0V1V3V2V0V1V3V2V0V1V2V0V1V3V0ABCDEHMFGIJLK无向图无向图G的三个连通分量的三个连通分量ABCDEFGIJLHMK无向图无向图G强连通图强连通图 有向图有向图G 有向图有向图G的两的两个个 强强连通分量连通分量12431234v生成树生成树：ABCDEHMABCDEHM无向图无向图G 无向图无向图G的生成树的生成树 v生成森林生成森林：有向图有向图G的生成森林的生成森林有向

8、图有向图G本章只讨论本章只讨论简单图简单图,有两类图形不在本章讨论之列：有两类图形不在本章讨论之列：ADT Graph 数据对象数据对象V：v v是具有相同特性的数据元素的集合，称为是具有相同特性的数据元素的集合，称为顶点集。顶点集。数据关系数据关系 R R：R=VRR=VR；VR=VR=|v,wV|v,wV 且且 P(v,w)P(v,w),表示从表示从v v到到w w的弧，的弧，谓词谓词P(v,w)P(v,w)定义了弧定义了弧 v,w的意义或信息的意义或信息 基本操作基本操作P P：CreatGraph(&G,V,VR)/按定义按定义(V,VR)构造图构造图DestroyGraph(&G):

9、/销毁图基本操作基本操作LocateVex(G,u);/若若G中存在顶点中存在顶点u，则返回该顶点在则返回该顶点在 图中图中“位置位置”；否则返回其它信息。否则返回其它信息。GetVex(G,v);/返回返回 v 的值。的值。PutVex(&G,v,value);/对对 v 赋值赋值value。FirstAdjVex(G,v);/返回返回 v 的的“第一个邻接点第一个邻接点”。若该顶点。若该顶点/在在 G 中没有邻接点，则返回中没有邻接点，则返回“空空”。NextAdjVex(G,v,w);/返回返回 v 的（相对于的（相对于 w 的）的）“下一个邻接下一个邻接 点点”。若。若 w 是是 v

10、的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。基本操作基本操作InsertArc(&G,v,w);/在在G中增添弧中增添弧，若若G是无向的，是无向的，/则还增添对称弧则还增添对称弧。DeleteArc(&G,v,w);/在在G中删除弧中删除弧，若若G是无向的，是无向的，/则还删除对称弧则还删除对称弧。DeleteVex(&G,v);/删除删除G中顶点中顶点v及其相关的弧。及其相关的弧。InsertVex(&G,v);/在图在图G中增添新顶点中增添新顶点v。基本操作基本操作DFSTraverse(G,v,Visit()/从顶点从顶点v v起深度优先遍历图起深度优先遍历图G G，并对每

11、个顶点调并对每个顶点调用函数用函数VisitVisit一次且仅一次一次且仅一次。BFSTraverse(G,v,Visit()/从顶点从顶点v v起广度优先遍历图起广度优先遍历图G G，并对每个顶点并对每个顶点调用函数调用函数VisitVisit一次且仅一次。一次且仅一次。图的四种常用的存储形式：图的四种常用的存储形式：邻接矩阵和加权邻接矩阵邻接矩阵和加权邻接矩阵（labeled adjacency matrix）邻接表邻接表十字链表十字链表邻接多重表邻接多重表一、一、(加权加权)邻接矩阵（邻接矩阵（labeled adjacency matrix）,0),(,1 .G否则否则或者或者如果如果

12、EjiEjijiarcs0101101101011110.1arcsG无向图无向图G10001000100100100000001010.2arcsG有向图有向图G2 一、一、(加权加权)邻接矩阵（邻接矩阵（continue）一、一、(加权加权)邻接矩阵（邻接矩阵（continue）njijiavID1)(njijiavOD1)(定义为：定义为：G.arcs i j=Wij 或（或（vi,vj）VR 无边（弧）无边（弧）以有向网为例：以有向网为例：邻接矩阵：N.Edge=(v1 v2 v3 v4 v5 v6 )顶点表：5v1v2v3v4v5v6489755613N 5 7 4 8 9 5 6

13、5 3 1 一、一、(加权加权)邻接矩阵（邻接矩阵（continue）容易实现图的操作，如：求某顶点的容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。接点等等。n n个顶点需要个顶点需要n n*n n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O(nO(n2 2)。对稀疏图而言尤其浪费空间对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：一、一、(加权加权)邻接矩阵（邻接矩阵（continue）#define INFINITY INT_MAX#define MAX

14、_VERTEX_NUM 20typedef enumDG,DN,UDG,UDN GraghKind;typedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。是顶点关系类型。/对无权图，用对无权图，用1或或0表示相邻否表示相邻否；/对带权图，则为权值类型。对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义图的定义 VertexType vexsMAX_VERTE

15、X_NUM;/顶点顶点信息信息 AdjMatrix arcs;/弧的信息弧的信息 int vexnum,arcnum;/顶点数，弧数顶点数，弧数 GraphKind kind;/图的种类标志图的种类标志 MGraph;Status CreateUDN(Mgraph&G)/用邻接矩阵表示用邻接矩阵表示return OK;例：用邻接矩阵生成无向网的算法例：用邻接矩阵生成无向网的算法（参见教材（参见教材P162）scanf(&G.vexnum,&G.arcnum,&IncInfo);/输入总顶输入总顶点数，总弧数和信息点数，总弧数和信息for(i=0;iG.vexnum,;+i)scanf(&G.v

16、exsi);/输入顶输入顶点值，存入一维向量中点值，存入一维向量中for(i=0;iG.vexnum;+i)/对邻接矩阵对邻接矩阵n n*n n个单元初个单元初始化，始化，adj=,info=NULL for(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;for(k=0;kG.arcnum;+k)/给弧赋初值给弧赋初值(循环次数循环次数弧数弧数)scanf(&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);/找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n n次次)G.arcsij.adj=w;/输入对应权值输

17、入对应权值 If(IncInfo)Input(*G.arcsij.info);G.arcsji=G.arcs i j；/无向网是对称矩阵无向网是对称矩阵 对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率=O(nO(n2 2+n+e+n+e*n)n)int firstAdjVex(Mgraph G,int v)/返回顶点返回顶点v的第一个邻接点，的第一个邻接点，G为无向图为无向图 for(k=0;k0 )break;if(k=G.vexnum)k=-1;/无邻接点无邻接点return k;/end firstAdjVex()图的部分操作在邻接矩阵上的实现图的部分操作在

18、邻接矩阵上的实现、0123413341420注：邻接表不唯一，因各个边结点的链入顺序是任意的。注：邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v1v2v3v5v4v4data:结点的数据域，保存结点的数据值。结点的数据域，保存结点的数据值。firstarc:结点的指针域，给出自该结点出发的的第一条边结点的指针域，给出自该结点出发的的第一条边 的边结点的地址。的边结点的地址。头结点头结点:datafirstarcadjvexnextarc表结点表结点:adjvex:该边或弧所指向的顶点的位置该边或弧所指向的顶点的位置.nextarc:指向下一条边或弧的指针指向下

19、一条边或弧的指针.、adjvexnextarcdatafirstarc、0123413341420v1v2v3v4v5231420v1v2v3v5v4v4v1v2v3v4V4V3V2V12301V4V3V2V13020邻接表邻接表(出边出边)逆邻接表逆邻接表(入边入边)01230123用用邻接表表示有向图时邻接表表示有向图时，若不考虑逆邻接表，只需，若不考虑逆邻接表，只需 n n 个顶点结点，个顶点结点，e e 个边结点。个边结点。带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 costcost/边结点定义边结点定义typedef struct ArcNode int adj

20、vex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;adjvex info nextarc/头结点定义头结点定义typedef struct VNode VertexType data;/顶点信息顶点信息 ArcNode *firstarc;/指向第一条依附该顶指向第一条依附该顶点的弧点的弧 VNode,AdjListMAX_VERTEX_NUM;data firstArc/图的定义图的定义typedef struct

21、 AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志图的种类标志 ALGraph;int firstAdjVex(ALGraph ghead,int v)return gheadv-firstArc.adjvex;/end firstAdjVex()int nextAdjVex(ALGraph ghead,int v,int w)p=gheadv-firstArc;while(p&p-adjvex!=w)p=p-next;if(!p)return 0;else return p-next-adjvex;/end nextAdjVex()找某顶

22、点的所有邻接点的时间复杂度是找某顶点的所有邻接点的时间复杂度是O(e)如何建立邻接表（以有向图为例）如何建立邻接表（以有向图为例）算法思想：算法思想：首先将邻接表表头数组初始化，首先将邻接表表头数组初始化，vertexvertex域初始域初始化为化为i i，firstarcfirstarc初始化为初始化为NULLNULL；然后对读入的每一条弧然后对读入的每一条弧 i,j，产生一个表结产生一个表结点，点，adjveradjver域置为域置为j j，并将结点链接到邻接表的并将结点链接到邻接表的第第i i个链表中。个链表中。算法如下：算法如下：Void GreatAdjList(ALGraph&G)

23、ArcNode *p;sacnf(“%d%d”,&n,&e);G.vexnum=n;G.arcnum=e;for(i=0;in;i+)G.verticesi.vertex=i;G.verticesi.firstarc=NULL;for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;/GreatAdjList讨论：邻接表与邻接矩阵的比较讨论：邻接表与邻接矩阵的比较1.1.联系：联系：都可以用来存储有向图和无向图；邻接表中都可以用来存储有向图和无向图；邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个每个链

24、表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。数等于一行中非零元素的个数。2.2.区别：区别：邻接矩阵是顺序结构，邻接表是链式结构邻接矩阵是顺序结构，邻接表是链式结构对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂而邻接表的空间复杂度为度为O(n+e)O(n+e)。邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e

25、接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)三、三、邻接多重表邻接多重表(无向图无向图的一种存储结构的一种存储结构)在在无向图无向图的邻接表中的邻接表中,一条边出现两个单链表中一条边出现两个单链表中.浪费浪费空间，也给某种操作带来了困难。空间，也给某种操作带来了困难。在邻接多重表中，每一条边只有一个结点在邻接多重表中，每一条边只有一个结点(称边结点称边结点)为有关边的处理提供了方便。为有关边的处理提供了方便。mark ivex jvex ilink jlinkEbox:三、三、邻接多重表邻接多重表(无向图无向图的一种存储

26、结构的一种存储结构)顶点结点的结构顶点结点的结构:其中其中:data 存放与该顶点相关的信息存放与该顶点相关的信息;Firstarc 是指示第一条依附于该顶点的边的指针。是指示第一条依附于该顶点的边的指针。存储顶点信息的结点表以顺序表方式组织存储顶点信息的结点表以顺序表方式组织.在邻在邻接多重表中接多重表中,所有依附于同一个顶点的边都链接所有依附于同一个顶点的边都链接在同一个单链表中。从顶点在同一个单链表中。从顶点 i i 出发出发,可以循链找到可以循链找到所有依附于该顶点的边，也可以找到它的所有邻所有依附于该顶点的边，也可以找到它的所有邻接顶点。接顶点。data FirstarcVexBox

27、:三、三、邻接多重表邻接多重表(无向图无向图的一种存储结构的一种存储结构)例例aecbd0123acdb4e 0 1 0 3 2 3 2 1 2 4 4 1三、三、邻接多重表邻接多重表(无向图无向图的一种存储结构的一种存储结构)v可以把十字链表看成是将有向图的邻接表和逆可以把十字链表看成是将有向图的邻接表和逆邻接表这两个表结合起来而得到的一种链表。邻接表这两个表结合起来而得到的一种链表。v在十字链表中在十字链表中,有向图中每一条弧对应一个结点有向图中每一条弧对应一个结点(称称弧结点弧结点)v每一个顶点也对应一个结点每一个顶点也对应一个结点(称顶点结点称顶点结点)。其中其中:tailvex表示该

28、弧的弧尾顶点在图中的位置；表示该弧的弧尾顶点在图中的位置；headvex表示该弧的弧头顶点在图中的位置；表示该弧的弧头顶点在图中的位置；hlink指向指向弧头弧头相同的下一条弧的指针；相同的下一条弧的指针；tlink指向指向弧尾弧尾相同的下一条边的指针。相同的下一条边的指针。需要时还可有权值域需要时还可有权值域cost tailvex headvex hlink tlinkArcBox:data Firstin FirstoutVexNode:其中其中:数据域数据域data存放与该顶点相关的信息，存放与该顶点相关的信息，指针域指针域Firstin指向以该顶点为指向以该顶点为弧头弧头的第一条弧；

29、的第一条弧；指针域指针域Firstout指向以该顶点为指向以该顶点为弧尾弧尾的第一条弧。的第一条弧。例例bdacab cd0123 0 2 0 1 2 3 2 0 3 2 3 1 3 0#define MAX_VERTEX_NUM 20Typedef struct ArcBox /弧结点结构弧结点结构 int tailvex,headvex;struct ArcBox*hlink,tlink;InfoType *info;ArcBox；Typedef struct VexNode /顶点结构顶点结构 VertexType data;ArcBox *firstin,*firstout;VexNo

30、de;Typedef struct VexNode xlist MAX_VERTEX_NUM;/表头向量表头向量 int vexnum,arcnum;OLGraph;/图结构图结构q从已给的连通图中某一顶点出发，沿着一些边访问图从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历(Graph Traversal)。u深度优先遍历深度优先遍历u广度优先遍历广度优先遍历q图的两种遍历方法图的两种遍历方法图中可能存在回路，在访问完某个顶点之后图中可能存在回路，在访问完某个顶点之后可能会沿着某些边又回

31、到了曾经访问过的顶点可能会沿着某些边又回到了曾经访问过的顶点为了避免重复访问，可设置一个标志顶点是为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组否被访问过的辅助数组 visited ，它的初始它的初始状态为状态为 0 0，在图的遍历过程中，一旦某一个顶，在图的遍历过程中，一旦某一个顶点点 i i 被访问，就立即让被访问，就立即让 visited i 为为 1 1，防止，防止它被多次访问。它被多次访问。DFS算法思想：算法思想：深度优先搜索深度优先搜索从图中某个顶点从图中某个顶点V V0 0 出发，访问此顶点，然后出发，访问此顶点，然后依次从依次从V V0 0的各个未被访问的邻接点出

32、发深度优先搜索遍历图的各个未被访问的邻接点出发深度优先搜索遍历图，直至直至V V0 0 的所有邻接点都被访问到。的所有邻接点都被访问到。若此时图中尚有顶点未被访问若此时图中尚有顶点未被访问,则另选图中一个未则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。中所有顶点都被访问到为止。深度优先搜索的示例深度优先搜索的示例深度优先遍历生成树深度优先遍历生成树图的深度优先遍历算法图的深度优先遍历算法void dfsTraverse()for(v=1;v=n;v+)visitedv=false;for(v=1;v=n;v+)

33、if(!visitedv)dfs(v);void dfs(int v)visitedv=1;for(w=firstAdjVex(v);w;w=nextAdjVex(v,w)if(!visitedw)dfs(w);/使用使用ADT在递归函数中增加一计数器在递归函数中增加一计数器sum，初值为初值为n，每访问每访问一次就减一次就减1,减到减到0则则return，可避免递归时间过长。可避免递归时间过长。在邻接矩阵在邻接矩阵A A上实现上实现 void dfs(int v)visitedv=true;for(w=1;w0)if(!visitedw)dfs(w);/图的深度优先遍历算法图的深度优先遍历算

34、法在邻接链表上实现在邻接链表上实现 void dfs(int v)visitedv=true;p=gheadv-firstArc;while(p)w=p-adjvex;if(!visitedw)dfs(w);p=p-next;同学们自己考虑非递归实现算法同学们自己考虑非递归实现算法图的深度优先遍历算法图的深度优先遍历算法Dfs1(Graph g,int v)/利用栈实现非递归算法利用栈实现非递归算法 /第一个顶点入栈并访问第一个顶点入栈并访问 Visit(v);visitv=1;push(s,v);/当栈不空时做当栈不空时做 Whlie(!EmptyStack(s)p=gheadv-first

35、Arc;/找到栈顶的一个未被访问的邻接点，入栈并访问找到栈顶的一个未被访问的邻接点，入栈并访问while(p)w=p-adjvex;if(!visitedw)push(s,w);visit(w);p=gheadw-firstArc;else p=p-next;/while/如果所有邻接点都被访问，出栈如果所有邻接点都被访问，出栈 pop(s,v);/whileV1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V112341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2

36、V5 V8 V4V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：深度遍历：V1V3 V7 V6 V2 V4 V8 V5DFS 算法效率分析算法效率分析:设图中有设图中有 n n 个顶点，个顶点，e e 条边，遍历时对图中每个顶条边，遍历时对图中每个顶点至多调用一次点至多调用一次DSFDSF函数，遍历图的过程就是对每个函数，遍历图的过程就是对每个顶点查找其邻接点的过程，消耗的时间取决于所采顶点查找其邻接点的过程，消耗的时间取决于所采用的存储结构用的存储结构u如果用邻接矩阵来表示图，

37、查找每个顶点的邻接如果用邻接矩阵来表示图，查找每个顶点的邻接点所需的时间为点所需的时间为O(O(n n2 2)。u如果用邻接表来表示图，查找每个顶点的邻接点如果用邻接表来表示图，查找每个顶点的邻接点所需的时间为所需的时间为O(e)O(e),加上访问加上访问 n n个头结点的时间，个头结点的时间，因此遍历图的时间复杂度为因此遍历图的时间复杂度为O(O(n n+e e)。BFS算法思想：算法思想：从图中的某个顶点从图中的某个顶点V V0 0出发，并在访问此顶点之后出发，并在访问此顶点之后依次访问依次访问V V0 0的所有未被访问过的邻接点的所有未被访问过的邻接点，之后，之后按这些按这些顶点被访问的

38、先后次序依次访问它们的邻接点顶点被访问的先后次序依次访问它们的邻接点，直至，直至图中所有和图中所有和V V0 0有路径相通的顶点都被访问到。有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问若此时图中尚有顶点未被访问,则另选图中一个则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。中所有顶点都被访问到为止。ABCDEFGHIJKL树的按层次进行访问的次序：树的按层次进行访问的次序：A、B、C、D、E、F、G、H、I、J、K、L适用的数据结构：队列适用的数据结构：队列 除了辅助数组除了辅助数组 visitedv

39、isited 之外，为了实现逐层之外，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问的这一层和上一层的顶点，以便于向下一层访问 广度优先搜索是一种分层的搜索过程，每向前走广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。递归的过程，其算法也不是递归的。Void BFSTraverse(Gragh G,int v)f

40、or(v=0;vG.vexnum;v+)visitedv=0;/清访问标记清访问标记 InitQueue(Q);/清队列清队列Q;for(v=0;vG.vexnum;v+)/对每一个顶点对每一个顶点v if(!visitedv)visitedv=1;visit(v);/访问访问v;标记标记v;EnQueue(Q,v);/v未被访问未被访问 while(!QueueEmpty(Q)/Q不空不空 DeQueue(Q,u);/出队头元素到出队头元素到u for(w=firstAdjVex(u);w;w=nextAdjVex(u,w)if(!visitedw)visitedw=1;visit(w);E

41、nQueue(w);/将将u的每个未被访问的邻接点的每个未被访问的邻接点w 入队入队 /if/while /if 例例adbce1234acdbvexdatafirstarc 5 5 4 3adjvexnext5e 1 5 1 1 4 3 2 20 1 2 3 4 5afr遍历序列：遍历序列：a0 1 2 3 4 5dfr遍历序列：遍历序列：a d0 1 2 3 4 5d cfr遍历序列：遍历序列：a d c1234acdbvexdatafirstarc 5 5 4 3adjvexnext5e 1 5 1 1 4 3 2 20 1 2 3 4 5d c bfr遍历序列：遍历序列：a d c b

42、0 1 2 3 4 5 c bfr遍历序列：遍历序列：a d c b0 1 2 3 4 5 c b efr遍历序列：遍历序列：a d c b e例例adbce0 1 2 3 4 5 2 5fr遍历序列：遍历序列：adcbe0 1 2 3 4 5 5fr遍历序列：遍历序列：adcbe0 1 2 3 4 5 fr遍历序列：遍历序列：a d c b e1234acdbvexdatafirstarc 5 5 4 3adjvexnext5e 1 5 1 1 4 3 2 2例例adbce 空间复杂度相同，都是空间复杂度相同，都是O(n)O(n)(借用了堆栈或队列）；借用了堆栈或队列）；时间复杂度只与存储结

43、构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有关，而与搜索路径无关。有关，而与搜索路径无关。1.1.求一条求一条从顶点从顶点 i i 到顶点到顶点 s s 的简单路径的简单路径2.2.求两个顶点之间的一条求两个顶点之间的一条路径长度最短路径长度最短的路径的路径三、遍历应用举例三、遍历应用举例应用应用1.1.求一条从顶点求一条从顶点 i i 到顶点到顶点 s s 的简单路径的简单路径a ab bc ch hd de ek kf fg g 求从顶点求从顶点 b b 到顶点到顶点 k k 的一条简单路径。的一条简单路径。从顶点从顶点 b b 出发进行深出发进行深度优先搜索遍历度优

44、先搜索遍历例如例如:假设找到的第一个邻接点是假设找到的第一个邻接点是a,a,且得到的结点访问序列为且得到的结点访问序列为:b b a a d h c d h c e e k k f g f g 假设找到的第一个邻接点是假设找到的第一个邻接点是c,c,则得到的结点访问序列为则得到的结点访问序列为:b b c h d a ec h d a e k k f g f gvoid DFSearch(int v,int s,char*PATH)/从第从第v个顶点出发递归地深度优先遍历图个顶点出发递归地深度优先遍历图G，/求得一条从求得一条从v到到s的简单路径，并记录在的简单路径，并记录在PATH中中 vi

45、sitedv=TRUE;/访问第访问第 v 个顶点个顶点 for(w=FirstAdjVex(v);w!=0 ;w=NextAdjVex(v)if(!visitedw)DFSearch(w,s,PATH);Append(PATH,getVertex(v);/第第v个顶点加入路径个顶点加入路径&!foundif(w=s)found=TRUE;Append(PATH,w);else if(!found)Delete(PATH,v);/从路径上删除顶点从路径上删除顶点 v应用应用2.2.求两个顶点之间的一条路径长度最短的路径求两个顶点之间的一条路径长度最短的路径 若两个顶点之间存在多条路径，则其中必

46、有若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径一条路径长度最短的路径。如何求得这条路径?abchdekfg求路径长度最短的路径可以基于广度优先搜索遍历进行求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改队列的结点结构及其入队列和出队列的算法。但需要修改队列的结点结构及其入队列和出队列的算法。深度优先搜索访问顶点的次深度优先搜索访问顶点的次序取决于图的存储结构，序取决于图的存储结构，而而广度优先搜索访问顶点的次广度优先搜索访问顶点的次序是按序是按“路径长度路径长度”渐增的渐增的次序次序。例如例如:求下图中顶点求下图中顶点 3 3 至顶至顶点点 5 5

47、 的一条最短路径。的一条最短路径。队列用双向链表的队列用双向链表的表示表示:3 1 2 4 7 5 Q.front Q.rear321475689q对无向连通图进行遍历对无向连通图进行遍历得到的将是一个极小连通子图，得到的将是一个极小连通子图，即图的即图的生成树生成树！由深度优先搜索得到的生成树，称为由深度优先搜索得到的生成树，称为深度优先搜索生成树深度优先搜索生成树。由广度优先搜索得到的生成树，称为由广度优先搜索得到的生成树，称为广度优先搜索生成树广度优先搜索生成树。q对非连通图进行遍历，得到的将是各连通分量的生成得到的将是各连通分量的生成树，即图的树，即图的生成森林生成森林！7.4.1 例

48、1：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图DEABCFJLMGHIK例例2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）求解步骤：求解步骤：Step1:Step1:先求出邻接矩阵或邻接表；先求出邻接矩阵或邻接表；Step2:Step2:写出写出DFSDFS或或BFSBFS结果序列；结果序列；Step3:Step3:画出对应子图或生成森林。画出对应子图或生成森林。我们选用我们选用邻接表邻接表方式来求方式来求

49、深度优先搜索深度优先搜索生成森林生成森林115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子图子图1：再写出再写出DFS结果（结果（3次）次）ABMJLCFDEGHKIABCFJLM先写出邻接表（或邻接矩阵）：先写出邻接表（或邻接矩阵）：子图子图2：子图子图3：极小连极小连通！通！DEGHIK子图子图(或连通分量或连通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林生成森林用对应的二叉树存储）生成森林用对应的二叉树存储）Void DFSForest(BiTree&T

50、)T=NULL;for(v=0;vn;v+)visitedv=0;for(v=0;vnextsibling=p;q=p;/q 当前森林中最后一棵树的根当前森林中最后一棵树的根 DFSTree(G,v,p);/深度优先遍历，并建立树；深度优先遍历，并建立树；/if/Void DFSTree(Graph G,int v,CSTree&T)visitedv=1;first=true;for(w=firstAdjVex(v);w;w=nextAdjVex(v,w)if(!visitedw)p=(CSTree)malloc(sizeof(CSNode);/生成树的根生成树的根 *p=GetVex(G,v