第七章 图精选PPT.ppt

《第七章 图精选PPT.ppt》由会员分享，可在线阅读，更多相关《第七章 图精选PPT.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 图图1第1页，本讲稿共71页7.1 图的基本概念图的基本概念图的定义和术语图的定义和术语图的基本操作图的基本操作2第2页，本讲稿共71页7.1.1 7.1.1 图的定义和术语图的定义和术语1 1图的定义图的定义 图图(Graph)是是由由非非空空的的顶顶点点集集合合和和一一个个描描述述顶顶点点之之间间关关系系边（或者弧）的集合组成，其形式化定义为：边（或者弧）的集合组成，其形式化定义为：G（V，E）Vvi|vi dataobject，E(vi,vj)|vi,vj V P(vi,vj)其其中中，G表表示示一一个个图图，V是是图图G中中顶顶点点的的集集合合，E是是图图G中中边边的的集

2、集合合，集集合合E中中P(vi,vj)表表示示顶顶点点vi和和顶顶点点vj之之间间有有一一条条直直接接连连线线，即即偶偶对对(vi,vj)表示一条边。表示一条边。3第3页，本讲稿共71页2.图的相关术语图的相关术语 无无向向图图。在在一一个个图图中中，如如果果任任意意两两个个顶顶点点构构成成的的偶偶对对（vi,vj）E是是无无序序的的，即即顶顶点点之之间间的的连连线线没没有有方方向向，则则称该图为无向图。称该图为无向图。有有向向图图。在在一一个个图图中中，如如果果任任意意两两个个顶顶点点构构成成的的偶偶对对（vi,vj）E是是有有序序的的，即即顶顶点点之之间间的的连连线线是是有有方方向向的的，

3、则称该图为有向图。则称该图为有向图。有向图G24第4页，本讲稿共71页 顶点、边、弧、弧头、弧尾。顶点、边、弧、弧头、弧尾。图中的数据元素图中的数据元素vi称称为顶点为顶点(vertex)；P(vi,vj)表示在顶点表示在顶点vi和顶点和顶点vj之间有一条之间有一条直接连线。在无向图中称为边；有向图中称为弧。边用顶点直接连线。在无向图中称为边；有向图中称为弧。边用顶点的无序偶对（的无序偶对（vi,vj）来表示，顶点）来表示，顶点vi和顶点和顶点vj互为邻接点；互为邻接点；弧用顶点的有序偶对弧用顶点的有序偶对来表示，有序偶对的第一个结点来表示，有序偶对的第一个结点vi称为始点（或弧尾），在图中就

4、是不带箭头的一端；有序称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点偶对的第二个结点vj称为终点（或弧头），在图中就是带箭称为终点（或弧头），在图中就是带箭头的一端。头的一端。无向完全图。无向完全图。在一个无向图中，如果任意两顶点都有在一个无向图中，如果任意两顶点都有一条直接边相连接，则该图为无向完全图。在一个含有一条直接边相连接，则该图为无向完全图。在一个含有n个个顶点的无向完全图中，有顶点的无向完全图中，有n(n-1)/2条边。条边。有向完全图。有向完全图。在一个有向图中，如果任意两顶点之间在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则该图为有向完

5、全图。都有方向互为相反的两条弧相连接，则该图为有向完全图。在一个含有在一个含有n个顶点的有向完全图中，有个顶点的有向完全图中，有n(n-1)条边。条边。5第5页，本讲稿共71页 顶点的度、入度、出度。顶点的度、入度、出度。顶点的度（顶点的度（degree）是指依）是指依附于某顶点附于某顶点v的边数，通常记为的边数，通常记为TD(v)。在有向图中，要区。在有向图中，要区别顶点的入度与出度的概念。顶点别顶点的入度与出度的概念。顶点v的入度是指以顶点的入度是指以顶点 为终为终点的弧的数目。记为点的弧的数目。记为ID(v)；顶点；顶点v出度是指以顶点出度是指以顶点v为始点为始点的弧的数目，记为的弧的数

6、目，记为OD(v)。有。有TD(v)=ID(v)OD(v)。可以证明，对于具有可以证明，对于具有n个顶点、个顶点、e条边的图，顶点条边的图，顶点vi的度的度TD(vi)与顶点的个数以及边的数目满足关系：与顶点的个数以及边的数目满足关系：2e =6第6页，本讲稿共71页 (7)边的权、网图。与边有关的数据信息称为权边的权、网图。与边有关的数据信息称为权（weight）。在实际应用中，权值可以有某种含义。比如，）。在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上

