C语言数据结构第讲图.pptx

第7章 图知 识 点图的逻辑结构及基本术语图的逻辑结构及基本术语邻接矩阵和邻接表的存储结构和特点邻接矩阵和邻接表的存储结构和特点深度优先搜索和广度优先搜索两种遍历算法深度优先搜索和广度优先搜索两种遍历算法图的连通性和生成树的概念图的连通性和生成树的概念最短路径的含义及求最短路径的算法最短路径的含义及求最短路径的算法难难点点图的遍历图的遍历最小生成树最小生成树最短路径最短路径要要求求熟练掌握以下内容：熟练掌握以下内容：图的存储结构图的存储结构图的遍历算法图的遍历算法了解以下内容：了解以下内容：图的最小生成树和求最小生成树算法图的最小生成树和求最小生成树算法带权有向图的最短路径问题带权有向图的最短路径问题第7章 目录7-1 7-1 图的定义和术语图的定义和术语7-2 7-2 图的存储表示图的存储表示7-3 7-3 图的遍历图的遍历7-4 7-4 图的连通性图的连通性7-5 7-5 最短路径最短路径小小 结结实验实验7 7 图子系统图子系统习题习题7 77-1 图的定义和术语 图图（GraphGraph）是是一一种种比比树树形形结结构构更更复复杂杂的的非非线线性性结结构构。在在图图形形结结构构中中，每每个个结结点点都都可可以以有有多多个个直直接接前前驱驱和和多多个个直直接接后后继。继。7-1 7-1 图的定义和术语图的定义和术语7-1-1 7-1-1 图的定义图的定义 图图（GraphGraph）是是由由非非空空的的顶顶点点（VerticesVertices）集集合合和和一一个个描描述述顶顶点点之之间间关关系系边边（EdgesEdges）的的有有限限集集合合组组成成的的一一种种数数据据结构。可以用二元组定义为：结构。可以用二元组定义为：G G（V V，E E）其其中中，G G表表示示一一个个图图，V V是是图图G G中中顶顶点点的的集集合合，E E是是图图G G中中边边的集合。的集合。图图7-1无向图无向图G1图图7-2有向图有向图G G2 2 V1V3V2V4V5V1V3V2V4 G1=（V，E）Vv1,v2,v3,v4,v5；E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)。(v(vi i,v,vj j)表示顶点表示顶点v vi i和顶点和顶点v vj j之间有一之间有一条无向直接连线，也称为边。条无向直接连线，也称为边。G2=(V,E)V=v1,v2,v3,v4E=,表示顶点表示顶点vi和顶点和顶点vj之间有一条之间有一条有向直接连线，也称为弧。其中有向直接连线，也称为弧。其中vi称称为弧尾，为弧尾，vj称为弧头。称为弧头。7-1-2 7-1-2 图的相关术语图的相关术语（1 1）无向图（）无向图（UndigraphUndigraph）在在一一个个图图中中，如如果果每每条条边边都都没没有有方方向向（如如图图7-17-1），则称该图为无向图。则称该图为无向图。（2 2）有向图（）有向图（DigraphDigraph）在在一一个个图图中中，如如果果每每条条边边都都有有方方向向（如如图图7-27-2），则则称该图为有向图。称该图为有向图。（3 3）无向完全图）无向完全图 在在一一个个无无向向图图中中，如如果果任任意意两两顶顶点点都都有有一一条条直直接接边边相相连连接接，则则称称该该图图为为无无向向完完全全图图。可可以以证证明明，在在一一个个含含有有n n个顶点的无向完全图中，有个顶点的无向完全图中，有n(n-1)/2n(n-1)/2条边。条边。（4 4）有向完全图）有向完全图 在在一一个个有有向向图图中中，如如果果任任意意两两顶顶点点之之间间都都有有方方向向互互为为相相反反的的两两条条弧弧相相连连接接，则则称称该该图图为为有有向向完完全全图图。在在一一个个含含有有n n个顶点的有向完全图中，有个顶点的有向完全图中，有n(n-1)n(n-1)条弧。条弧。（5 5）稠密图、稀疏图）稠密图、稀疏图 我我们们称称边边数数很很多多的的图图为为稠稠密密图图；称称边边数数很很少少的的图图为为稀稀疏图。疏图。（6 6）顶点的度）顶点的度 在在无无向向图图中中：一一个个顶顶点点拥拥有有的的边边数数，称称为为该该顶顶点点的的度度。记为记为TD(v)TD(v)。在有向图中：在有向图中：(a)一个顶点拥有的弧头的数目，称为该顶点的入度，一个顶点拥有的弧头的数目，称为该顶点的入度，记为记为ID(v)；(b)一个顶点拥有的弧尾的数目，称为该顶点的出度，一个顶点拥有的弧尾的数目，称为该顶点的出度，记为记为OD(v)；(c)一个顶点度等于顶点的入度一个顶点度等于顶点的入度+出度，出度，即：即：TD(v)=ID(v)OD(v)。在图在图7-1的的G1中有：中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在图在图7-2的的G2中有：中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2 可可以以证证明明，对对于于具具有有n n个个顶顶点点、e e条条边边的的图图，顶顶点点v vi i的的度度TD(vTD(vi i)与顶点的个数以及边的数目满足关系：与顶点的个数以及边的数目满足关系：（7 7）权）权 图图的的边边或或弧弧有有时时具具有有与与它它有有关关的的数数据据信信息息，这这个个数数据据信息就称为权（信息就称为权（WeightWeight）。）。ACBD58697（8 8）网）网边（或弧）上带权边（或弧）上带权的图称为网（的图称为网（NetworkNetwork）。）。如图如图7-37-3所示，就是一个无所示，就是一个无向网。如果边是有方向的带权向网。如果边是有方向的带权图，则就是一个有向网。图，则就是一个有向网。图图7-3一个无向网示意一个无向网示意图图7-3一个无向网示意一个无向网示意（9 9）路径、路径长度）路径、路径长度 顶点顶点v vi i到顶点到顶点v vj j之间的路径是指顶点序列之间的路径是指顶点序列v vi i,v,vi1i1,v,vi2i2,v,vimim,v,vj.j.。其中，（。其中，（v vi i,v,vi1i1），），(v(vi1i1,v,vi2i2)，,(v(vimim,.v,.vj j)分别为图中的边。路径上边的数目称为路径长度。分别为图中的边。路径上边的数目称为路径长度。在在图图7-17-1的的无无向向图图G1G1中中，v v1 1vv4 4vv3 3vv5 5与与v v1 1vv2 2vv5 5是是从顶点从顶点v v1 1 到顶点到顶点v v5 5 的两条路径，路径长度分别为的两条路径，路径长度分别为3 3和和2 2。（1010）回路、简单路径、简单回路）回路、简单路径、简单回路 在在一一条条路路径径中中，如如果果其其起起始始点点和和终终止止点点是是同同一一顶顶点点，则则称称其其为为回回路路或或者者环环。如如果果一一条条路路径径上上所所有有顶顶点点除除起起始始点点和和终终止点外彼此都是不同的，则称该路径为简单路径。止点外彼此都是不同的，则称该路径为简单路径。在在图图7-17-1中中，前前面面提提到到的的v v1 1到到v v5 5的的两两条条路路径径都都为为简简单单路路径径。除除起起始始点点和和终终止止点点外外，其其他他顶顶点点不不重重复复出出现现的的回回路路称称为为简简单回路，或者简单环。如图单回路，或者简单环。如图7-27-2中的中的v v1 1vv3 3vv4 4vv1 1。（1111）子图）子图 对对于于图图G=G=（V V，E E），G G=（V V，E E），若若存存在在V V是是V V的子集的子集 ，E E是是E E的子集的子集 ，则称图，则称图G G是是G G的一个子图。的一个子图。图图7-47-4示出了示出了G G1 1和和G G2 2的子图。的子图。图图7-4图图G1和和G2的两个子图示意的两个子图示意(a)G1的子图的子图(b)G2的子图的子图V1V3V2V1V3V2V4V5V1V3V2V4V5图图7-1无向图无向图G1（1212）连通图、连通分量）连通图、连通分量 在在无无向向图图中中，如如果果从从一一个个顶顶点点v vi i到到另另一一个个顶顶点点v vj j(ij)(ij)有有路路径径，则则称称顶顶点点v vi i和和v vj j是是连连通通的的。任任意意两两顶顶点点都都是是连连通通的的图图称称为为连连通通图图。无无向向图图的的极极大大连连通通子子图图称称为为连连通通分分量量。图图7-5(7-5(a)a)中有两个连通分量，如图中有两个连通分量，如图7-5(7-5(b)b)所示。所示。AEBFCDAEBFCD(a)无向图无向图G3(b)G3的两个连通分量的两个连通分量图图7-5无向图及连通分量示意无向图及连通分量示意（13）强连通图、强连通分量）强连通图、强连通分量对对于于有有向向图图来来说说，若若图图中中任任意意一一对对顶顶点点vi和和vj(ij)均均有有从从一一个个顶顶点点vi到到另另一一个个顶顶点点vj有有路路径径，也也有有从从vj到到vi的的路路径径，则则称称该该有有向向图图是是强强连连通通图图。有有向向图图的的极极大强连通子图称为强连通分量。大强连通子图称为强连通分量。图图7-2中中有有两两个个强强连连通通分分量量，分分别别是是v1,v2,v3和和v4，如图如图7-6所示。所示。（14）生成树）生成树连连通通图图G的的一一个个子子图图如如果果是是一一棵棵包包含含G的的所所有有顶顶点点的的树树，则则该该子子图图称称为为G的的生生成成树树（SpanningTree）。在在生生成成树树中中添添加加任任意意一一条条属属于于原原图图中中的的边边必必定定会会产产生生回回路路，因因为为新新添添加加的的边边使使其其所所依依附附的的两两个个顶顶点点之之间间有有了了第第二二条条路路径径。若若生生成成树树中中减减少少任任意意一一条条边边，则则必必然然成成为为非非连连通通的的。n个个顶顶点点的的生生成成树树具具有有n-1条边。条边。V1V3V2V4图图7-6有向图有向图G2的两个的两个强连通分量示意强连通分量示意7-1-3图的基本操作图的基本操作图的基本操作有：图的基本操作有：（1）CreatGraph（G）输输入入图图G的的顶顶点点和和边边，建建立立图图G的的存储。存储。（2）DFSTraverse（G，v）在在图图G中中，从从顶顶点点v出出发发深深度度优先遍历图优先遍历图G。（3）BFSTtaverse（G，v）在在图图G中中，从从顶顶点点v出出发发广广度度优先遍历图优先遍历图G。图图的的存存储储结结构构比比较较多多。对对于于图图的的存存储储结结构构的的选选择择取取决决于具体的应用和需要进行的运算。于具体的应用和需要进行的运算。下面介绍几种常用的图的存储结构。下面介绍几种常用的图的存储结构。7-2 图的存储表示邻接矩阵是表示顶点之间相邻关系的矩阵。邻接矩阵是表示顶点之间相邻关系的矩阵。假假设设图图G（V，E）有有n个个顶顶点点，即即Vv0,v1,vn-1，则则G的邻接矩阵是具有如下性质的的邻接矩阵是具有如下性质的n阶方阵：阶方阵：1若若(vi,vj)或或是是E(G)中的边中的边Aij=0若若(vi,vj)或或不是不是E(G)中的边中的边若若G是网，则邻接矩阵可定义为：是网，则邻接矩阵可定义为：wij若若(vi,vj)或或是是E(G)中的边中的边Aij=0或或若若(vi,vj)或或不是不是E(G)中的边中的边其其中中，wij表表示示边边(vi,vj)或或上上的的权权值值（如如图图7-3）；表示一个计算机允许的、大于所有边上权值的数。表示一个计算机允许的、大于所有边上权值的数。用用邻邻接接矩矩阵阵表表示示法法如如图图7-77-7所所示示；用用邻邻接接矩矩阵阵表表示示法法如图如图7-87-8所示。所示。图的邻接矩阵具有以下性质：图的邻接矩阵具有以下性质：（1 1）无无向向图图的的邻邻接接矩矩阵阵一一定定是是一一个个对对称称矩矩阵阵。因因此此，在在具具体体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2 2）对对于于无无向向图图，邻邻接接矩矩阵阵的的第第i i行行（或或第第i i列列）非非零零元元素素（或非（或非元素）的个数正好是第元素）的个数正好是第i i个顶点的度个顶点的度TD(vTD(vi i)。（3 3）对对于于有有向向图图，邻邻接接矩矩阵阵的的第第i i行行（或或第第i i列列）非非零零元元素素（或或非非元元素素）的的个个数数正正好好是是第第i i个个顶顶点点的的出出度度OD(vOD(vi i)（或或入入度度ID(vID(vi i)）。）。（4 4）用用邻邻接接矩矩阵阵方方法法存存储储图图，很很容容易易确确定定图图中中任任意意两两个个顶顶点点之之间间是是否否有有边边相相连连；但但是是，要要确确定定图图中中有有多多少少条条边边，则则必必须须按按行行、按按列列对对每每个个元元素素进进行行检检测测，所所花花费费的的时时间间代代价价很很大大。这是用邻接矩阵存储图的局限性。这是用邻接矩阵存储图的局限性。图的邻接矩阵存储的描述如下：图的邻接矩阵存储的描述如下：#defineMAXLEN10typedefstructcharvexsMAXLEN;intedgesMAXLENMAXLEN;intn,e;MGraph;建立一个图的邻接矩阵存储的算法如下：建立一个图的邻接矩阵存储的算法如下：voidCreateMGraph(MGraph*G)inti,j,k;charch1,ch2;printf(请请输输入入顶顶点点数数和和边边数数(输输入入格格式式为为:顶顶点点数数,边边数数):n);scanf(%d,%d,&(G-n),&(G-e);printf(请请输输入入顶顶点点信信息息(顶顶点点号号)每每个个顶顶点点以以回回车车作作为为结结束束:n);for(i=0;in;i+)getchar();scanf(%c,&(G-vexsi);for(i=0;in;i+)for(j=0;jn;j+)G-edgesij=0;printf(请输入每条边对应的两个顶点的序号请输入每条边对应的两个顶点的序号(输入格式为输入格式为:i,j):n);for(k=0;ke;k+)getchar();printf(请输入第请输入第%d条边的顶点序号：条边的顶点序号：,k+1);scanf(%c,%c,&ch1,&ch2);for(i=0;ch1!=G-vexsi;i+);for(j=0;ch2!=G-vexsj;j+);G-edgesij=1;7-2-2 7-2-2 邻接表邻接表邻邻接接表表(AdjacencyList)是是图图的的一一种种顺顺序序存存储储与与链链式式存存储储结结合合的的存存储储方方法法。邻邻接接表表表表示示法法类类似似于于树树的的孩孩子子链链表表表表示示法法。就就是是对对于于图图G中中的的每每个个顶顶点点vi，该该方方法法将将所所有有邻邻接接于于vi的的顶顶点点vj链链成成一一个个单单链链表表，这这个个单单链链表表就就称称为为顶顶点点vi的的邻邻接接表表。再再将将所所有有点点的的邻邻接接表表表表头头放放到到数数组组中中，就就构构成成了了图的邻接表。图的邻接表。在邻接表表示中有两种结点结构，如图在邻接表表示中有两种结点结构，如图7-9所示。所示。顶点域顶点域边表头指针边表头指针邻接点域邻接点域指针域指针域顶点表顶点表边表边表图图7-9邻接矩阵表示的结点结构邻接矩阵表示的结点结构vertexfirstedgeadjvexnext 一一种种是是顶顶点点表表的的结结点点结结构构，它它由由顶顶点点域域（vertex）和和指指向向第第一一条条邻邻接接边边的的指指针针域域（firstedge）构构成成，另另一一种种是是边边表表结结点点，它它由由邻邻接接点点域域(adjvex)和和指指向向下下一一条条邻邻接接边边的的指指针针域域(next)构构成成。对对于于网网的的边边表表需需再再增增设设一一个个存存储储边边上上信信息息（如如权权值值等等）的的域域（info），网网的的边边表表结结构构如如图图7-10所示。所示。邻接点域邻接点域边上信息边上信息指针域指针域图图7-10网的边表结构网的边表结构adjvexinfonext 图图7-11给出无向图给出无向图7-7对应的邻接表表示。对应的邻接表表示。邻接表表示形式描述如下：邻接表表示形式描述如下：defineMAXLEN10/最大顶点数为最大顶点数为10typedefstructnode/边表结点边表结点intadjvex;/邻接点域邻接点域structnode*next;/指向下一个邻接点的指针域指向下一个邻接点的指针域/若要表示边上信息，则应增加一个数据域若要表示边上信息，则应增加一个数据域infoEdgeNode;typedefstructvnode/顶点表结点顶点表结点VertexTypevertex;/顶点域顶点域EdgeNode*firstedge;/边表头指针边表头指针VertexNode;typedefVertexNodeAdjListMAXLEN;/AdjList是邻接表类型是邻接表类型typedefstructAdjListadjlist;/接表接表intn,e;/顶点数和边数顶点数和边数ALGraph;/ALGraph是以邻接表方式存储的图类型是以邻接表方式存储的图类型建立一个有向图的邻接表存储的算法如下：建立一个有向图的邻接表存储的算法如下：voidCreateGraphAL(ALGraph*G)inti,j,k;EdgeNode*s;printf(“请输入顶点数和边数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数)：n);scanf(%d,%d,&(G-n),&(G-e);/读入顶点数和边数读入顶点数和边数printf(请输入顶点请输入顶点(格式为格式为:顶点号顶点号)以回车作为结束以回车作为结束:n);for(i=0;in;i+)/立有立有n个顶点的顶点表个顶点的顶点表scanf(n%c,&(G-adjlisti.vertex);/读入顶点信息读入顶点信息G-adjlisti.firstedge=NULL;/点的边表头指针设为空点的边表头指针设为空printf(请输入边的信息请输入边的信息(输入格式为输入格式为:i,j)：n);for(k=0;ke;k+)/建立边表建立边表scanf(“n%d,%d”,&i,&j);/读入边读入边的顶点对应序号的顶点对应序号 s=newEdgeNode;/生成新边表结点生成新边表结点ss-adjvex=j;/邻接点序号为邻接点序号为js-next=G-adjlisti.firstedge;/新边表插入到顶点边表头部新边表插入到顶点边表头部G-adjlisti.firstedge=s;若无向图中有若无向图中有n个顶点、个顶点、e条边，则它的邻接表需条边，则它的邻接表需n个头个头结点和结点和2e个表结点。显然，在边稀疏个表结点。显然，在边稀疏(en(n-1)/2)的情况下，的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。息较多时更是如此。在在无无向向图图的的邻邻接接表表中中，顶顶点点vi的的度度恰恰为为第第i个个链链表表中中的的结结点点数数；但但在在有有向向图图中中，第第i个个链链表表中中的的结结点点个个数数只只是是顶顶点点vi的的出出度度。如如果果要要求求入入度度，则则必必须须遍遍历历整整个个邻邻接接表表才才能能得得到到结结果果。有有时时，为为了了便便于于确确定定顶顶点点的的入入度度或或以以顶顶点点vi为为头头的的弧弧，可可以以建建立立一一个个有有向向图图的的逆逆邻邻接接表表，即即对对每每个个顶顶点点vi建建立立一一个个链链接接，以以vi为为弧弧头头的的弧弧的的链链表表。例例如如图图7-12所所示示为为有有向向图图G2（图图7-2）的邻接表和逆邻接表。）的邻接表和逆邻接表。在建立邻接表或逆邻接表时，若输入的顶点信息即为在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为顶点的编号，则建立邻接表的复杂度为O（n+e），否则，），否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为需要通过查找才能得到顶点在图中位置，则时间复杂度为O（n*e）。）。7-3 图的遍历图图的的遍遍历历（traversinggraph）是是指指从从图图中中的的某某一一顶顶点点出出发发，对对图图中中的的所所有有顶顶点点访访问问一一次次，而而且且仅仅访访问问一一次次。图图的的遍遍历历是是图图的的一一种种基基本本操操作作。由由于于图图结结构构本本身身的的复复杂杂性性，所所以以图图的遍历操作也较复杂，主要表现在以下四个方面：的遍历操作也较复杂，主要表现在以下四个方面：（1）在在图图结结构构中中，每每一一个个结结点点的的地地位位都都是是相相同同的的，没没有有一一个个“自自然然”的的首首结结点点，图图中中任任意意一一个个顶顶点点都都可可作作为为访访问问的的起起始结点。始结点。（2）在在非非连连通通图图中中，从从一一个个顶顶点点出出发发，只只能能够够访访问问它它所所在在的的连连通通分分量量上上的的所所有有顶顶点点，因因此此，还还需需考考虑虑如如何何访访问问图图中中其其余的连通分量。余的连通分量。（3）在在图图结结构构中中，如如果果有有回回路路存存在在，那那么么一一个个顶顶点点被被访访问问之后，有可能沿回路又回到该顶点。之后，有可能沿回路又回到该顶点。（4）在在图图中中，一一个个顶顶点点可可以以和和其其它它多多个个顶顶点点相相连连，当当这这个个顶点访问过后，就要考虑如何选取下一个要访问的顶点。顶点访问过后，就要考虑如何选取下一个要访问的顶点。7-3-1深度优先搜索深度优先搜索深深度度优优先先搜搜索索（Depth-FisrstSearch）遍遍历历类类似似于于树树的的先先根遍历，是树的先根遍历的推广。根遍历，是树的先根遍历的推广。假假设设初初始始状状态态是是图图中中所所有有顶顶点点未未曾曾被被访访问问，则则深深度度优优先先搜搜索索可可从从图图中中某某个个顶顶点点发发v出出发发，首首先先访访问问此此顶顶点点，然然后后任任选选一一个个v的的未未被被访访问问的的邻邻接接点点w出出发发，继继续续进进行行深深度度优优先先搜搜索索，直直到到图图中中所所有有和和v路路径径相相通通的的顶顶点点都都被被访访问问到到；若若此此时时图图中中还还有有顶顶点点未未被被访访问问到到，则则另另选选一一个个未未被被访访问问的的顶顶点点作作为为起始点，重复上面的做法，直至图中所有的顶点都被访问。起始点，重复上面的做法，直至图中所有的顶点都被访问。V1V5V2V4V8V3V6V7图图7-13无向图无向图G5 以以图图7-13的的无无向向图图G5为为例例，其其深深度度优优先先搜搜索索得得到到的的顶顶点点访访问问序列为：序列为：v1v2v4v8v5v3v6、v7显显然然，以以上上方方法法是是一一个个递递归归的的过过程程。为为了了在在遍遍历历过过程程中中便便于于区区分分顶顶点点是是否否已已被被访访问问，需需附附设设访访问问标标志志数数组组visited0:n-1,，其其初初值值为为FALSE，一一旦旦某某个个顶顶点点被被访访问问，则其相应的分量置为则其相应的分量置为TRUE。从从图图的的某某一一点点v出出发发，递递归归地地进进行行深深度度优优先先遍遍历历的的过过程程如如下面算法所示。下面算法所示。voidDFSTraverseM(MGraph*G)inti;for(i=0;in;i+)visitedi=FALSE;/FALSE在在c语言中定义为语言中定义为0，以下同，以下同for(i=0;in;i+)if(!visitedi)DFSM(G,i);voidDFSM(MGraph*G,inti)intj;printf(tt深度优先遍历结点深度优先遍历结点:结点结点%cn,G-vexsi);visitedi=TRUE;/TRUE在在c语言中定义为语言中定义为1，以下同，以下同for(j=0;jn;j+)if(G-edgesij=1&!visitedj)DFSM(G,j);在在遍遍历历时时，对对图图中中每每个个顶顶点点至至多多调调用用一一次次DFSM函函数数，因因为为一一旦旦某某个个顶顶点点被被标标志志成成已已被被访访问问，就就不不再再从从它它出出发发进进行行搜搜索索。因因此此，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程。其其耗耗费费的的时时间间则则取取决决于于所所采采用用的的存存储储结结构构。当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵图图的的存存储储结结构构时时，查查找找每每个个顶顶点点的的邻邻接点所需时间为接点所需时间为O(n2)，其中，其中n为图中顶点数。为图中顶点数。当当以以邻邻接接表表作作图图的的存存储储结结构构时时，找找邻邻接接点点所所需需时时间间为为O(e)，其其中中e为为无无向向图图中中边边的的数数或或有有向向图图中中弧弧的的数数。由由此此，当当以以邻邻接接表表作作存存储储结结构构时时，深深度度优优先先搜搜索索遍遍历历图图的的时时间间复复杂杂度为度为O(n+e)。7-3-2广度优先搜索广度优先搜索广度优先搜索广度优先搜索遍历类似于树的按层次遍历。遍历类似于树的按层次遍历。假假设设从从图图中中某某顶顶点点v出出发发，在在访访问问了了v之之后后依依次次访访问问v的的各各个个未未曾曾访访问问过过的的邻邻接接点点，然然后后分分别别从从这这些些邻邻接接点点出出发发依依次次访访问问它它们们的的邻邻接接点点，并并使使“先先被被访访问问的的顶顶点点的的邻邻接接点点”先先于于“后后被被访访问问的的顶顶点点的的邻邻接接点点”被被访访问问，直直至至图图中中所所有有已已被被访访问问的的顶顶点点的的邻邻接接点点都都被被访访问问到到。若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中中所所有有顶顶点点都都被被访访问问到到为为止止。换换句句话话说说，广广度度优优先先搜搜索索遍遍历历图图的的过过程程中中以以v为为起起始始点点，由由近近至至远远，依依次次访访问问和和v有有路径相通且路径长度为路径相通且路径长度为1,2,的顶点。的顶点。对对图图7-13无无向向图图G5进进行行广广度度优优先先搜搜索索遍遍历历，首首先先访访问问v1和和v1的的邻邻接接点点v2和和v3，然然后后依依次次访访问问v2的的邻邻接接点点v4和和v5及及v3的的邻邻接接点点v6和和v7，最最后后访访问问v4的的邻邻接接点点v8。由由于于这这些些顶顶点点的的邻邻接接点点均均已已被被访访问问，并并且且图图中中所所有有顶顶点点都都被被访访问问，由由些些完完成成了了图图的的遍遍历历。得得到到的顶点访问序列为：的顶点访问序列为：v1v2v3v4v5v6v7v8和和深深度度优优先先搜搜索索类类似似，在在遍遍历历的的过过程程中中也也需需要要一一个个访访问问标标志志数数组组。并并且且，为为了了顺顺次次访访问问路路径径长长度度为为2、3、的的顶顶点点，需需附附设设队队列列以以存存储储已已被被访访问问的的路路径径长长度度为为1、2、的顶点。的顶点。V1V5V2V4V8V3V6V7图图7-13无向图无向图G5 从从图图的的某某一一点点v出出发发，递递归归地地进进行行广广度度优优先先遍遍历历的的过过程程如如下面的算法所示。下面的算法所示。voidBFSTraverseM(MGraph*G)inti;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi)BFSM(G,i);voidBFSM(MGraph*G,intk)inti,j;CirQueueQ;InitQueue(&Q);printf(广度优先遍历结点广度优先遍历结点:结点结点%cn,G-vexsk);visitedk=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)i=DeQueue(&Q);for(j=0;jn;j+)if(G-edgesij=1&!visitedj)printf(广度优先遍历结点广度优先遍历结点:%cn,G-vexsj);visitedj=TRUE;EnQueue(&Q,j);图7-4 图的连通性 分分析析上上述述算算法法，每每个个顶顶点点至至多多进进一一次次队队列列。遍遍历历图图的的过过程程实实质质是是通通过过边边或或弧弧找找邻邻接接点点的的过过程程，因因此此广广度度优优先先搜搜索索遍遍历历图图和和深深度度优优先先搜搜索索遍遍历历的的时时间间复复杂杂度度是是相相同同的的，两两者不同之处仅仅在于对顶点访问的顺序不同。者不同之处仅仅在于对顶点访问的顺序不同。判判定定一一个个图图的的连连通通性性是是图图的的一一个个应应用用问问题题，我我们们可可以以利利用用图图的的遍遍历历算算法法来来求求解解这这一一问问题题。本本节节将将讨讨论论无无向向图图的的连通性问题，并讨论最小代价生成树等问题。连通性问题，并讨论最小代价生成树等问题。7-4-1 7-4-1 无向图的连通分量和生成树无向图的连通分量和生成树 在在对对无无向向图图进进行行遍遍历历时时，对对于于连连通通图图，仅仅需需从从图图中中任任一一顶顶点点出出发发，进进行行深深度度优优先先搜搜索索或或广广度度优优先先搜搜索索，便便可可访访问问到到图图中中所所有有顶顶点点。对对非非连连通通图图，则则需需从从多多个个顶顶点点出出发发进进行行搜搜索索，而而每每一一次次从从一一个个新新的的起起始始点点出出发发进进行行搜搜索索过过程程中中得到的顶点访问序列恰为其各个连通分量中的顶点集。得到的顶点访问序列恰为其各个连通分量中的顶点集。例例如如，图图7-14(a)是是一一个个非非连连通通图图G6，按按照照图图7-14(b)所示所示G3的邻接表进行深度优先搜索遍历的邻接表进行深度优先搜索遍历AEBFCD图图7-14(a)非连通图非连通图图图7-14(b)G6的邻接表的邻接表两两次次调调用用DFS过过程程（即即分分别别从从顶顶点点A和和D出出发发），得得到到的顶点访问序列为：的顶点访问序列为：ABFECE这这两两个个顶顶点点集集分分别别加加上上所所有有依依附附于于这这些些顶顶点点的的边边，便便构成了非连通图构成了非连通图G3的两个连通分量。的两个连通分量。因因此此，要要想想判判定定一一个个无无向向图图是是否否为为连连通通图图，或或有有几几个个连连通通分分量量，就就可可设设一一个个计计数数变变量量count，初初始始时时取取值值为为0，在在深深度度优优先先搜搜索索算算法法循循环环中中，每每调调用用一一次次DFS，就就给给count增增1。这这样样，当当整整个个算算法法结结束束时时，依依据据count的的值值，就就可可确确定定图的连通性了。图的连通性了。设设E(G)E(G)为为连连通通图图G G中中所所有有边边的的集集合合，则则从从图图中中任任一一顶顶点点出出发发遍遍历历图图时时，必必定定将将E(G)E(G)分分成成两两个个集集合合T(G)T(G)和和B(G)B(G)，其其中中T(G)T(G)是是遍遍历历图图过过程程中中历历经经的的边边的的集集合合；B(G)B(G)是是剩剩余余的的边边的的集集合合。显显然然，T(G)T(G)和和图图G G中中所所有有顶顶点点一一起起构构成成连连通通图图G G的的极小连通子图。极小连通子图。按按照照7-1-27-1-2节节的的定定义义，它它是是连连通通图图的的一一棵棵生生成成树树，并并且且由由深深度度优优先先搜搜索索得得到到的的为为深深度度优优先先生生成成树树；由由广广度度优优先先搜搜索索得得到到的的为为广广度度优优先先生生成成树树。例例如如，图图7-15(a)7-15(a)和和(b)(b)所所示示分分别别为为图图7-137-13连连通通图图G5G5的的深深度度优优先先生生成成树树和和广广度度优优先先生生成成树树。图图中中虚线为集合虚线为集合B(G)B(G)中的边，实线为集合中的边，实线为集合T(G)T(G)中的边。中的边。图图7-15(a)G5的深度优先生成树的深度优先生成树图图7-15(b)G5的广度优先生成树的广度优先生成树V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7 对对于于非非连连通通图图，通通过过这这样样的的遍遍历历，将将得得到到的的是是生生成成森森林林。例例如如，图图7-16 7-16(b)(b)所所示示为为图图7-16 7-16(a)(a)的的深深度优先生成森林，它由三棵深度优先生成树组成。度优先生成森林，它由三棵深度优先生成树组成。图图7-16(a)非连通无向图非连通无向图G7图图7-16(b)G7的深度优先生成树林的深度优先生成树林JHKLMAICFGBDEJHKLMAICFGBDE7-4-2 7-4-2 最小生成树最小生成树1 1最小生成树的基本概念最小生成树的基本概念由由生生成成树树的的定定义义可可知知，无无向向连连通通图图的的生生成成树树不不一一定定是是唯唯一一的的。连连通通图图的的一一次次遍遍历历所所经经过过的的边边的的集集合合及及图图中中所所有有顶顶点点的的集集合合就就构构成成了了该该图图的的一一棵棵生生成成树树，对对连连通通图图的的不不同同遍遍历历，就就可可能能得得到到不不同同的的生生成成树树。图图7-17(a)、(b)和和(c)所示的均为图所示的均为图7-13的无向连通图的无向连通图G5的生成树。的生成树。V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7 图图7-17 7-17 无向连通图无向连通图G5G5的三棵生成树的三棵生成树（a）（b）（c）可可以以证证明明，对对于于有有n个个顶顶点点的的无无向向连连通通图图，无无论论其其生生成成树树的形态如何，所有生成树中都有且仅有的形态如何，所有生成树中都有且仅有n-1条边。条边。如如果果无无向向连连通通图图是是一一个个网网，那那么么，它它的的所所有有生生成成树树中中必必有一棵边的权值之和为最小的生成树，简称为最小生成树。有一棵边的权值之和为最小的生成树，简称为最小生成树。最最小小生生成成树树的的概概念念可可以以应应用用到到许许多多实实际际问问题题中中。例例如如有有这这样样一一个个问问题题：以以尽尽可可能能抵抵的的总总造造价价建建造造城城市市间间的的通通讯讯网网络络，把把十十个个城城市市联联系系在在一一起起。在在这这十十个个城城市市中中，任任意意两两个个城城市市之之间间都都可可以以建建造造通通讯讯线线路路，通通讯讯线线路路的的造造价价依依据据城城市市间间的的距距离离不不同同而而有有不不同同的的造造价价，可可以以构构造造一一个个通通讯讯线线路路造造价价网网络络，在在网网络络中中，每每个个顶顶点点表表示示城城市市，顶顶点点之之间间的的边边表表示示城城市市之之间间可可构构造造通通讯讯线线路路，每每条条边边的的权权值值表表示示该该条条通通讯讯线线路路的的造造价价，要要想使总的造价最低，实际上就是寻找该网络的最小生成树。想使总的造价最低，实际上就是寻找该网络的最小生成树。2常用的构造最小生成树的方法常用的构造最小生成树的方法（1 1）构造最小生成树的）构造最小生成树的PrimPrim算法算法假假设设G（V，E）为为一一连连通通网网，顶顶点点集集V=v1，v2，vn，E为为网网中中所所有有带带权权边边的的集集合合。设设置置两两个个新新的的集集合合U和和T，其其中中集集合合U用用于于存存放放G的的最最小小生生成成树树中中的的顶顶点点，集集合合T存存放放G的的最最小小生生成成树树中中的的边边。令令集集合合U的的初初值值为为Uv1（假假设设构构造造最最小小生生成成树树时时，从从顶顶点点v