《第七章图.ppt》由会员分享，可在线阅读，更多相关《第七章图.ppt（96页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的基本概念图的基本概念图的存储表示图的存储表示图的遍历图的遍历图的连通性图的连通性 最小生成树最小生成树最短路径最短路径 活动网络活动网络第七章第七章 图图7.1 图的基本概念图的基本概念图定义图定义图定义图定义 图是由顶点集合图是由顶点集合图是由顶点集合图是由顶点集合(vertex)vertex)及顶点间的关系集合及顶点间的关系集合及顶点间的关系集合及顶点间的关系集合组成的一种数据结构组成的一种数据结构组成的一种数据结构组成的一种数据结构：GraphGraphGraphGraph(V V V V,E E E E)其中其中其中其中 V V V V=x x x x|x x x x 某个数据对象
2、某个数据对象某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；E E E E=(=(=(=(x x x x,y y y y)|)|)|)|x x x x,y y y y V V V V 或或或或 E E E E=yyy|x x x x,y y y y V V V V&PathPathPathPath(x x x x,y y y y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)edge)edge)edge)集合。集合。集合。集合。
3、PathPathPathPath(x x x x,y y y y)表示从表示从表示从表示从 x x x x 到到到到 y y y y 的一条单向通路的一条单向通路的一条单向通路的一条单向通路,它是有它是有它是有它是有方向的。方向的。方向的。方向的。o o有向图与无向图有向图与无向图有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对在有向图中，顶点对在有向图中，顶点对 x,yx,yx,y是有序的。在无是有序的。在无是有序的。在无是有序的。在无向图中，顶点对向图中，顶点对向图中，顶点对向图中，顶点对(x,y)x,y)x,y)x,y)是无序的。是无序的。是无序的。是无序的。o o完全
4、图完全图完全图完全图 若有若有若有若有 n n n n 个顶点的无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n n n(n n n n-1)/2-1)/2-1)/2-1)/2 条边条边条边条边,则此图则此图则此图则此图为完全无向图。有为完全无向图。有为完全无向图。有为完全无向图。有 n n n n 个顶点的有向图有个顶点的有向图有个顶点的有向图有个顶点的有向图有n n n n(n-n-n-n-1)1)1)1)条边条边条边条边,则此图则此图则此图则此图为完全有向图。为完全有向图。为完全有向图。为完全有向图。o o邻接顶点邻接顶点邻接顶点邻接顶点 如果如果如果如果(u u u u
5、,v v v v)是是是是 E E E E(G)(G)(G)(G)中的一条边，则称中的一条边，则称中的一条边，则称中的一条边，则称 u u u u 与与与与 v v v v 互为邻接顶点互为邻接顶点互为邻接顶点互为邻接顶点。l l权权 某某些些图图的的边边具具有有与与它它相相关关的的数数,称称之之为为权权。这种带权图叫做网络。这种带权图叫做网络。l l子子图图 设设有有两两个个图图 G G(V V,E E)和和 GG(V V,E E)。若若 V V V V 且且 E E E E,则则称称 图图G G 是是 图图G G 的子图。的子图。l l顶顶点点的的度度 一一个个顶顶点点v v的的度度是是与
6、与它它相相关关联联的的边边的的条条数数。记记作作TD(TD(v v)。在在有有向向图图中中,顶顶点点的的度度等等于于该顶点的入度与出度之和。该顶点的入度与出度之和。l l顶点顶点顶点顶点 v v v v 的入度的入度的入度的入度是以是以是以是以 v v v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(ID(ID(ID(v v v v););););顶点顶点顶点顶点 v v v v 的出度是以的出度是以的出度是以的出度是以 v v v v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记作记作记
7、作记作 OD(OD(OD(OD(v v v v)。l l路径路径路径路径 在图在图在图在图 G G G G(V V V V,E E E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v v v vi i i i 出发出发出发出发,沿沿沿沿一些边经过一些顶点一些边经过一些顶点一些边经过一些顶点一些边经过一些顶点 v v v vp p p p1 1 1 1,v v v vp p p p2 2 2 2,v v v vpmpmpmpm，到达顶点到达顶点到达顶点到达顶点v v v vj j j j。则称顶点序列则称顶点序列则称顶点序列则称顶点序列(v v v vi i i i v v v vp p p
8、 p1 1 1 1 v v v vp p p p2 2 2 2.v v v vpm pm pm pm v v v vj j j j )为从顶点为从顶点为从顶点为从顶点v v v vi i i i 到顶点到顶点到顶点到顶点 v v v vj j j j 的路径。它经过的边的路径。它经过的边的路径。它经过的边的路径。它经过的边(v v v vi i i i,v v v vp p p p1 1 1 1)、(v v v vp p p p1 1 1 1,v v v vp p p p2 2 2 2)、.、(v v v vpmpmpmpm,v v v vj j j j)应是属于应是属于应是属于应是属于E E
9、 E E的边。的边。的边。的边。l l路径长度路径长度路径长度路径长度 非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。l l简单路径简单路径简单路径简单路径 若路径上各顶点若路径上各顶点若路径上各顶点若路径上各顶点 v v v v1 1 1 1,v v v v2 2 2 2,.,.,.,.,v v v vm m m m 均不
10、互相均不互相均不互相均不互相重复重复重复重复,则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。l l回路回路回路回路 若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点 v v v v1 1 1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点v v v vm m m m 重重重重合合合合,则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。l l连通图与连通分量连通图与连通分量连通图与连通分量连通图与连通分量 在无向图中在无向图中在无向图中在无向图中,
11、若从顶点若从顶点若从顶点若从顶点v v v v1 1 1 1到顶点到顶点到顶点到顶点v v v v2 2 2 2有路径有路径有路径有路径,则称顶点则称顶点则称顶点则称顶点v v v v1 1 1 1与与与与v v v v2 2 2 2是连通的。如果图中任意一是连通的。如果图中任意一是连通的。如果图中任意一是连通的。如果图中任意一对顶点都是连通的对顶点都是连通的对顶点都是连通的对顶点都是连通的,则称此图是连通图。非连通图的则称此图是连通图。非连通图的则称此图是连通图。非连通图的则称此图是连通图。非连通图的极大连通子图叫做连通分量。极大连通子图叫做连通分量。极大连通子图叫做连通分量。极大连通子图叫
12、做连通分量。l l强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中,若若对于每一对顶点对于每一对顶点v vi i和和v vj j,都存在一条从都存在一条从v vi i到到v vj j和从和从v vj j到到v vi i的路径的路径,则称此图是强连通图。则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分非强连通图的极大强连通子图叫做强连通分量。量。l l生成树生成树 一个连通图的生成树是它的极小一个连通图的生成树是它的极小连通子图，在连通子图，在n n个顶点的情形下，有个顶点的情形下，有n n-1-1条边。条边。但有向图则可能得到它的由若干有向树组成但有向图则可能得到它的由
13、若干有向树组成的生成森林。的生成森林。7.2 图的存储表示图的存储表示l l在图的邻接矩阵表示中，有一个记录各个顶点信息的在图的邻接矩阵表示中，有一个记录各个顶点信息的在图的邻接矩阵表示中，有一个记录各个顶点信息的在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。顶点表，还有一个表示各个顶点之间关系的邻接矩阵。顶点表，还有一个表示各个顶点之间关系的邻接矩阵。顶点表，还有一个表示各个顶点之间关系的邻接矩阵。l l设图设图设图设图 A=(A=(A=(A=(V V V V,E E E E)是一个有是一个有是一个有是一个有 n n n n 个顶点的图，则图的
14、邻个顶点的图，则图的邻个顶点的图，则图的邻个顶点的图，则图的邻接矩阵是一个二维数组接矩阵是一个二维数组接矩阵是一个二维数组接矩阵是一个二维数组 A A A A.edge.edge.edge.edge n n n nn n n n ，定义：定义：定义：定义：邻接矩阵邻接矩阵(Adjacency Matrix)此时，邻接矩阵定义如下：此时，邻接矩阵定义如下：此时，邻接矩阵定义如下：此时，邻接矩阵定义如下：int adjmatrixint adjmatrixint adjmatrixint adjmatrixnn.nn.nn.nn.无向图的邻接矩阵是对称的，无向图的邻接矩阵是对称的，无向图的邻接矩阵
15、是对称的，无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的有向图的邻接矩阵可能是不对称的有向图的邻接矩阵可能是不对称的有向图的邻接矩阵可能是不对称的l在有向图中在有向图中,统计第统计第 i i 行行 1 1 的个数可得顶点的个数可得顶点 i i 的的出度，统计第出度，统计第 j j 行行 1 1 的个数可得顶点的个数可得顶点 j j 的入度。的入度。l在无向图中在无向图中,统计第统计第 i i 行行(列列)1)1 的个数可得顶点的个数可得顶点i i 的度。的度。网络的邻接矩阵网络的邻接矩阵此时，邻接矩阵定义如下：此时，邻接矩阵定义如下：此时，邻接矩阵定义如下：此时，邻接矩阵定义如下：i
16、nt adjnetworkint adjnetworkint adjnetworkint adjnetworknn.nn.nn.nn.为了反映一个图的全面信息，可以采用以下结构：为了反映一个图的全面信息，可以采用以下结构：#define MAXVEX 100Struct vertexint num;/*顶点编号顶点编号*/char data;/*顶点的信息顶点的信息*/；typedef struct graphstruct vertex vexsMAXVEX;/*顶点集合顶点集合*/int edgesMAXVEXMAXVEX;/*边的集合边的集合*/adjmax;其中其中MAXVEX定义一个图
17、的最多顶点个数，定义一个图的最多顶点个数，vertex结构定结构定义一个顶的基本数据，义一个顶的基本数据，adjmax定义图的类型，包含该图的定义图的类型，包含该图的所有顶点和边。所有顶点和边。以下函数通过用户交互产生一个图以下函数通过用户交互产生一个图的邻接矩阵表示。的邻接矩阵表示。1、输入顶点数和边、输入顶点数和边数数.2、输入顶点信息、输入顶点信息.3、确定边的顶点和、确定边的顶点和权重值。权重值。C程序程序运行运行C程序程序abfcde1024251647583邻接表邻接表(Adjacency List)Adjacency List)l l无向图的邻接表无向图的邻接表无向图的邻接表无向
18、图的邻接表 把同一个顶点发出的边链接在同一个边链表中，链表把同一个顶点发出的边链接在同一个边链表中，链表把同一个顶点发出的边链接在同一个边链表中，链表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存的每一个结点代表一条边，叫做边结点，结点中保存的每一个结点代表一条边，叫做边结点，结点中保存的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标有与该边相关联的另一顶点的顶点下标有与该边相关联的另一顶点的顶点下标有与该边相关联的另一顶点的顶点下标 destdestdestdest 和指向和指向和指向和指向同一链表中下一个边结点的
19、指针同一链表中下一个边结点的指针同一链表中下一个边结点的指针同一链表中下一个边结点的指针 linklinklinklink。l l有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第 i i i i 个边链表链接的边都是顶点个边链表链接的边都是顶点个边链表链接的边都是顶点个边链表链接的边都是顶点 i i i i 发发发发出的边。也叫做出的边。也叫做出的边。也叫做出的边。也叫做出边表出边表出边表出边表。在有向图的逆邻接表中，第在有向图的逆邻接表中，第在有向图的逆邻接
20、表中，第在有向图的逆邻接表中，第 i i i i 个边链表链接的边都是进入顶个边链表链接的边都是进入顶个边链表链接的边都是进入顶个边链表链接的边都是进入顶点点点点 i i i i 的边。也叫做的边。也叫做的边。也叫做的边。也叫做入边表入边表入边表入边表。l l带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 costcost。l l顶点顶点 i i 的边链表的表头指针的边链表的表头指针 adjadj 在顶点表的在顶点表的下标为下标为 i i 的顶点记录中，该记录还保存了该的顶点记录中，该记录还保存了该顶点的其它信息。顶点的其它信息。l l在邻接表的边链表中，各个边结点的链入顺序
21、在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。l l设图中有设图中有 n n 个顶点，个顶点，e e 条边，则用邻接表表条边，则用邻接表表示无向图时，需要示无向图时，需要 n n 个顶点结点，个顶点结点，2 2e e 个边结个边结点；用邻接表表示有向图时，若不考虑逆邻接点；用邻接表表示有向图时，若不考虑逆邻接表，只需表，只需 n n 个顶点结点，个顶点结点，e e 个边结点。个边结点。网络网络(带权图带权图)的邻接表的邻接表注意：一个图的临界矩阵表示是唯一的，但其邻接表表示不唯注意：一个图的临界矩阵表示是唯一的，但其邻接表表示不唯一。这是因为邻
22、接表表示中，各边表结点的邻接次序取决于建一。这是因为邻接表表示中，各边表结点的邻接次序取决于建立邻接表的算法以及边的输入次序。也就是说，在邻接表的每立邻接表的算法以及边的输入次序。也就是说，在邻接表的每个线性链表中，各结点的顺序是任意的。个线性链表中，各结点的顺序是任意的。一个图的邻接表存储结构定义如下：一个图的邻接表存储结构定义如下：#include#define MAXVEX 30Struct edgenode int adjvex;/*邻接点序号邻接点序号 */char info;/*邻接点信息邻接点信息*/struct edgenode*next;Struct vexnode char
23、 data;/*结点信息结点信息*/struct edgenode *link;Typedef struct vexnode adjlistMAXVEX;以下函数通过用户交互产生一个图以下函数通过用户交互产生一个图的邻接表表示。的邻接表表示。1、输入顶点数和边数。、输入顶点数和边数。2、输入顶点信息。、输入顶点信息。3、确定边的起始顶点。、确定边的起始顶点。C程序程序运行运行C程序程序邻接多重表邻接多重表(Adjacency Multilist)l l在邻接多重表中，每一条边只有一个边结点。为有关在邻接多重表中，每一条边只有一个边结点。为有关在邻接多重表中，每一条边只有一个边结点。为有关在邻接
24、多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。边的处理提供了方便。边的处理提供了方便。边的处理提供了方便。l l无向图的情形无向图的情形无向图的情形无向图的情形边结点的结构边结点的结构边结点的结构边结点的结构 mark vertex1 vertex2 path1 path2其中，其中，其中，其中，mark mark mark mark 是记录是否处理过的标记；是记录是否处理过的标记；是记录是否处理过的标记；是记录是否处理过的标记；vertexvertexvertexvertex1 1 1 1和和和和vertexvertexvertexvertex2 2 2 2是依附于该边的两顶点
25、位置。是依附于该边的两顶点位置。是依附于该边的两顶点位置。是依附于该边的两顶点位置。pathpathpathpath1 1 1 1域是链域是链域是链域是链接指针，指向下一条依附于顶点接指针，指向下一条依附于顶点接指针，指向下一条依附于顶点接指针，指向下一条依附于顶点vertexvertexvertexvertex1 1 1 1的边；的边；的边；的边；pathpathpathpath2 2 2 2也是链接指针，指向下一条依附于顶点也是链接指针，指向下一条依附于顶点也是链接指针，指向下一条依附于顶点也是链接指针，指向下一条依附于顶点vertexvertexvertexvertex2 2 2 2的边
26、。需要时还可设置一个存放与该边相关的边。需要时还可设置一个存放与该边相关的边。需要时还可设置一个存放与该边相关的边。需要时还可设置一个存放与该边相关的权值的域的权值的域的权值的域的权值的域 costcostcostcost。顶点结点的结构顶点结点的结构顶点结点的结构顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每一个顶存储顶点信息的结点表以顺序表方式组织，每一个顶存储顶点信息的结点表以顺序表方式组织，每一个顶存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，点结点有两个数据成员：其中，点结点有两个数据成员：其中，点结点有两个数据成员：其中，data data d
27、ata data 存放与该顶点相存放与该顶点相存放与该顶点相存放与该顶点相关的信息，关的信息，关的信息，关的信息，Firstout Firstout Firstout Firstout 是指示第一条依附于该顶点的边是指示第一条依附于该顶点的边是指示第一条依附于该顶点的边是指示第一条依附于该顶点的边的指针。的指针。的指针。的指针。在邻接多重表中在邻接多重表中在邻接多重表中在邻接多重表中,所有依附于同一个顶点的边都链接所有依附于同一个顶点的边都链接所有依附于同一个顶点的边都链接所有依附于同一个顶点的边都链接在同一个单链表中。在同一个单链表中。在同一个单链表中。在同一个单链表中。从顶点从顶点从顶点从
28、顶点 i i i i 出发出发出发出发,可以循链找到所有依附于该顶点可以循链找到所有依附于该顶点可以循链找到所有依附于该顶点可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。的边，也可以找到它的所有邻接顶点。的边，也可以找到它的所有邻接顶点。的边，也可以找到它的所有邻接顶点。data Firstoutl l有向图的情形有向图的情形有向图的情形有向图的情形 在用邻接表表示有向图时，有时需要同时使用邻在用邻接表表示有向图时，有时需要同时使用邻在用邻接表表示有向图时，有时需要同时使用邻在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表接表和逆邻接表。用有向图的
29、邻接多重表接表和逆邻接表。用有向图的邻接多重表接表和逆邻接表。用有向图的邻接多重表(十字链表十字链表十字链表十字链表)可把这两个表结合起来表示。可把这两个表结合起来表示。可把这两个表结合起来表示。可把这两个表结合起来表示。邻接多重表的结构邻接多重表的结构邻接多重表的结构邻接多重表的结构 其中，其中，其中，其中，markmarkmarkmark是处理标记；是处理标记；是处理标记；是处理标记；vertexvertexvertexvertex1 1 1 1和和和和vertexvertexvertexvertex2 2 2 2指明该指明该指明该指明该有向边始顶点和终顶点的位置。有向边始顶点和终顶点的位
30、置。有向边始顶点和终顶点的位置。有向边始顶点和终顶点的位置。pathpathpathpath1 1 1 1是指向始顶点与是指向始顶点与是指向始顶点与是指向始顶点与该边相同的下一条边的指针；该边相同的下一条边的指针；该边相同的下一条边的指针；该边相同的下一条边的指针；pathpathpathpath2 2 2 2是指向终顶点与该是指向终顶点与该是指向终顶点与该是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域边相同的下一条边的指针。需要时还可有权值域边相同的下一条边的指针。需要时还可有权值域边相同的下一条边的指针。需要时还可有权值域costcostcostcost。顶点结点的结构顶点结点
31、的结构顶点结点的结构顶点结点的结构 每个顶点有一个结点，它相当于出边表和入边表的表每个顶点有一个结点，它相当于出边表和入边表的表每个顶点有一个结点，它相当于出边表和入边表的表每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员头结点：其中，数据成员头结点：其中，数据成员头结点：其中，数据成员datadatadatadata存放与该顶点相关的信存放与该顶点相关的信存放与该顶点相关的信存放与该顶点相关的信息，指针息，指针息，指针息，指针FirstoutFirstoutFirstoutFirstout指示以该顶点为始顶点的出边表的指示以该顶点为始顶点的出边表的指示以该顶点为始顶点的出
32、边表的指示以该顶点为始顶点的出边表的第一条边，第一条边，第一条边，第一条边，FirstinFirstinFirstinFirstin指示以该顶点为终顶点的入边表指示以该顶点为终顶点的入边表指示以该顶点为终顶点的入边表指示以该顶点为终顶点的入边表的第一条边。的第一条边。的第一条边。的第一条边。data Firstin Firstout mark vertex1 vertex2 path1 path2-边结点的结构边结点的结构边结点的结构边结点的结构邻接多重表的结构邻接多重表的结构习题1、给出以下无向图、给出以下无向图G的的邻接矩阵和邻接表两种存储结构。邻接矩阵和邻接表两种存储结构。14523无向
33、图无向图G2、给出有向图、给出有向图G的邻接矩阵和十字链表两种存储结构。的邻接矩阵和十字链表两种存储结构。ABECDF15350103035452050152010有向图有向图G7.3 图的遍历图的遍历l l从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历图的遍历
34、图的遍历(Graph Traversal)Graph Traversal)Graph Traversal)Graph Traversal)。l l图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。回到了曾经访问过的顶点。回到了曾经访问过的顶点。回到了曾经访问
35、过的顶点。l l为了避免重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组过的辅助数组过的辅助数组过的辅助数组 visitedvisitedvisitedvisited ，它的初始状态为它的初始状态为它的初始状态为它的初始状态为 0 0 0 0，在，在，在，在图的遍历过程中，一旦某一个顶点图的遍历过程中，一旦某一个顶点图的遍历过程中，一旦某一个顶点图的遍历过程中，一旦某一个顶点 i i i i 被访问，就立即被访问，就立即被访问，就立即被访问，就立即让让让让
36、 visitedvisitedvisitedvisited i i i i 为为为为 1 1 1 1，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。深度优先搜索深度优先搜索DFS(Depth First Search)l l深度优先搜索的示例深度优先搜索的示例l lDFS DFS DFS DFS 在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点 v v v v 后，由后，由后，由后，由 v v v v 出发，出发，出发，出发，访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点 w w w w1
37、 1 1 1；再从再从再从再从 w w w w1 1 1 1 出发，访问与出发，访问与出发，访问与出发，访问与 w w w w1 1 1 1邻邻邻邻 接但还没有访问过的顶点接但还没有访问过的顶点接但还没有访问过的顶点接但还没有访问过的顶点 w w w w2 2 2 2；然后再从然后再从然后再从然后再从 w w w w2 2 2 2 出出出出发，进行类似的访问，发，进行类似的访问，发，进行类似的访问，发，进行类似的访问，如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点
38、所有的邻接顶点都被访问过的顶点 u u u u 为止。接着，为止。接着，为止。接着，为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点
39、出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。实现深度优先搜索的递归函数如下：实现深度优先搜索的递归函数如下：Boolean visitedMAX;/访问标志数组访问标志数组Status(*VisitFunc)(int v);/函数变量函数变量Void DFSTraverse(
40、Graph G,Status(*Visit)(int v)/对图对图G做深度优先遍历做深度优先遍历 VisitFunc=Visit;/使用全局变量使用全局变量VisitFunc,使使DFS不必设函数指针参数不必设函数指针参数 for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用对尚未访问的顶点调用DFSVoid DFS(Graph G,int v)/从第从第v个顶点出发递归地深度优先遍历图个顶点出发递归地深度优先遍历图G Visitedv=TRUE;V
41、isitFunc(v);/访问第访问第v个顶点个顶点 for(w=FirstAdjVex(G,v);w;w=NextadjVex(G,v,w)if(!visitedw)DFS(G,w);/对对v尚未访问的邻接顶点尚未访问的邻接顶点w调用调用DFS算法分析算法分析l l图中有图中有图中有图中有 n n n n 个顶点，个顶点，个顶点，个顶点，e e e e 条边。条边。条边。条边。l l如果用邻接表表示图，沿如果用邻接表表示图，沿如果用邻接表表示图，沿如果用邻接表表示图，沿 FirstoutFirstoutFirstoutFirstout link link link link 链可以链可以链可
42、以链可以找到某个顶点找到某个顶点找到某个顶点找到某个顶点 v v v v 的所有邻接顶点的所有邻接顶点的所有邻接顶点的所有邻接顶点 w w w w。由于总共有由于总共有由于总共有由于总共有 2 2 2 2e e e e 个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为O(O(O(O(e e e e)。而且对所有顶而且对所有顶而且对所有顶而且对所有顶点递归访问点递归访问点递归访问点递归访问1 1 1 1次，所以遍历图的时间复杂性为次，所以遍历图的时间复杂性为次，所以遍历图的时间复杂性为次，所以遍历图的时间复杂性为O(O(O(O(n
43、n n n+e e e e)。l l如果用邻接矩阵表示图，则查找每一个顶点的所有的如果用邻接矩阵表示图，则查找每一个顶点的所有的如果用邻接矩阵表示图，则查找每一个顶点的所有的如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为边，所需时间为边，所需时间为边，所需时间为O(O(O(O(n n n n)，则遍历图中所有的顶点所需的则遍历图中所有的顶点所需的则遍历图中所有的顶点所需的则遍历图中所有的顶点所需的时间为时间为时间为时间为O(O(O(O(n n n n2 2 2 2)。广度优先搜索广度优先搜索BFS(Breadth First Search)l l广度优先搜索的示例广度优先搜索的示
44、例 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树l l使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点 v v v v 之后，由之后，由之后，由之后，由 v v v v 出发，依次访问出发，依次访问出发，依次访问出发，依次访问 v v v v 的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点 w w w w1 1 1 1,w w w w2 2 2 2,w w w wt t t t，然后再顺序访问然后再顺序访问然后再顺序访问然后再顺序访
45、问 w w w w1 1 1 1,w w w w2 2 2 2,w w w wt t t t 的所有还未被访问过的邻接顶点。再从这些访问过的所有还未被访问过的邻接顶点。再从这些访问过的所有还未被访问过的邻接顶点。再从这些访问过的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻的顶点出发，再访问它们的所有还未被访问过的邻的顶点出发，再访问它们的所有还未被访问过的邻的顶点出发，再访问它们的所有还未被访问过的邻接顶点，接顶点，接顶点，接顶点，如此做下去，直到图中所有顶点都被访如此做下去，直到图中所有顶点都被访如此做下去，直到图中所有顶点都被访如此做下去，直到图中
46、所有顶点都被访问到为止。问到为止。问到为止。问到为止。l l广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往步可能访问一批顶点，不像深度优先搜索那样有往步可能访问一批顶点，不像深度优先搜索那样有往步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的回退的情况。因此，广度优先搜索不是一个递归的回退的情况。因此，广度优先搜索不是一个递归的回退的情况。因此，广度优先搜索不是一个递归的过程，其算法
47、也不是递归的。过程，其算法也不是递归的。过程，其算法也不是递归的。过程，其算法也不是递归的。l l为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层访问。访问。访问。访问。l l为避免重复访问，需要一个辅助数组为避免重复访问，需要一个辅助数组为避免重复访问，需要一个辅助数组为避免重
48、复访问，需要一个辅助数组 visitedvisitedvisitedvisited ，给被访问过的顶点加标记。给被访问过的顶点加标记。给被访问过的顶点加标记。给被访问过的顶点加标记。算法分析算法分析如果使用邻接表表示图，则循环的总时间代价为如果使用邻接表表示图，则循环的总时间代价为如果使用邻接表表示图，则循环的总时间代价为如果使用邻接表表示图，则循环的总时间代价为 d d d d0 0 0 0+d d d d1 1 1 1+d d d dn n n n-1-1-1-1=O(=O(=O(=O(e e e e)，其中的其中的其中的其中的 d d d di i i i 是顶点是顶点是顶点是顶点 i
49、i i i 的度。的度。的度。的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，如果使用邻接矩阵，则对于每一个被访问过的顶点，如果使用邻接矩阵，则对于每一个被访问过的顶点，如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的循环要检测矩阵中的循环要检测矩阵中的循环要检测矩阵中的 n n n n 个元素，总的时间代价为个元素，总的时间代价为个元素，总的时间代价为个元素，总的时间代价为O(O(O(O(n n n n2 2 2 2)。算法：算法：p170 算法算法7.67.4 图的连通性图的连通性l l当无向图为非连通图时，从图中某一顶点出发，利用深度优先当无向图为非连通图时，从图中某
50、一顶点出发，利用深度优先当无向图为非连通图时，从图中某一顶点出发，利用深度优先当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图只能访问到该顶点所在的最大连通子图只能访问到该顶点所在的最大连通子图只能访问到该顶点所在的最大连通子图(连通分量连通分量连通分量连通分量)的所有顶点。的所有顶点。的所有顶点。的所有顶点。l l若从无向图的每一个连通分量