7、的权条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。边上带权的图称为网图到后一个工程所需要的时间等等。边上带权的图称为网图或网络（或网络（network）。如果边是有方向的带权图，则就是）。如果边是有方向的带权图，则就是一个有向网图。一个有向网图。(8)路径、路径长度。路径、路径长度。顶点顶点vp到顶点到顶点vq之间的路径之间的路径（path）是指顶点序列）是指顶点

8、序列vp,vi1,vi2,vim,vq。其中，（。其中，（vp,vi1），），(vi1,vi2)，,(vim,vq)分别为图中的边。路径上边的数目分别为图中的边。路径上边的数目称为路径长度。称为路径长度。7第7页，本讲稿共71页 (9)回路、简单路径、简单回路。回路、简单路径、简单回路。路径中第一个顶点路径中第一个顶点与最后一个顶点相同的路径称为回路或者环（与最后一个顶点相同的路径称为回路或者环（cycle）。）。序列中顶点不重复出现的路径称为简单路径。除第一个序列中顶点不重复出现的路径称为简单路径。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路顶点与最后一个顶点之外，其他顶点不重复

9、出现的回路称为简单回路，或者简单环。称为简单回路，或者简单环。(10)子图。对于图子图。对于图G=（V，E），），G=（V，E），若），若存在存在V是是V的子集的子集，E是是E的子集的子集，则称图，则称图G是是G的一的一个子图。下图示出了个子图。下图示出了G2和和G1的两个子图的两个子图G和和G。8第8页，本讲稿共71页(11)连连通通的的、连连通通图图、连连通通分分量量。在在无无向向图图中中，如如果果从从一一个个顶顶点点vi到到另另一一个个顶顶点点vj(ij)有有路路径径，则则称称顶顶点点vi和和vj是是连连通通的的。如如果果图图中中任任意意两两顶顶点点都都是是连连通通的的，则则称称该该图图

10、是是连连通通图图。无无向向图图的的极极大大连连通通子子图图称称为为连连通通分分量量。下下图图(a)中中有有两个连通分量，如图两个连通分量，如图(b)所示。所示。9第9页，本讲稿共71页 (12)强强连连通通图图、强强连连通通分分量量。对对于于有有向向图图来来说说，若若图图中中任任意意一一对对顶顶点点vi 和和vj(ij)均均有有从从一一个个顶顶点点vi到到另另一一个个顶顶点点vj有有路路径径，也也有有从从vj到到vi的的路路径径，则则称称该该有有向向图图是是强强连连通通图图。有向图的极大强连通子图称为强连通分量。有向图的极大强连通子图称为强连通分量。左左下下图图中中有有两两个个强强连连通通分分

11、量量，分分别别是是v1,v3,v4和和v2，如右下图所示。如右下图所示。10第10页，本讲稿共71页 (13)生生成成树树。所所谓谓连连通通图图G的的生生成成树树，是是G的的包包含含其其全全部部n个个顶顶点点的的一一个个极极小小连连通通子子图图。它它必必定定包包含含且且仅仅包包含含G的的n-1条边。下图示出了图条边。下图示出了图G1 的一棵生成树。的一棵生成树。(14)生生成成森森林林。在在非非连连通通图图中中，由由每每个个连连通通分分量量都都可可得得到到一一个个极极小小连连通通子子图图，即即一一棵棵生生成成树树。这这些些连连通通分分量量的生成树就组成了一个非连通图的生成森林。的生成树就组成了

12、一个非连通图的生成森林。11第11页，本讲稿共71页7.1.2 7.1.2 图的基本操作图的基本操作CreatGraph（G）输入图）输入图G的顶点和边，建立图的顶点和边，建立图G的存储。的存储。DestroyGraph（G）释放图）释放图G占用的存储空间。占用的存储空间。GetVex（G，v）在图）在图G中找到顶点中找到顶点v，并返回顶点，并返回顶点v的相关信息。的相关信息。PutVex（G，v，value）在在图图G中中找找到到顶顶点点v，并并将将value值值赋赋给顶点给顶点v。InsertVex（G，v）在图）在图G中增添新顶点中增添新顶点v。DeleteVex（G，v）在在图图G中中

13、，删删除除顶顶点点v以以及及所所有有和和顶顶点点v相相关关联联的边或弧。的边或弧。InsertArc（G，v，w）在在图图G中中增增添添一一条条从从顶顶点点v到到顶顶点点w的的边或弧。边或弧。DeleteArc（G，v，w）在在图图G中中删删除除一一条条从从顶顶点点v到到顶顶点点w的的边边或弧。或弧。12第12页，本讲稿共71页DFSTraverse（G，v）在图在图G中，从顶点中，从顶点v出发深度优先遍出发深度优先遍历图历图G。BFSTraverse（G，v）在图在图G中，从顶点中，从顶点v出发广度优先遍出发广度优先遍历图历图G。LocateVex（G，u）在图在图G中找到顶点中找到顶点u，

