第七章 图精选文档.ppt

第七章第七章 图图1本讲稿第一页，共七十一页7.1 图的基本概念图的基本概念图的定义和术语图的定义和术语图的基本操作图的基本操作2本讲稿第二页，共七十一页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中中边边的的集集合合，集集合合E中中P(vi,vj)表表示示顶顶点点vi和和顶顶点点vj之之间间有有一一条条直直接接连连线线，即即偶偶对对(vi,vj)表示一条边。表示一条边。3本讲稿第三页，共七十一页2.图的相关术语图的相关术语 无无向向图图。在在一一个个图图中中，如如果果任任意意两两个个顶顶点点构构成成的的偶偶对对（vi,vj）E是是无无序序的的，即即顶顶点点之之间间的的连连线线没没有有方方向向，则则称称该该图图为为无向图。无向图。有有向向图图。在在一一个个图图中中，如如果果任任意意两两个个顶顶点点构构成成的的偶偶对对（vi,vj）E是是有有序序的的，即即顶顶点点之之间间的的连连线线是是有有方方向向的的，则则称称该该图图为为有有向向图。图。有向图G24本讲稿第四页，共七十一页 顶点、边、弧、弧头、弧尾。顶点、边、弧、弧头、弧尾。图中的数据元素图中的数据元素vi称为顶称为顶点点(vertex)；P(vi,vj)表示在顶点表示在顶点vi和顶点和顶点vj之间有一条直接连线。之间有一条直接连线。在无向图中称为边；有向图中称为弧。边用顶点的无序偶对（在无向图中称为边；有向图中称为弧。边用顶点的无序偶对（vi,vj）来表示，顶点）来表示，顶点vi和顶点和顶点vj互为邻接点；弧用顶点的有序偶对互为邻接点；弧用顶点的有序偶对来表示，有序偶对的第一个结点来表示，有序偶对的第一个结点vi称为始点（或弧尾），称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点在图中就是不带箭头的一端；有序偶对的第二个结点vj称为终点称为终点（或弧头），在图中就是带箭头的一端。（或弧头），在图中就是带箭头的一端。无向完全图。无向完全图。在一个无向图中，如果任意两顶点都有一条在一个无向图中，如果任意两顶点都有一条直接边相连接，则该图为无向完全图。在一个含有直接边相连接，则该图为无向完全图。在一个含有n个顶点的个顶点的无向完全图中，有无向完全图中，有n(n-1)/2条边。条边。有向完全图。有向完全图。在一个有向图中，如果任意两顶点之间都有在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则该图为有向完全图。在一个方向互为相反的两条弧相连接，则该图为有向完全图。在一个含有含有n个顶点的有向完全图中，有个顶点的有向完全图中，有n(n-1)条边。条边。5本讲稿第五页，共七十一页 顶点的度、入度、出度。顶点的度、入度、出度。顶点的度（顶点的度（degree）是指依附于）是指依附于某顶点某顶点v的边数，通常记为的边数，通常记为TD(v)。在有向图中，要区别顶点的。在有向图中，要区别顶点的入度与出度的概念。顶点入度与出度的概念。顶点v的入度是指以顶点的入度是指以顶点 为终点的弧的数目。为终点的弧的数目。记为记为ID(v)；顶点；顶点v出度是指以顶点出度是指以顶点v为始点的弧的数目，记为为始点的弧的数目，记为OD(v)。有。有TD(v)=ID(v)OD(v)。可以证明，对于具有可以证明，对于具有n个顶点、个顶点、e条边的图，顶点条边的图，顶点vi的度的度TD(vi)与与顶点的个数以及边的数目满足关系：顶点的个数以及边的数目满足关系：2e =6本讲稿第六页，共七十一页 (7)边的权、网图。边的权、网图。与边有关的数据信息称为权（与边有关的数据信息称为权（weight）。）。在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。边上带权的图称为网图或网络到后一个工程所需要的时间等等。边上带权的图称为网图或网络（network）。如果边是有方向的带权图，则就是一个有向网图。）。如果边是有方向的带权图，则就是一个有向网图。(8)路径、路径长度。路径、路径长度。顶点顶点vp到顶点到顶点vq之间的路径（之间的路径（path）是指顶点序列是指顶点序列vp,vi1,vi2,vim,vq。其中，（。其中，（vp,vi1），），(vi1,vi2)，,(vim,vq)分别为图中的边。路径上边的数目称为路径长度。分别为图中的边。路径上边的数目称为路径长度。7本讲稿第七页，共七十一页 (9)回路、简单路径、简单回路。回路、简单路径、简单回路。路径中第一个顶点与路径中第一个顶点与最后一个顶点相同的路径称为回路或者环（最后一个顶点相同的路径称为回路或者环（cycle）。序列中顶）。序列中顶点不重复出现的路径称为简单路径。除第一个顶点与最后点不重复出现的路径称为简单路径。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。或者简单环。(10)子图。子图。对于图对于图G=（V，E），），G=（V，E），若存在），若存在V是是V的子集的子集，E是是E的子集的子集，则称图，则称图G是是G的一个子图。下的一个子图。下图示出了图示出了G2和和G1的两个子图的两个子图G和和G。8本讲稿第八页，共七十一页(11)连连通通的的、连连通通图图、连连通通分分量量。在在无无向向图图中中，如如果果从从一一个个顶顶点点vi到到另另一一个个顶顶点点vj(ij)有有路路径径，则则称称顶顶点点vi和和vj是是连连通通的的。如如果果图图中中任任意意两两顶顶点点都都是是连连通通的的，则则称称该该图图是是连连通通图图。无无向向图图的的极极大大连连通通子子图图称称为为连连通通分分量量。下下图图(a)中中有有两两个个连连通通分分量量，如图如图(b)所示。所示。9本讲稿第九页，共七十一页 (12)强强连连通通图图、强强连连通通分分量量。对对于于有有向向图图来来说说，若若图图中中任任意意一一对对顶顶点点vi 和和vj(ij)均均有有从从一一个个顶顶点点vi到到另另一一个个顶顶点点vj有有路路径径，也也有有从从vj到到vi的的路路径径，则则称称该该有有向向图图是是强强连连通通图图。有有向向图图的极大强连通子图称为强连通分量。的极大强连通子图称为强连通分量。左左下下图图中中有有两两个个强强连连通通分分量量，分分别别是是v1,v3,v4和和v2，如如右右下下图所示。图所示。10本讲稿第十页，共七十一页 (13)生生成成树树。所所谓谓连连通通图图G的的生生成成树树，是是G的的包包含含其其全全部部n个个顶顶点点的的一一个个极极小小连连通通子子图图。它它必必定定包包含含且且仅仅包包含含G的的n-1条条边边。下图示出了图下图示出了图G1 的一棵生成树。的一棵生成树。(14)生生成成森森林林。在在非非连连通通图图中中，由由每每个个连连通通分分量量都都可可得得到到一一个个极极小小连连通通子子图图，即即一一棵棵生生成成树树。这这些些连连通通分分量量的的生生成成树树就就组组成成了一个非连通图的生成森林。了一个非连通图的生成森林。11本讲稿第十一页，共七十一页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中中，删删除除顶顶点点v以以及及所所有有和和顶顶点点v相相关关联联的边或弧。的边或弧。InsertArc（G，v，w）在在图图G中中增增添添一一条条从从顶顶点点v到到顶顶点点w的的边边或弧。或弧。DeleteArc（G，v，w）在在图图G中中删删除除一一条条从从顶顶点点v到到顶顶点点w的的边或弧。边或弧。12本讲稿第十二页，共七十一页DFSTraverse（G，v）在图在图G中，从顶点中，从顶点v出发深度优先遍历图出发深度优先遍历图G。BFSTraverse（G，v）在图在图G中，从顶点中，从顶点v出发广度优先遍历图出发广度优先遍历图G。LocateVex（G，u）在图在图G中找到顶点中找到顶点u，返回该顶点在图中位置。，返回该顶点在图中位置。FirstAdjVex（G，v）在图在图G中，返回中，返回v的第一个邻接点。若顶点的第一个邻接点。若顶点在在G中没有邻接顶点，则返回中没有邻接顶点，则返回“空空”。NextAdjVex（G，v，w）在图在图G中，返回中，返回v的的(相对于相对于w的的)下一个邻下一个邻接顶点。若接顶点。若w是是v的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。13本讲稿第十三页，共七十一页7.2 7.2 图的存储表示图的存储表示邻接矩阵邻接矩阵邻接表邻接表14本讲稿第十四页，共七十一页7.2.1 邻接矩阵邻接矩阵 所所谓谓邻邻接接矩矩阵阵（Adjacency Matrix）的的存存储储结结构构，就就是是用用一一维维数数组组存存储储图图中中顶顶点点的的信信息息，用用矩矩阵阵表表示示图图中中各各顶顶点点之之间间的的邻邻接接关关系系。假假设设图图G（V，E）有有n个个确确定定的的顶顶点点，即即Vv0,v1,vn-1,则则表表示示G中中各各顶顶点点相相邻邻关关系系为为一一个个n阶阶方方阵阵，矩矩阵的元素为：阵的元素为：Aij=若若G是网图，则邻接矩阵可定义为：是网图，则邻接矩阵可定义为：Aij=其其中中，wij表表示示边边(vi,vj)或或上上的的权权值值；表表示示一一个个计计算算机机允许的、大于所有边上权值的数。允许的、大于所有边上权值的数。1 若若(vi,vj)或或是是E(G)中的边中的边0 若若(vi,vj)或或不是不是E(G)中的边中的边wij 若若(vi,vj)或或是是E(G)中的边中的边0或或 若若(vi,vj)或或不是不是E(G)中的边中的边15本讲稿第十五页，共七十一页 用邻接矩阵表示法表示的无向图和网图如下图所示。16本讲稿第十六页，共七十一页 从图的邻接矩阵存储方法容易看出这种表示具有以下特点：从图的邻接矩阵存储方法容易看出这种表示具有以下特点：无无向向图图的的邻邻接接矩矩阵阵一一定定是是一一个个对对称称矩矩阵阵。因因此此，在在具具体体存存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。对对于于无无向向图图，邻邻接接矩矩阵阵的的第第i i行行（或或第第i i列列）非非零零元元素素（或或非非元素）的个数正好是第元素）的个数正好是第i i个顶点的度个顶点的度TD(vi)TD(vi)。对对于于有有向向图图，邻邻接接矩矩阵阵的的第第i i行行（或或第第i i列列）非非零零元元素素（或或非非元元素素）的的个个数数正正好好是是第第i i个个顶顶点点的的出出度度OD(vi)OD(vi)（或或入入度度ID(vi)ID(vi)）。）。用用邻邻接接矩矩阵阵方方法法存存储储图图，很很容容易易确确定定图图中中任任意意两两个个顶顶点点之之间间是是否否有有边边相相连连；但但是是，要要确确定定图图中中有有多多少少条条边边，则则必必须须按按行行、按按列列对对每每个个元元素素进进行行检检测测，所所花花费费的的时时间间代代价价很很大大。这这是是用用邻邻接接矩矩阵阵存存储储图的局限性。图的局限性。17本讲稿第十七页，共七十一页 在在用用邻邻接接矩矩阵阵存存储储图图时时，除除了了用用一一个个二二维维数数组组存存储储用用于于表表示示顶顶点点间间相相邻邻关关系系的的邻邻接接矩矩阵阵外外，还还需需用用一一个个一一维维数数组组来来存存储储顶顶点点信信息息，另另外外还还有有图图的的顶顶点点数数和和边边数数。故故可可将将其其形形式式描描述如下：述如下：#define n 6/图的顶点数图的顶点数#define e 8/图的边（弧）数图的边（弧）数typedef char vextype;/顶点的数据类型顶点的数据类型typedef float adjtype;/权值类型权值类型typedef structvextype vexsn;/顶点表顶点表adjtype arcsnn;/邻接矩阵，即边表邻接矩阵，即边表int n,e;graph;/graph是以邻接矩阵存储的图类型是以邻接矩阵存储的图类型18本讲稿第十八页，共七十一页 建立一个图的邻接矩阵存储的算法如下：建立一个图的邻接矩阵存储的算法如下：算法算法7.1 无向网络的建立无向网络的建立CREATGRAPH(graph*ga)int i,j,k;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本讲稿第十九页，共七十一页7.2.2 邻接表邻接表 邻接表邻接表(Adjacency List)是图的一种顺序存储与链式存储是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图就是对于图G中的每个顶点中的每个顶点vi，将所有邻接于，将所有邻接于vi的顶点的顶点vj链成一链成一个单链表，这个单链表就称为顶点个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。邻接表表头放到数组中，就构成了图的邻接表。20本讲稿第二十页，共七十一页 在邻接表表示中有两种结点结构，如下图所示。在邻接表表示中有两种结点结构，如下图所示。一一种种是是顶顶点点表表的的结结点点结结构构，它它由由顶顶点点域域（vertex）和和指指向向第第一一条条邻邻接接边边的的指指针针域域（firstedge）构构成成，另另一一种种是是边边表表（即即邻邻接接表表）结结点点，它它由由邻邻接接点点域域(adjvex)和和指指向向下下一一条条邻邻接接边边的的指指针针域域(next)构构成成。对对于于网网图图的的边边表表需需再再增增设设一一个个存存储储边边上上信信息息（如如权权值值等等）的域（的域（info），网图的边表结构如下图所示。），网图的边表结构如下图所示。21本讲稿第二十一页，共七十一页 下图给出无向图及对应的邻接表表示。下图给出无向图及对应的邻接表表示。22本讲稿第二十二页，共七十一页邻接表表示的形式描述如下：邻接表表示的形式描述如下：typedef struct nodeint adjvex;/*邻接点域邻接点域*/struct node*next;/*指向下一个邻接点的指针域指向下一个邻接点的指针域*/*若要表示边上信息，则应增加一个数据域若要表示边上信息，则应增加一个数据域info*/EdgeNode;/*边表结点边表结点*/typedef struct vnodeVertexType vertex;/*顶点域顶点域*/EdgeNode*firstedge;/*边表头指针边表头指针*/VerNode;/*顶点表结点顶点表结点*/VerNode gan;23本讲稿第二十三页，共七十一页算法算法7.2 无向图邻接表的建立无向图邻接表的建立CREATADJLIST(VexNode ga)/*建立无向图的邻接表建立无向图的邻接表*/int i,j,k;EdgeNode*s;for(i=0;in;i+)/*读入顶点信息读入顶点信息*/gai.vertex=getchar();gai.firstedge=NULL;/*边表头指针初始化边表头指针初始化*/for(k=0;kadjvex=j;s-next=gai.firstedge;gai.firstedge=s;/*将将*s插入顶点插入顶点vi的边表头部的边表头部*/24本讲稿第二十四页，共七十一页 若若无无向向图图中中有有n个个顶顶点点、e条条边边，则则它它的的邻邻接接表表需需n个个头头结结点点和和2e个个表表结结点点。显显然然，在在边边稀稀疏疏(en(n-1)/2)的的情情况况下下，用用邻邻接接表表表表示示图图比比邻邻接接矩矩阵阵节节省省存存储储空空间间，当当和和边边相相关关的的信信息息较较多多时更是如此。时更是如此。在在无无向向图图的的邻邻接接表表中中，顶顶点点vi的的度度恰恰为为第第i个个链链表表中中的的结结点点数数；而而在在有有向向图图中中，第第i个个链链表表中中的的结结点点个个数数只只是是顶顶点点vi的的出出度度，为为求求入入度度，必必须须遍遍历历整整个个邻邻接接表表。在在所所有有链链表表中中其其邻邻接接点点域域的的值值为为i的的结结点点的的个个数数是是顶顶点点vi的的入入度度。有有时时，为为了了便便于于确确定定顶顶点点的的入入度度或或以以顶顶点点vi为为头头的的弧弧，可可以以建建立立一一个个有有向向图图的的逆逆邻邻接接表表，即对每个顶点即对每个顶点vi 建立一个链接以建立一个链接以vi为头的弧的链表。为头的弧的链表。25本讲稿第二十五页，共七十一页 下图所示为有向图下图所示为有向图G2的邻接表和逆邻接表。的邻接表和逆邻接表。26本讲稿第二十六页，共七十一页 在在建建立立邻邻接接表表或或逆逆邻邻接接表表时时，若若输输入入的的顶顶点点信信息息即即为为顶顶点点的的编编号号，则则建建立立邻邻接接表表的的复复杂杂度度为为O（n+e），否否则则，需需要要通通过过查查找找才才能能得得到到顶顶点点在在图图中中位位置置，则则时时间间复复杂杂度度为为O（ne）。）。在在邻邻接接表表上上容容易易找找到到任任一一顶顶点点的的第第一一个个邻邻接接点点和和下下一一个个邻邻接接点点，但但要要判判定定任任意意两两个个顶顶点点（vi 和和vj）之之间间是是否否有有边边或或弧弧相相连连，则需搜索第则需搜索第i个或第个或第j个链表，因此，不及邻接矩阵方便。个链表，因此，不及邻接矩阵方便。27本讲稿第二十七页，共七十一页7.3 图的遍历图的遍历深度优先搜索深度优先搜索广度优先搜索广度优先搜索28本讲稿第二十八页，共七十一页 图图的的遍遍历历是是指指从从图图中中的的任任一一顶顶点点出出发发，对对图图中中的的所所有有顶顶点点访访问问一一次次且且只只访访问问一一次次。图图的的遍遍历历是是图图的的一一种种基基本本操操作作，图图的的许许多多其其它它操操作作都是建立在遍历操作的基础之上。都是建立在遍历操作的基础之上。由由于于图图结结构构本本身身的的复复杂杂性性，所所以以图图的的遍遍历历操操作作也也较较复复杂杂，主主要要表表现现在在以下四个方面：以下四个方面：在在图图结结构构中中，没没有有一一个个“自自然然”的的首首结结点点，图图中中任任意意一一个个顶顶点都可作为第一个被访问的结点。点都可作为第一个被访问的结点。在在非非连连通通图图中中，从从一一个个顶顶点点出出发发，只只能能够够访访问问它它所所在在的的连连通通分分量量上上的的所所有有顶顶点点，因因此此，还还需需考考虑虑如如何何选选取取下下一一个个出出发发点点以以访访问图中其余的连通分量。问图中其余的连通分量。在在图图结结构构中中，如如果果有有回回路路存存在在，那那么么一一个个顶顶点点被被访访问问之之后后，有有可能沿回路又回到该顶点。可能沿回路又回到该顶点。在在图图结结构构中中，一一个个顶顶点点可可以以和和其其它它多多个个顶顶点点相相连连，当当这这样样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。的顶点访问过后，存在如何选取下一个要访问的顶点的问题。29本讲稿第二十九页，共七十一页7.3.1 深度优先搜索 深深度度优优先先搜搜索索（Depth_First Search）遍遍历历类类似似于于树树的的先先根根遍历，是树的先根遍历的推广。遍历，是树的先根遍历的推广。假假设设初初始始状状态态是是图图中中所所有有顶顶点点未未曾曾被被访访问问，则则深深度度优优先先搜搜索索可可从从图图中中某某个个顶顶点点发发v出出发发，访访问问此此顶顶点点，然然后后依依次次从从v的的未未被被访访问问的的邻邻接接点点出出发发深深度度优优先先遍遍历历图图，直直至至图图中中所所有有和和v有有路路径径相相通通的的顶顶点点都都被被访访问问到到；若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中中所所有有顶顶点点都被访问到为止。都被访问到为止。30本讲稿第三十页，共七十一页 以以下下图图的的无无向向图图G5为为例例，进进行行图图的的深深度度优优先先搜搜索索。假假设设从从顶顶点点v1出出发发进进行行搜搜索索，在在访访问问了了顶顶点点v1之之后后，选选择择邻邻接接点点v2。因因为为v2未未曾曾访访问问，则则从从v2出出发发进进行行搜搜索索。依依次次类类推推，接接着着从从v4、v8、v5 出出发发进进行行搜搜索索。在在访访问问了了v5之之后后，由由于于v5的的邻邻接接点点都都已已被被访访问问，则则搜搜索索回回到到 v8。由由于于同同样样的的理理由由，搜搜索索继继续续回回到到v4，v2直直至至v1，此此时时由由于于v1的的另另一一个个邻邻接接点点未未被被访访问问，则则搜搜索索又又从从v1到到v3，再继续进行下去由此，得到的顶点访问序列为：，再继续进行下去由此，得到的顶点访问序列为：v1 v2 v4v8 v5 v3v6v731本讲稿第三十一页，共七十一页 显显然然，这这是是一一个个递递归归的的过过程程。为为了了在在遍遍历历过过程程中中便便于于区区分分顶顶点点是是否否已已被被访访问问，需需附附设设访访问问标标志志数数组组visitedn，其其初初值值为为FALSE，一旦某个顶点被访问，则其相应的分量置为一旦某个顶点被访问，则其相应的分量置为TRUE。算法算法7.3 深度优先搜索算法深度优先搜索算法int visitednGraph g;DFS(int i)int j;printf(node:%cn,g.vexsi);/*访问顶点访问顶点Vi*/visitedi=TRUE;/*标记标记Vi已访问已访问*/for(j=0;jadjvex)DFSL(p-adjvex);p=p-next;/*找找Vi的下一个邻接点的下一个邻接点*/33本讲稿第三十三页，共七十一页 分分析析上上述述算算法法，在在遍遍历历时时，对对图图中中每每个个顶顶点点至至多多调调用用一一次次DFS 函函数数，因因为为一一旦旦某某个个顶顶点点被被标标志志成成已已被被访访问问，就就不不再再从从它它出出发发进进行行搜搜索索。因因此此，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程。其其耗耗费费的的时时间间则则取取决决于于所所采采用用的的存存储储结结构构。当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵图图的的存存储储结结构构时时，查查找找每每个个顶顶点点的的邻邻接接点点所所需需时时间间为为O(n2)，其其中中n为为图图中中顶顶点点数数。而而当当以以邻邻接接表表作作图图的的存存储储结结构构时时，找找邻邻接接点点所所需需时时间间为为O(e)，其其中中e为为无无向向图图中中边边的的数数或或有有向向图图中中弧弧的的数数。由由此此，当当以以邻邻接接表表作作存存储储结结构构时时，深深度度优优先先搜搜索索遍遍历历图图的的时时间间复复杂度为杂度为O(n+e)。34本讲稿第三十四页，共七十一页7.3.2 广度优先搜索广度优先搜索 广广度度优优先先搜搜索索（Breadth_First Search）遍遍历历类类似似于于树树的的按按层次遍历的过程。层次遍历的过程。假假设设从从图图中中某某顶顶点点v出出发发，在在访访问问了了v之之后后依依次次访访问问v的的各各个个未未曾曾访访问问过过和和邻邻接接点点，然然后后分分别别从从这这些些邻邻接接点点出出发发依依次次访访问问它它们们的的邻邻接接点点，并并使使“先先被被访访问问的的顶顶点点的的邻邻接接点点”先先于于“后后被被访访问问的的顶顶点点的的邻邻接接点点”被被访访问问，直直至至图图中中所所有有已已被被访访问问的的顶顶点点的的邻邻接接点点都都被被访访问问到到。若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中中所所有有顶顶点点都都被被访访问问到到为为止止。换换句句话话说说，广广度度优优先先搜搜索索遍遍历历图图的的过过程程中中以以v为为起起始始点点，由由近近至至远远，依依次次访访问问和和v有有路路径径相相通通且且路路径径长度为长度为1,2,的顶点。的顶点。35本讲稿第三十五页，共七十一页 例例如如，对对下下图图所所示示无无向向图图G5 进进行行广广度度优优先先搜搜索索遍遍历历，首首先先访访问问v1 和和v1的的邻邻接接点点v2和和v3，然然后后依依次次访访问问v2 的的邻邻接接点点v4 和和v5 及及v3 的的邻邻接接点点v6和和v7，最最后后访访问问v4 的的邻邻接接点点v8。由由于于这这些些顶顶点点的的邻邻接接点点均均已已被被访访问问，并并且且图图中中所所有有顶顶点点都都被被访访问问，由由些些完完成了图的遍历。得到的顶点访问序列为：成了图的遍历。得到的顶点访问序列为：v1v2 v3 v4 v5 v6 v7 v836本讲稿第三十六页，共七十一页 和和深深度度优优先先搜搜索索类类似似，在在遍遍历历的的过过程程中中也也需需要要一一个个访访问问标标志志数数组组。并并且且，为为了了顺顺次次访访问问路路径径长长度度为为2、3、的的顶顶点点，需附设队列以存储已被访问的路径长度为需附设队列以存储已被访问的路径长度为1、2、的顶点。的顶点。从从图图的的某某一一点点v出出发发，递递归归地地进进行行广广度度优优先先遍遍历历的的过过程程如如算算法法所所示。示。37本讲稿第三十七页，共七十一页算法算法7.4 广度优先搜索算法广度优先搜索算法BFS(int k)/广度优先搜索邻接矩阵表示的图广度优先搜索邻接矩阵表示的图int i,j;SETNULL(Q);/置空队列置空队列printf(%cn,g.vexsk);/访问出发点访问出发点vkvisitedk=TRUE;/标记标记vk已访问过已访问过ENQUEUE(Q,k);/已访问过的顶点入队已访问过的顶点入队while(!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本讲稿第三十九页，共七十一页 分分析析上上述述算算法法，每每个个顶顶点点至至多多进进一一次次队队列列。遍遍历历图图的的过过程程实实质质是是通通过过边边或或弧弧找找邻邻接接点点的的过过程程，因因此此广广度度优优先先搜搜索索遍遍历历图图的的时时间间复复杂杂度度和和深深度度优优先先搜搜索索遍遍历历相相同同，两两者者不不同同之处仅仅在于对顶点访问的顺序不同。之处仅仅在于对顶点访问的顺序不同。40本讲稿第四十页，共七十一页7.4 最小生成树最小生成树最小生成树的基本概念最小生成树的基本概念构造最小生成树的构造最小生成树的Prim算法算法41本讲稿第四十一页，共七十一页7.4.1 最小生成树的基本概念最小生成树的基本概念 由由生生成成树树的的定定义义可可知知，无无向向连连通通图图的的生生成成树树不不是是唯唯一一的的。连连通通图图的的一一次次遍遍历历所所经经过过的的向向前前边边的的集集合合及及图图中中所所有有顶顶点点的的集集合合就就构构成成了了该该图图的的一一棵棵生生成成树树，对对连连通通图图的的不不同同遍遍历历，如如遍遍历历出出发发点点不不同同或或存存储储点点的的顺顺序序不不同同，就就可可能能得得到到不不同同的的生生成成树树。下下图图(a)、(b)和和(c)所所示示的的均均为为无无向向连连通通图图G5的的生生成树。成树。42本讲稿第四十二页，共七十一页 可可以以证证明明，对对于于有有n个个顶顶点点的的无无向向连连通通图图，无无论论其其生生成成树树的的形形态如何，所有生成树中都有且仅有态如何，所有生成树中都有且仅有n-1条边。条边。如如果果无无向向连连通通图图是是一一个个网网，那那么么，它它的的所所有有生生成成树树中中必必有有一一棵棵边边的的权权值值总总和和最最小小的的生生成成树树，我我们们称称这这棵棵生生成成树树为为最最小小生生成成树树，简称为最小生成树。简称为最小生成树。最最小小生生成成树树的的概概念念可可以以应应用用到到许许多多实实际际问问题题中中。例例如如有有这这样样一一个个问问题题：以以尽尽可可能能低低的的总总造造价价建建造造城城市市间间的的通通讯讯网网络络，把把十十个个城城市市联联系系在在一一起起。在在这这十十个个城城市市中中，任任意意两两个个城城市市之之间间都都可可以以建建造造通通讯讯线线路路，通通讯讯线线路路的的造造价价依依据据城城市市间间的的距距离离不不同同而而有有不不同同的的造造价价，可可以以构构造造一一个个通通讯讯线线路路造造价价网网络络，在在网网络络中中，每每个个顶顶点点表表示示城城市市，顶顶点点之之间间的的边边表表示示城城市市之之间间可可构构造造通通讯讯线线路路，每每条条边边的的权权值值表表示示该该条条通通讯讯线线路路的的造造价价，要要想使总的造价最低，实际上就是寻找该网络的最小生成树。想使总的造价最低，实际上就是寻找该网络的最小生成树。43本讲稿第四十三页，共七十一页7.4.2 构造最小生成树的构造最小生成树的Prim算法算法 假假设设G（V，E）为为一一网网图图，其其中中V为为网网图图中中所所有有顶顶点点的的集集合合，E为为网网图图中中所所有有带带权权边边的的集集合合。设设置置两两个个新新的的集集合合U和和T，其其中中集集合合U用用于于存存放放G的的最最小小生生成成树树中中的的顶顶点点，集集合合T存存放放G的的最最小小生生成成树树中中的的边边。令令集集合合U的的初初值值为为Uu1（假假设设构构造造最最小小生生成成树树时时，从从顶顶点点u1出出发发），集集合合T的的初初值值为为T。Prim算算法法的的思思想想是是:从所有uU，vVU的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到UV时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。44本讲稿第四十四页，共七十一页 Prim算算法法可可用用下下述述过过程程描描述述，其其中中用用wuv表表示示顶顶点点u与与顶顶点点v边边上上的权值。的权值。Uu1,T=;while(UV)do (u，v)minwuv；uU，vVU TT(u，v)UUv 结束。结束。45本讲稿第四十五页，共七十一页 下图(a)所示的一个网图，按照Prim方法，从顶点1出发，该网的最小生成树的产生过程如图(b)、(c)、(d)、(e)、(f)和(g)所示。46本讲稿第四十六页，共七十一页 为为实实现现Prim算算法法，需需设设置置两两个个辅辅助助一一维维数数组组lowcost和和closevert，其其中中lowcost用用来来保保存存集集合合VU中中各各顶顶点点与与集集合合U中中各各顶顶点点构构成成的的边边中中具具有有最最小小权权值值的的边边的的权权值值；数数组组closevertex用用来来保保存存依依附附于于该该边边的的在在集集合合U中中的的顶顶点点。假假设设初初始始状状态态时时，Uu1(u1为为出出发发的的顶顶点点)，这这时时有有lowcost0=0，它它表表示示顶顶点点u1已已加加入入集集合合U中中，数数组组lowcost的的其其它它各各分分量量的的值值是是顶顶点点u1到到其其余余各各顶顶点点所所构构成成的的直直接接边边的的权权值值。然然后后不不断断选选取取权权值值最最小小的的边边（ui，uk）（uiU，ukVU），每每选选取取一一条条边边，就就将将lowcost（k）置置为为0，表表示示顶顶点点uk已已加加入入集集合合U中中。由由于于顶顶点点uk从从集集合合VU进进入入集集合合U后后，这这两两个个集集合合的的内内容容发发生生了了变变化化，就就需需依依据据具具体体情情况况更更新新数数组组lowcost和和closevertex中中部部分分量的内容。最后分分量的内容。最后closevertex中即为所建立的最小生成树。中即为所建立的最小生成树。47本讲稿第四十七页，共七十一页 当当无无向向网网采采用用二二维维数数组组存存储储的的邻邻接接矩矩阵阵存存储储时时，Prim算算法法的的C语语言言实现为：实现为：PRIM()/*从第一个顶点出发构造连通网络从第一个顶点出发构造连通网络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本讲稿第四十八页，共七十一页for(k0;kn-1;k+)/*求第求第k条边条边*/minmax;for(jk;jn-1;j+)/*在候选紫边集中找最短紫边在候选紫边集中找最短紫边*/if(Tj.1engthmin)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本讲稿第四十九页，共七十一页7.5 7.5 最短路径最短路径从一个源点到其它各点的最短路径从一个源点到其它各点的最短路径每一对顶点之间的最短路径每一对顶点之间的最短路径50本讲稿第五十页，共七十一页最短路径问题是图的又一个比较典型的应用问题。例如，某最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个公路网，给定了该网内的一地区的一个公路网，给定了该网内的n个城市以及这些城市个城市以及这些城市之间的相通公路的距离，能否找到城市之间的相通公路的距离，能否找到城市A到城市到城市B之间一条举例之间一条举例最近的通路呢？如果将城市用点表示，城市间的公路用边表最近的通路呢？如果将城市用点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，