14、返回该顶点在图，返回该顶点在图中位置。中位置。FirstAdjVex（G，v）在图在图G中，返回中，返回v的第一个邻接点。若的第一个邻接点。若顶点在顶点在G中没有邻接顶点，则返回中没有邻接顶点，则返回“空空”。NextAdjVex（G，v，w）在图在图G中，返回中，返回v的的(相对于相对于w的的)下下一个邻接顶点。若一个邻接顶点。若w是是v的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。13第13页，本讲稿共71页7.2 7.2 图的存储表示图的存储表示邻接矩阵邻接矩阵邻接表邻接表14第14页，本讲稿共71页7.2.1 邻接矩阵邻接矩阵 所所谓谓邻邻接接矩矩阵阵（Adjacency

15、Matrix）的的存存储储结结构构，就就是是用用一一维维数数组组存存储储图图中中顶顶点点的的信信息息，用用矩矩阵阵表表示示图图中中各各顶顶点点之之间间的的邻邻接接关关系系。假假设设图图G（V，E）有有n个个确确定定的的顶顶点点，即即Vv0,v1,vn-1,则则表表示示G中中各各顶顶点点相相邻邻关关系系为为一一个个n阶阶方方阵阵，矩矩阵阵的元素为：的元素为：Aij=若若G是网图，则邻接矩阵可定义为：是网图，则邻接矩阵可定义为：Aij=其其中中，wij表表示示边边(vi,vj)或或上上的的权权值值；表表示示一一个个计计算算机允许的、大于所有边上权值的数。机允许的、大于所有边上权值的数。1 若若(v

16、i,vj)或或是是E(G)中的边中的边0 若若(vi,vj)或或不是不是E(G)中的边中的边wij 若若(vi,vj)或或是是E(G)中的边中的边0或或 若若(vi,vj)或或不是不是E(G)中的边中的边15第15页，本讲稿共71页 用邻接矩阵表示法表示的无向图和网图如下图所示。16第16页，本讲稿共71页 从从图图的的邻邻接接矩矩阵阵存存储储方方法法容容易易看看出出这这种种表表示示具具有有以以下下特特点：点：无无向向图图的的邻邻接接矩矩阵阵一一定定是是一一个个对对称称矩矩阵阵。因因此此，在在具具体体存存放放邻邻接接矩矩阵阵时时只只需需存存放放上上（或或下下）三三角角矩矩阵阵的的元元素素即即可

17、。可。对对于于无无向向图图，邻邻接接矩矩阵阵的的第第i i行行（或或第第i i列列）非非零零元元素素（或非（或非元素）的个数正好是第元素）的个数正好是第i i个顶点的度个顶点的度TD(vi)TD(vi)。对对于于有有向向图图，邻邻接接矩矩阵阵的的第第i i行行（或或第第i i列列）非非零零元元素素（或或非非元元素素）的的个个数数正正好好是是第第i i个个顶顶点点的的出出度度OD(vi)OD(vi)（或或入度入度ID(vi)ID(vi)）。）。用用邻邻接接矩矩阵阵方方法法存存储储图图，很很容容易易确确定定图图中中任任意意两两个个顶顶点点之之间间是是否否有有边边相相连连；但但是是，要要确确定定图图

18、中中有有多多少少条条边边，则则必必须须按按行行、按按列列对对每每个个元元素素进进行行检检测测，所所花花费费的的时时间间代代价价很大。这是用邻接矩阵存储图的局限性。很大。这是用邻接矩阵存储图的局限性。17第17页，本讲稿共71页 在在用用邻邻接接矩矩阵阵存存储储图图时时，除除了了用用一一个个二二维维数数组组存存储储用用于于表表示示顶顶点点间间相相邻邻关关系系的的邻邻接接矩矩阵阵外外，还还需需用用一一个个一一维维数数组组来来存存储储顶顶点点信信息息，另另外外还还有有图图的的顶顶点点数数和和边边数数。故故可可将将其其形式描述如下：形式描述如下：#define n 6/图的顶点数图的顶点数#defin

19、e e 8/图的边（弧）数图的边（弧）数typedef char vextype;/顶点的数据类型顶点的数据类型typedef float adjtype;/权值类型权值类型typedef structvextype vexsn;/顶点表顶点表adjtype arcsnn;/邻接矩阵，即边表邻接矩阵，即边表int n,e;graph;/graph是以邻接矩阵存储的图类型是以邻接矩阵存储的图类型18第18页，本讲稿共71页 建立一个图的邻接矩阵存储的算法如下：建立一个图的邻接矩阵存储的算法如下：算法算法7.1 无向网络的建立无向网络的建立CREATGRAPH(graph*ga)int i,j,k

20、;float w;for(i=0;ivexsi=getchar();/建立顶点表建立顶点表for(i=0;in;i+)for(j=0;jarcsij=0;/邻接矩阵初始化邻接矩阵初始化for(k=0;karcsij=w;ga-arcsji=w;19第19页，本讲稿共71页7.2.2 邻接表邻接表 邻接表邻接表(Adjacency List)是图的一种顺序存储与链式存储结是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图就是对于图G中的每个顶点中的每个顶点vi，将所有邻接于，将所有邻接于vi的顶点的顶点

21、vj链成链成一个单链表，这个单链表就称为顶点一个单链表，这个单链表就称为顶点vi的邻接表，再将所有的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。点的邻接表表头放到数组中，就构成了图的邻接表。20第20页，本讲稿共71页 在邻接表表示中有两种结点结构，如下图所示。在邻接表表示中有两种结点结构，如下图所示。一一种种是是顶顶点点表表的的结结点点结结构构，它它由由顶顶点点域域（vertex）和和指指向向第第一一条条邻邻接接边边的的指指针针域域（firstedge）构构成成，另另一一种种是是边边表表（即即邻邻接接表表）结结点点，它它由由邻邻接接点点域域(adjvex)和和指指向向下下一

22、一条条邻邻接接边边的的指指针针域域(next)构构成成。对对于于网网图图的的边边表表需需再再增增设设一一个个存存储储边边上上信信息息（如如权权值值等等）的的域域（info），网网图图的的边边表表结结构构如如下图所示。下图所示。21第21页，本讲稿共71页 下图给出无向图及对应的邻接表表示。下图给出无向图及对应的邻接表表示。22第22页，本讲稿共71页邻接表表示的形式描述如下：邻接表表示的形式描述如下：typedef struct nodeint adjvex;/*邻接点域邻接点域*/struct node*next;/*指向下一个邻接点的指针域指向下一个邻接点的指针域*/*若要表示边上信息，则

23、应增加一个数据域若要表示边上信息，则应增加一个数据域info*/EdgeNode;/*边表结点边表结点*/typedef struct vnodeVertexType vertex;/*顶点域顶点域*/EdgeNode*firstedge;/*边表头指针边表头指针*/VerNode;/*顶点表结点顶点表结点*/VerNode gan;23第23页，本讲稿共71页算法算法7.2 无向图邻接表的建立无向图邻接表的建立CREATADJLIST(VexNode ga)/*建立无向图的邻接表建立无向图的邻接表*/int i,j,k;EdgeNode*s;for(i=0;in;i+)/*读入顶点信息读入顶

24、点信息*/gai.vertex=getchar();gai.firstedge=NULL;/*边表头指针初始化边表头指针初始化*/for(k=0;kadjvex=j;s-next=gai.firstedge;gai.firstedge=s;/*将将*s插入顶点插入顶点vi的边表头部的边表头部*/24第24页，本讲稿共71页 若若无无向向图图中中有有n个个顶顶点点、e条条边边，则则它它的的邻邻接接表表需需n个个头头结结点点和和2e个个表表结结点点。显显然然，在在边边稀稀疏疏(en(n-1)/2)的的情情况况下下，用用邻邻接接表表表表示示图图比比邻邻接接矩矩阵阵节节省省存存储储空空间间，当当和和边

25、边相相关的信息较多时更是如此。关的信息较多时更是如此。在在无无向向图图的的邻邻接接表表中中，顶顶点点vi的的度度恰恰为为第第i个个链链表表中中的的结结点点数数；而而在在有有向向图图中中，第第i个个链链表表中中的的结结点点个个数数只只是是顶顶点点vi的的出出度度，为为求求入入度度，必必须须遍遍历历整整个个邻邻接接表表。在在所所有有链链表表中中其其邻邻接接点点域域的的值值为为i的的结结点点的的个个数数是是顶顶点点vi的的入入度度。有有时时，为为了了便便于于确确定定顶顶点点的的入入度度或或以以顶顶点点vi为为头头的的弧弧，可可以以建建立立一一个个有有向向图图的的逆逆邻邻接接表表，即即对对每每个个顶顶

26、点点vi 建建立立一一个个链链接接以以vi为头的弧的链表。为头的弧的链表。25第25页，本讲稿共71页 下图所示为有向图下图所示为有向图G2的邻接表和逆邻接表。的邻接表和逆邻接表。26第26页，本讲稿共71页 在在建建立立邻邻接接表表或或逆逆邻邻接接表表时时，若若输输入入的的顶顶点点信信息息即即为为顶顶点点的的编编号号，则则建建立立邻邻接接表表的的复复杂杂度度为为O（n+e），否否则则，需需要要通通过过查查找找才才能能得得到到顶顶点点在在图图中中位位置置，则则时时间复杂度为间复杂度为O（ne）。）。在在邻邻接接表表上上容容易易找找到到任任一一顶顶点点的的第第一一个个邻邻接接点点和和下下一一个个

27、邻邻接接点点，但但要要判判定定任任意意两两个个顶顶点点（vi 和和vj）之之间间是是否否有有边边或或弧弧相相连连，则则需需搜搜索索第第i个个或或第第j个个链链表表，因因此此，不及邻接矩阵方便。不及邻接矩阵方便。27第27页，本讲稿共71页7.3 图的遍历图的遍历深度优先搜索深度优先搜索广度优先搜索广度优先搜索28第28页，本讲稿共71页 图图的的遍遍历历是是指指从从图图中中的的任任一一顶顶点点出出发发，对对图图中中的的所所有有顶顶点点访访问问一一次次且且只只访访问问一一次次。图图的的遍遍历历是是图图的的一一种种基基本本操操作作，图图的许多其它操作都是建立在遍历操作的基础之上。的许多其它操作都是

28、建立在遍历操作的基础之上。由由于于图图结结构构本本身身的的复复杂杂性性，所所以以图图的的遍遍历历操操作作也也较较复复杂杂，主要表现在以下四个方面：主要表现在以下四个方面：在在图图结结构构中中，没没有有一一个个“自自然然”的的首首结结点点，图图中中任任意意一一个顶点都可作为第一个被访问的结点。个顶点都可作为第一个被访问的结点。在在非非连连通通图图中中，从从一一个个顶顶点点出出发发，只只能能够够访访问问它它所所在在的的连连通通分分量量上上的的所所有有顶顶点点，因因此此，还还需需考考虑虑如如何何选选取取下下一一个个出出发点以访问图中其余的连通分量。发点以访问图中其余的连通分量。在在图图结结构构中中，

29、如如果果有有回回路路存存在在，那那么么一一个个顶顶点点被被访访问问之之后，有可能沿回路又回到该顶点。后，有可能沿回路又回到该顶点。在在图图结结构构中中，一一个个顶顶点点可可以以和和其其它它多多个个顶顶点点相相连连，当当这这样样的的顶顶点点访访问问过过后后，存存在在如如何何选选取取下下一一个个要要访访问问的的顶顶点点的的问问题。题。29第29页，本讲稿共71页7.3.1 深度优先搜索 深深度度优优先先搜搜索索（Depth_First Search）遍遍历历类类似似于于树树的的先先根根遍历，是树的先根遍历的推广。遍历，是树的先根遍历的推广。假假设设初初始始状状态态是是图图中中所所有有顶顶点点未未曾

30、曾被被访访问问，则则深深度度优优先先搜搜索索可可从从图图中中某某个个顶顶点点发发v出出发发，访访问问此此顶顶点点，然然后后依依次次从从v的的未未被被访访问问的的邻邻接接点点出出发发深深度度优优先先遍遍历历图图，直直至至图图中中所所有有和和v有有路路径径相相通通的的顶顶点点都都被被访访问问到到；若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中所有顶点都被访问到为止。中所有顶点都被访问到为止。30第30页，本讲稿共71页 以以下下图图的的无无向向图图G5为为例例，进进行行图图

31、的的深深度度优优先先搜搜索索。假假设设从从顶顶点点v1出出发发进进行行搜搜索索，在在访访问问了了顶顶点点v1之之后后，选选择择邻邻接接点点v2。因因为为v2未未曾曾访访问问，则则从从v2出出发发进进行行搜搜索索。依依次次类类推推，接接着着从从v4、v8、v5 出出发发进进行行搜搜索索。在在访访问问了了v5之之后后，由由于于v5的的邻邻接接点点都都已已被被访访问问，则则搜搜索索回回到到 v8。由由于于同同样样的的理理由由，搜搜索索继继续续回回到到v4，v2直直至至v1，此此时时由由于于v1的的另另一一个个邻邻接接点点未未被被访访问问，则则搜搜索索又又从从v1到到v3，再再继继续进行下去由此，得到

32、的顶点访问序列为：续进行下去由此，得到的顶点访问序列为：v1 v2 v4v8 v5 v3v6v731第31页，本讲稿共71页 显显然然，这这是是一一个个递递归归的的过过程程。为为了了在在遍遍历历过过程程中中便便于于区区分分顶顶点点是是否否已已被被访访问问，需需附附设设访访问问标标志志数数组组visitedn，其其初初值值为为FALSE，一一旦旦某某个个顶顶点点被被访访问问，则则其其相相应应的的分分量量置置为为TRUE。算法算法7.3 深度优先搜索算法深度优先搜索算法int visitednGraph g;DFS(int i)int j;printf(node:%cn,g.vexsi);/*访问

33、顶点访问顶点Vi*/visitedi=TRUE;/*标记标记Vi已访问已访问*/for(j=0;jadjvex)DFSL(p-adjvex);p=p-next;/*找找Vi的下一个邻接点的下一个邻接点*/33第33页，本讲稿共71页 分分析析上上述述算算法法，在在遍遍历历时时，对对图图中中每每个个顶顶点点至至多多调调用用一一次次DFS 函函数数，因因为为一一旦旦某某个个顶顶点点被被标标志志成成已已被被访访问问，就就不不再再从从它它出出发发进进行行搜搜索索。因因此此，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程。其其耗耗费费的的时时间间则则取取

34、决决于于所所采采用用的的存存储储结结构构。当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵图图的的存存储储结结构构时时，查查找找每每个个顶顶点点的的邻邻接接点点所所需需时时间间为为O(n2)，其其中中n为为图图中中顶顶点点数数。而而当当以以邻邻接接表表作作图图的的存存储储结结构构时时，找找邻邻接接点点所所需需时时间间为为O(e)，其其中中e为为无无向向图图中中边边的的数数或或有有向向图图中中弧弧的的数数。由由此此，当当以以邻邻接接表表作作存存储储结结构构时时，深深度度优先搜索遍历图的时间复杂度为优先搜索遍历图的时间复杂度为O(n+e)。34第34页，本讲稿共71页7.3.2 广度优先搜索广度优

35、先搜索 广广度度优优先先搜搜索索（Breadth_First Search）遍遍历历类类似似于于树树的的按按层层次遍历的过程。次遍历的过程。假假设设从从图图中中某某顶顶点点v出出发发，在在访访问问了了v之之后后依依次次访访问问v的的各各个个未未曾曾访访问问过过和和邻邻接接点点，然然后后分分别别从从这这些些邻邻接接点点出出发发依依次次访访问问它它们们的的邻邻接接点点，并并使使“先先被被访访问问的的顶顶点点的的邻邻接接点点”先先于于“后后被被访访问问的的顶顶点点的的邻邻接接点点”被被访访问问，直直至至图图中中所所有有已已被被访访问问的的顶顶点点的的邻邻接接点点都都被被访访问问到到。若若此此时时图图

36、中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中中所所有有顶顶点点都都被被访访问问到到为为止止。换换句句话话说说，广广度度优优先先搜搜索索遍遍历历图图的的过过程程中中以以v为为起起始始点点，由由近近至至远远，依依次次访访问问和和v有有路路径相通且路径长度为径相通且路径长度为1,2,的顶点。的顶点。35第35页，本讲稿共71页 例例如如，对对下下图图所所示示无无向向图图G5 进进行行广广度度优优先先搜搜索索遍遍历历，首首先先访访问问v1 和和v1的的邻邻接接点点v2和和v3，然然后后依依次

37、次访访问问v2 的的邻邻接接点点v4 和和v5 及及v3 的的邻邻接接点点v6和和v7，最最后后访访问问v4 的的邻邻接接点点v8。由由于于这这些些顶顶点点的的邻邻接接点点均均已已被被访访问问，并并且且图图中中所所有有顶顶点点都都被被访访问问，由由些些完完成成了了图图的的遍遍历历。得得到到的的顶顶点点访访问问序序列列为：为：v1v2 v3 v4 v5 v6 v7 v836第36页，本讲稿共71页 和和深深度度优优先先搜搜索索类类似似，在在遍遍历历的的过过程程中中也也需需要要一一个个访访问问标标志志数数组组。并并且且，为为了了顺顺次次访访问问路路径径长长度度为为2、3、的的顶顶点点，需需附附设设

38、队队列列以以存存储储已已被被访访问问的的路路径径长长度度为为1、2、的顶点。的顶点。从从图图的的某某一一点点v出出发发，递递归归地地进进行行广广度度优优先先遍遍历历的的过过程程如如算法所示。算法所示。37第37页，本讲稿共71页算法算法7.4 广度优先搜索算法广度优先搜索算法BFS(int k)/广度优先搜索邻接矩阵表示的图广度优先搜索邻接矩阵表示的图int i,j;SETNULL(Q);/置空队列置空队列printf(%cn,g.vexsk);/访问出发点访问出发点vkvisitedk=TRUE;/标记标记vk已访问过已访问过ENQUEUE(Q,k);/已访问过的顶点入队已访问过的顶点入队w

39、hile(!EMPTY(Q)/队列非空时队列非空时i=DEQUEUE(Q);/队首元素出队队首元素出队for(j=0;jadjvex)printf(%cn,glp-adjvex.vertex);visitedp-adjvex=TRUE;/访问过的顶点入队访问过的顶点入队ENQUEUE(Q,p-adjvex);p=p-next;/找找vi的下一个邻接点的下一个邻接点39第39页，本讲稿共71页 分分析析上上述述算算法法，每每个个顶顶点点至至多多进进一一次次队队列列。遍遍历历图图的的过过程程实实质质是是通通过过边边或或弧弧找找邻邻接接点点的的过过程程，因因此此广广度度优优先先搜搜索索遍遍历历图图的

40、的时时间间复复杂杂度度和和深深度度优优先先搜搜索索遍遍历历相相同同，两两者不同之处仅仅在于对顶点访问的顺序不同。者不同之处仅仅在于对顶点访问的顺序不同。40第40页，本讲稿共71页7.4 最小生成树最小生成树最小生成树的基本概念最小生成树的基本概念构造最小生成树的构造最小生成树的Prim算法算法41第41页，本讲稿共71页7.4.1 最小生成树的基本概念最小生成树的基本概念 由由生生成成树树的的定定义义可可知知，无无向向连连通通图图的的生生成成树树不不是是唯唯一一的的。连连通通图图的的一一次次遍遍历历所所经经过过的的向向前前边边的的集集合合及及图图中中所所有有顶顶点点的的集集合合就就构构成成了

41、了该该图图的的一一棵棵生生成成树树，对对连连通通图图的的不不同同遍遍历历，如如遍遍历历出出发发点点不不同同或或存存储储点点的的顺顺序序不不同同，就就可可能能得得到到不不同同的的生生成成树树。下下图图(a)、(b)和和(c)所所示示的均为无向连通图的均为无向连通图G5的生成树。的生成树。42第42页，本讲稿共71页 可可以以证证明明，对对于于有有n个个顶顶点点的的无无向向连连通通图图，无无论论其其生生成成树树的形态如何，所有生成树中都有且仅有的形态如何，所有生成树中都有且仅有n-1条边。条边。如如果果无无向向连连通通图图是是一一个个网网，那那么么，它它的的所所有有生生成成树树中中必必有有一一棵棵

42、边边的的权权值值总总和和最最小小的的生生成成树树，我我们们称称这这棵棵生生成成树树为为最小生成树，简称为最小生成树。最小生成树，简称为最小生成树。最最小小生生成成树树的的概概念念可可以以应应用用到到许许多多实实际际问问题题中中。例例如如有有这这样样一一个个问问题题：以以尽尽可可能能低低的的总总造造价价建建造造城城市市间间的的通通讯讯网网络络，把把十十个个城城市市联联系系在在一一起起。在在这这十十个个城城市市中中，任任意意两两个个城城市市之之间间都都可可以以建建造造通通讯讯线线路路，通通讯讯线线路路的的造造价价依依据据城城市市间间的的距距离离不不同同而而有有不不同同的的造造价价，可可以以构构造造

43、一一个个通通讯讯线线路路造造价价网网络络，在在网网络络中中，每每个个顶顶点点表表示示城城市市，顶顶点点之之间间的的边边表表示示城城市市之之间间可可构构造造通通讯讯线线路路，每每条条边边的的权权值值表表示示该该条条通通讯讯线线路路的的造造价价，要要想想使使总总的的造造价价最最低低，实实际际上上就就是是寻寻找找该该网网络的最小生成树。络的最小生成树。43第43页，本讲稿共71页7.4.2 构造最小生成树的构造最小生成树的Prim算法算法 假假设设G（V，E）为为一一网网图图，其其中中V为为网网图图中中所所有有顶顶点点的的集集合合，E为为网网图图中中所所有有带带权权边边的的集集合合。设设置置两两个个

44、新新的的集集合合U和和T，其其中中集集合合U用用于于存存放放G的的最最小小生生成成树树中中的的顶顶点点，集集合合T存存放放G的的最最小小生生成成树树中中的的边边。令令集集合合U的的初初值值为为Uu1（假假设设构构造造最最小小生生成成树树时时，从从顶顶点点u1出出发发），集集合合T的的初初值值为为T。Prim算算法法的的思思想想是是:从所有uU，vVU的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到UV时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。44第44页，本讲稿共71页 Prim算算法法可可用用下下述述过过程程描描

45、述述，其其中中用用wuv表表示示顶顶点点u与与顶点顶点v边上的权值。边上的权值。Uu1,T=;while(UV)do (u，v)minwuv；uU，vVU TT(u，v)UUv 结束。结束。45第45页，本讲稿共71页 下图(a)所示的一个网图，按照Prim方法，从顶点1出发，该网的最小生成树的产生过程如图(b)、(c)、(d)、(e)、(f)和(g)所示。46第46页，本讲稿共71页 为为实实现现Prim算算法法，需需设设置置两两个个辅辅助助一一维维数数组组lowcost和和closevert，其其中中lowcost用用来来保保存存集集合合VU中中各各顶顶点点与与集集合合U中中各各顶顶点点构

46、构成成的的边边中中具具有有最最小小权权值值的的边边的的权权值值；数数组组closevertex用用来来保保存存依依附附于于该该边边的的在在集集合合U中中的的顶顶点点。假假设设初初 始始 状状 态态 时时，U u1(u1为为 出出 发发 的的 顶顶 点点)，这这 时时 有有lowcost0=0，它它表表示示顶顶点点u1已已加加入入集集合合U中中，数数组组lowcost的的其其它它各各分分量量的的值值是是顶顶点点u1到到其其余余各各顶顶点点所所构构成成的的直直接接边边的的权权值值。然然后后不不断断选选取取权权值值最最小小的的边边（ui，uk）（uiU，ukVU），每每选选取取一一条条边边，就就将将

47、lowcost（k）置置为为0，表表示示顶顶点点uk已已加加入入集集合合U中中。由由于于顶顶点点uk从从集集合合VU进进入入集集合合U后后，这这两两个个集集合合的的内内容容发发生生了了变变化化，就就需需依依据据具具体体情情况况更更新新数数组组lowcost和和closevertex中中部部分分分分量量的的内内容容。最最后后closevertex中即为所建立的最小生成树。中即为所建立的最小生成树。47第47页，本讲稿共71页 当当无无向向网网采采用用二二维维数数组组存存储储的的邻邻接接矩矩阵阵存存储储时时，Prim算算法法的的C语言实现为：语言实现为：PRIM()/*从第一个顶点出发构造连通网络

48、从第一个顶点出发构造连通网络dist的最小生成树，的最小生成树，结果放在结果放在T中中*/int j,k,m,v,min,max10000;float d;edge e;for(j=1;jn;j+)/*构造初始候选紫边集构造初始候选紫边集*/Tj-1.formvex1;/*顶点顶点1是第一个加入树中的红点是第一个加入树中的红点*/Tj-1.endvexj+1;Tj-1.lengthdist0j;48第48页，本讲稿共71页for(k0;kn-1;k+)/*求第求第k条边条边*/minmax;for(jk;jn-1;j+)/*在候选紫边集中找最短紫边在候选紫边集中找最短紫边*/if(Tj.1en

49、gthmin)minTj.1ength;mj;/*Tm是当前最短紫边是当前最短紫边*/eTm;TmTk;Tke;/*Tk和和Tm交换后，交换后，Tk是第是第k条红色树边条红色树边*/vTk.endvex;/*v是新红点是新红点*/for(jk+1;jn-1;j+)/*调整候选紫边集调整候选紫边集*/ddistv-1Tj.endvex-1;if(dTj.1ength);Tj.lengthd;Tj.fromvexv;49第49页，本讲稿共71页7.5 7.5 最短路径最短路径从一个源点到其它各点的最短路径从一个源点到其它各点的最短路径每一对顶点之间的最短路径每一对顶点之间的最短路径50第50页，本

50、讲稿共71页最短路径问题是图的又一个比较典型的应用问题。例如，某一地最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个公路网，给定了该网内的区的一个公路网，给定了该网内的n个城市以及这些城市之间的相通个城市以及这些城市之间的相通公路的距离，能否找到城市公路的距离，能否找到城市A到城市到城市B之间一条举例最近的通路之间一条举例最近的通路呢？如果将城市用点表示，城市间的公路用边表示，公路的呢？如果将城市用点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，这个问题就可归结为在网图中，长度作为边的权值，那么，这个问题就可归结为在网图中，求点求点A到点到点B的所有路径中，边的权值