第七章图.ppt

第七章第七章 图图l7.1 7.1 图图的定的定义义和和术语术语 l7.2 7.2 图图的存的存储结储结构构l7.3 7.3 图图的遍的遍历历l7.4 7.4 图图的的连连通性通性问题问题l7.5 7.5 有向无有向无环图环图及其及其应应用用 l7.6 7.6 最短路径最短路径1.第七章第七章 图图l在在线线性性结结构构中，数据元素之中，数据元素之间间是一是一对对一的一的线线性性关系，除第一个数据元素和最后一个数据元素关系，除第一个数据元素和最后一个数据元素之外，每个数据元素只有一个直接前之外，每个数据元素只有一个直接前驱驱和一个和一个直接后直接后继继。l在在树树型型结结构构中，数据元素之中，数据元素之间间是一是一对对多的多的层层次次和分支的关系，除根和分支的关系，除根结结点外，每个数据元素都点外，每个数据元素都只有一个直接前只有一个直接前驱驱（即双（即双亲结亲结点），但每个数点），但每个数据元素都可能有多个直接后据元素都可能有多个直接后继继（即孩子（即孩子结结点）。点）。l然而在然而在图图型型结结构构中，数据元素之中，数据元素之间间的关系是任的关系是任意的，是多意的，是多对对多的关系，既多的关系，既图图中任意两个中任意两个结结点点之之间间都可能相关。都可能相关。2.7.1 图图的定的定义义和和术语术语l图图中的数据元素通常称中的数据元素通常称为为顶顶点。点。l图图G G由两个集合由两个集合V V和和E E组组成，通常成，通常记为记为 G G(V(V，E)E)其中，其中，V V是是图图中中顶顶点的有点的有穷穷非空集合，非空集合，E E是是V V中中顶顶点点间间的的边边的有的有穷穷集。集。除此之外，也通常将除此之外，也通常将图图G G的的顶顶点集和点集和边边集分集分别记别记为为V(G)V(G)和和E(G)E(G)。E(G)E(G)可以是空集。若可以是空集。若E(G)E(G)为为空，空，则图则图G G只有只有顶顶点而没有点而没有边边。图图可分可分为为无向无向图图和和有向有向图图两两类类。3.7.1 图图的定的定义义和和术语术语l无向无向图图：图图中的每条中的每条边边都是无方向的。都是无方向的。l在无向在无向图图中，一条无向中，一条无向边边是由两个是由两个顶顶点点组组成的成的无序无序对对，通常用，通常用圆圆括号括号表示。例如（表示。例如（vi，vj）表示一条无向表示一条无向边边，在无向在无向图图中，（中，（vi，vj）和）和（vj，vi）是两条相同的无向）是两条相同的无向边边。l（无向）完全（无向）完全图图：任意两个任意两个顶顶点之点之间间都有一条都有一条无向无向边边的无向的无向图图。l（无向）完全（无向）完全图图是是含有含有n n个个顶顶点和点和n(n-1)/2n(n-1)/2条条边边的无向的无向图图。4.7.1 图图的定的定义义和和术语术语l如下如下图图G G是一个无向是一个无向图图BCAFEDl图图G G可可记记作：作：lG G（V V，E E），），其中其中lV VA,B,C,D,E,FA,B,C,D,E,FlE E=(A,B),(A,E),(B,F),(B,E),(=(A,B),(A,E),(B,F),(B,E),(C,F),(C,D),(D,F)C,F),(C,D),(D,F)若若(vi(vi，vj)vj)是一条无向是一条无向边边，则则称称顶顶点点vivi和和vjvj互互为为邻邻接点接点，或称，或称vivi和vjvj相相邻邻接；接；同同时时称称边边(vi(vi，vj)vj)依附依附于于顶顶点点vivi和vjvj，或称，或称边边(vi(vi，vj)vj)与与顶顶点点vivi和和vjvj相关相关联联。5.7.1 图图的定的定义义和和术语术语l有向有向图图：图图中的每条中的每条边边都是有方向的。都是有方向的。l在有向在有向图图中，一条有向中，一条有向边边是由两个是由两个顶顶点点组组成的成的有序有序对对，通常用，通常用尖括号尖括号表示。例如表示。例如表表示一条有向示一条有向边边，vi是是边边的起始点，的起始点，vj是是边边的的终终点。因此，点。因此，和和是两条不同的是两条不同的有向有向边边。l有向有向边边也称也称为为弧弧，边边的起始点称的起始点称为为弧尾弧尾，终终点点称称为为弧弧头头。6.7.1 图图的定的定义义和和术语术语l如下如下图图G G 是一个有向是一个有向图图ABECFl图图G G可可记记作：作：lG G（V V，E E），），其中其中lV VA,B,C,D,E,FA,B,C,D,E,FlE E=,=,C,F,l若若v vi i,v,vj j是是图图中的一条有向中的一条有向边边，则则称称顶顶点点vj vj是是vi vi的的领领接点，或称接点，或称顶顶点点v vi i邻邻接到接到v vj j，或，或顶顶点点v vj j邻邻接自接自顶顶点点v vi i，并称弧，并称弧v vi i,v,vj j依附于依附于顶顶点点v vi i和和v vj j，或称弧或称弧v vi i,v,vj j与与顶顶点点v vi i和和v vj j相关相关联联。7.7.1 图图的定的定义义和和术语术语l有向完全有向完全图图：任意两个任意两个顶顶点之点之间间都有一都有一对对相向的相向的有向有向边边的有向的有向图图。即含有。即含有n n个个顶顶点和点和n(n-1)n(n-1)条弧（有条弧（有向向边边）的有向）的有向图图。ABECF1597211132l权权：与：与图图的的边边或弧相关的数。或弧相关的数。这这些些权权可以表示从一个可以表示从一个顶顶点到点到另一个另一个顶顶点的距离或者耗点的距离或者耗费费。l网网：弧（或：弧（或边边）带权带权的的图图称称为为网。网。8.7.1 图图的定的定义义和和术语术语l子子图图：给给定定图G1=G1=（V1V1，E1E1）、）、图G2=G2=（V2V2，E2E2），若），若V1V1是是V2V2的子集，的子集，E1E1是是E2E2的子集，的子集，则则称称G1G1是是G2G2的的子子图图。l例：例：ABECF图图G GAB图图G1G1CF图图G3G3E图图G2G2CE图图G4G49.7.1 图图的定的定义义和和术语术语l无向无向图图中中顶顶点点v v的的度：度：指的是和指的是和v v相关相关联联的的边边的数目的数目，通常通常记为记为D(v)D(v)。BCAFED例：在右例：在右图图中中D(B)=D(F)3D(A)=D(C)=D(D)=D(E)=2结论结论无向无向图图中：中：顶顶点的度之和点的度之和=边边数的两倍数的两倍10.7.1 图图的定的定义义和和术语术语l有向有向图图中中顶顶点点v v的度分的度分为为入度入度和和出度出度。l顶顶点点v v的入度：的入度：以以顶顶点点v v为终为终点的有向点的有向边边的数目，的数目，记为记为ID(v)ID(v)；l顶顶点点v v的出度：的出度：以以顶顶点点v v为为起始点的有向起始点的有向边边的数的数目，目，记为记为OD(v)OD(v)；l有向有向图图中中顶顶点点v v的度的度则则定定义为该顶义为该顶点的入度和点的入度和出度之和，即出度之和，即 D(v)D(v)ID(v)ID(v)十十OD(v)OD(v)。11.7.1 图图的定的定义义和和术语术语l例：在下面的例：在下面的有向有向图图中中lID(A)=1；OD(A)=2;D(A)=3lID(C)=1；OD(C)=1;D(C)=3ABECF结论结论有向有向图图中：中：顶顶点入度之和点入度之和=顶顶点出度之和点出度之和=弧数弧数12.7.1 图图的定的定义义和和术语术语l在无向在无向图图G G中，若存在一个中，若存在一个顶顶点序列（点序列（v vp p,v,vi1 i1,，v vin in，v vq q），使得，使得(v(vp p，v vil il)，(v(vi1 i1,v,vi2 i2)，(v(vin in，v vq q)均属于均属于边边集集E(G)E(G)，则则称称顶顶点点v vp p到到v vq q存在一条存在一条路径路径。l若若G G是有向是有向图图，则则路径也是有向的，它由路径也是有向的，它由E(G)E(G)中的有中的有向向边边v vp p，v vil il,v vil il，v vi2 i2,，v vin in，v vq q组组成。成。l路径路径长长度：度：该该路径上路径上边边的数目。的数目。l序列中序列中顶顶点不重复出点不重复出现现的路径称的路径称为为简单简单路径路径。l起点和起点和终终点相同点相同(v(vp pv vq q)的路径称的路径称为为回路回路。l若一条路径上除了若一条路径上除了v vp p和和v vq q可以相同外，其余可以相同外，其余顶顶点均不点均不相同，相同，则则称此路径称此路径为为简单简单回路回路或或简单环简单环。13.7.1 图图的定的定义义和和术语术语l例如：在有向例如：在有向图图G G中：中：l（A,B,C,FA,B,C,F）是）是图图G G的一条路径，它是由有向的一条路径，它是由有向边边序列序列,组组成，它成，它是一条是一条简单简单路径路径，路径，路径的的长长度是度是3 3。l（A,A,B B,C,F,C,F,B B,E,E）也是）也是图图G G的一条路径，它是由有向的一条路径，它是由有向边边序列序列A,A,B B,E组组成成 ，它，它不不是是简单简单路径路径，这这条路径的条路径的长长度是度是5 5。l,也是也是 图图G G的一条路径，的一条路径，这这条路径的条路径的长长 度是度是4 4，它，它是一条是一条简单简单回路回路。ABECF14.7.1 图图的定的定义义和和术语术语l在无向在无向图图G G中，若从中，若从顶顶点点v vi i到到顶顶点点v vj j有路径有路径，则则称称v vi i和和v vj j是是连连通的。通的。若若图图G G中任意两个不同的中任意两个不同的顶顶点点v vi i和和v vj j都都连连通，通，则则称称G G为为连连通通图图。l无向无向图图G G的一个的一个极大极大连连通子通子图图称称为为G G的一个的一个连连通通分量。分量。显显然，任何然，任何连连通通图图的的连连通分量只有一个，通分量只有一个，就是它自身，而非就是它自身，而非连连通的无向通的无向图图有多个有多个连连通分通分量。量。15.7.1 图图的定的定义义和和术语术语l例如：下例如：下图图所示所示为为两个无向两个无向图图G1G1和和G2G2，其中，其中:G1 G1是一个是一个连连通通图图 G2 G2是由是由4 4个个连连通分量通分量组组成的非成的非连连通通图图。BCAFED无向无向图图G1G1BEADCGHIFJ无向无向图图G2G216.7.1 图图的定的定义义和和术语术语l在有向在有向图图G中，若中，若对对于其中的任意两个不同的于其中的任意两个不同的顶顶点点vi和和vj，从，从vi到到vj和从和从vj到到vi都存在路径，都存在路径，则则称称G是是强强连连通通图图。l有向有向图图G的极大的极大强强连连通子通子图图称称为为G的的强强连连通分通分量量。显显然，然，强强连连通通图图只有一个只有一个强强连连通分量，即通分量，即是其自身。非是其自身。非强强连连通的有向通的有向图图有多个有多个强强连连通分通分量。量。17.7.1 图图的定的定义义和和术语术语l例如：下例如：下图图所示所示为为两个有向两个有向图图G1G1和和G2G2，其中，其中:G1 G1是一个是一个强强连连通通图图，G2 G2是由是由3 3个个强强连连通分量通分量组组成的非成的非连连通通图图。ABECF有向有向图图G1G1ABECF有向有向图图G2G218.7.1 图图的定的定义义和和术语术语l结论结论l有有n个个顶顶点的点的有向有向图图最多有最多有条条边边，最，最少有少有 条条边边。l有有n个个顶顶点的点的无向无向图图最多有最多有条条边边，最少有最少有条条边边。l有有n个个顶顶点的点的连连通通图图最少有最少有条条边边，若少于，若少于条条边边，图图一定是非一定是非连连通通图图，多于，多于条条边边，连连通通图图中一定有中一定有环环路存在。路存在。n(n-1)n(n-1)/200n-1n-1n-119.7.1 图图的定的定义义和和术语术语l生成生成树树：一个：一个连连通通图图的生成的生成树树是一个是一个极小极小连连通子通子图图，它含有它含有图图中全部中全部顶顶点，但只含有足以构成一棵点，但只含有足以构成一棵树树的的n-1n-1条条边边。l如如图图所示：所示：连连通通图图G G的一棵生成的一棵生成树树l注意注意:一棵有一棵有n n个个顶顶点的生成点的生成树树一定有一定有n-1n-1条条边边。但有。但有n n个个顶顶点和点和n-1n-1条条边边的的图图，一定是一棵生成，一定是一棵生成树吗树吗？ABECFABECF1 1棵生成棵生成树树20.7.2 图图的存的存储结储结构构l由于由于图图的的结结构比构比较较复复杂杂，除了要把，除了要把图图的各的各顶顶点存点存入入计计算机，算机，还应该还应该把各把各顶顶点之点之间间的关系也的关系也输输入入计计算机，而算机，而图图中任意两个中任意两个顶顶点之点之间间都可能存在都可能存在联联系，系，因此无法以数据元素在存因此无法以数据元素在存储储区中的物理位置来表区中的物理位置来表示元素之示元素之间间的关系，即的关系，即图图没有没有顺顺序映象的存序映象的存储结储结构，但可以借助数构，但可以借助数组组的数据的数据类类型表示型表示图图中中顶顶点之点之间间的关系，即的关系，即图图的的领领接矩接矩阵阵的存的存储结储结构构。l另一方面，也可以用另一方面，也可以用链链表表示表表示图图，如，如领领接表接表、领领接多重表接多重表和和十字十字链链表表是是图图常用的三种常用的三种链链式存式存储结储结构。构。21.7.2 图图的存的存储结储结构构l对对于具体于具体问题问题中的中的图图来来说说,要要为为其其选择选择最好的存最好的存储结储结构构，不，不仅仅仅仅要依要依赖赖于于图图的性的性质质如有向如有向图还图还是无向是无向图图,以及以及图图中的数据中的数据,例如例如:顶顶点数点数,边边数等数等,而且而且还还与与在在图图上所上所实实施的操作施的操作有关，例如有关，例如对图对图中的中的顶顶点点进进行插入或行插入或删删除操作的除操作的频频率等率等.l下面将主要介下面将主要介绍图绍图的的领领接矩接矩阵阵和和领领接表接表这这两种两种存存储储方式。方式。22.7.2.1 7.2.1 邻邻接矩接矩阵阵邻邻接矩接矩阵阵(数数组组表示法）是用二表示法）是用二维维数数组组表示表示顶顶点点之之间间相相邻邻关系的存关系的存储结储结构。构。设设G G(V(V，E)E)是具有是具有n n个个顶顶点的点的无无权图权图，则则G G的的邻邻接矩接矩阵阵是具有如下性是具有如下性质质的的n n阶阶方方阵阵：Ai,j=1若若(v vi i,v,vj j)或或或或是是是是E(G)E(G)中的中的中的中的边边边边 0 0 反之反之反之反之23.7.2.1 7.2.1 邻邻接矩接矩阵阵l l例例例例1 1：给给给给定定定定4 4个个个个顶顶顶顶点的有向点的有向点的有向点的有向图图图图24.7.2.1 7.2.1 邻邻接矩接矩阵阵l例例2：给给定定6个个顶顶点的无向点的无向图图A注注:无向无向图图的的邻邻接矩接矩阵阵是是对对称的，即称的，即 Aij=Aji Aij=Aji25.7.2.1 7.2.1 邻邻接矩接矩阵阵l若若G(V，E)是具有是具有n个个顶顶点的点的带权图带权图（网网）则则G的的邻邻接矩接矩阵阵是具有如下性是具有如下性质质的的n阶阶方方阵阵：Ai,j=WWijij若若(v(vi i,v,vj j)或或或或v是是是是E(G)E(G)中的中的中的中的边边边边，WWij ij为边为边为边为边上的上的上的上的权值权值权值权值 反之反之反之反之26.7.2.1 7.2.1 邻邻接矩接矩阵阵l l例：例：例：例：给给给给定定定定6 6 6 6个个个个顶顶顶顶点的无向网（无向点的无向网（无向点的无向网（无向点的无向网（无向带权图带权图带权图带权图）5781014124A=55885 107107 41441444 12128108107141271412无向网无向网无向网无向网G1G1G1G1及其及其及其及其领领领领接接接接矩矩矩矩阵阵阵阵存存存存储结储结储结储结构构构构27.7.2.1 7.2.1 邻邻接矩接矩阵阵l例例2：给给给给定定定定6 6 6 6个个个个顶顶顶顶点的有向网（有向点的有向网（有向点的有向网（有向点的有向网（有向带权图带权图带权图带权图）v0v1v2v3v4v5v01030100v1v2550v310v42060v5v v0 0v v5 5v v1 1v v2 2v v4 4v v3 330301010202050505 510101001006060图图图图G2G2的的的的领领领领接矩接矩接矩接矩阵阵阵阵存存存存储结储结储结储结构构构构有向有向有向有向带权图带权图带权图带权图G2G228.7.2.1 7.2.1 邻邻接矩接矩阵阵l结论结论l在在无向无向图图的的领领接矩接矩阵阵中中,顶顶点点vivi的度等于的度等于邻邻接接矩矩阵阵中第中第i i行行(或第或第i i列列)上非零元素的个数；上非零元素的个数；l在在有向有向图图的的领领接矩接矩阵阵中，中，顶顶点点vivi的出度等于的出度等于邻邻接矩接矩阵阵中的第中的第i i行上非零元素的个数行上非零元素的个数;l在在有向有向图图的的领领接矩接矩阵阵中，中，顶顶点点vivi的入度等于的入度等于邻邻接矩接矩阵阵中的第中的第i i列上非零元素的个数列上非零元素的个数.29.7.2.1 7.2.1 邻邻接矩接矩阵阵l图图的的领领接矩接矩阵阵存存储储表示表示用用邻邻接接矩矩阵阵表表示示法法表表示示图图，除除了了存存储储用用于于表表示示顶顶点点间间相相邻邻关关系系的的邻邻接接矩矩阵阵外外，通通常常还还需需要要用用一一个个顺顺序序表表来来存存储图储图的的顶顶点信息。其形式点信息。其形式说说明如下：明如下：#definen6/*图图的的顶顶点数点数*/#definee8/*图图的的边边（弧）数（弧）数*/typedefstructcharvexsn+1；/*设顶设顶点的数据点的数据类类型型为为char型型*/intarcsn+1n+1；/*设权值类设权值类型型为为int*/Graph；GraphG;30.7.2.1 7.2.1 邻邻接矩接矩阵阵l创创建无向网的算法建无向网的算法#defineMAX10000CreatGraph(Graph*G)/*建立无向网建立无向网络络*/inti，j，k；intw；for(i1；i=n；i+)G-vexsigetchar()；/*读读入入n个个顶顶点信息点信息*/for(i1；i=n；i+)for(j1；j=n；j+)G-arcsijMAX；/*邻邻接矩接矩阵阵初始化初始化*/for(k1；k=e；k+)/*读读入入e条条边边*/scanf(”ddd”，&i,&j,&w)；G-arcsijw；G-arcsjiw；31.7.2.1 7.2.1 邻邻接矩接矩阵阵l分析分析该该算法的算法的时间时间复复杂杂度度算法的算法的执执行行时间时间是是O(n+n2+e)，其中，其中O(n2)的的时时间间耗耗费费在在邻邻接矩接矩阵阵的初始化操作上。因的初始化操作上。因为为en2，所以，算法的，所以，算法的时间时间复复杂杂度是度是O(n2)。32.7.2.2 邻邻接表接表l领领接表是接表是图图的一种的一种链链式存式存储结储结构。构。类类似于似于树树的的孩子孩子链链表表示法。表表示法。l在在领领接表存接表存储结储结构中，构中，对对于于图图G G中的每个中的每个顶顶点点vi vi，把，把vi vi的所有的所有邻邻接点接点链链成一个成一个单链单链表，表，这这个个单链单链表就称表就称为为顶顶点点vi vi的的邻邻接点接点单链单链表表。那么，。那么，若若图图有有n n个个顶顶点，就有点，就有n n个个领领接点接点单链单链表。表。l为为了便于了便于随机随机访问访问任一任一顶顶点点的的邻邻接点接点单链单链表表，通常将所有通常将所有邻邻接点接点单链单链表的表的头结头结点点顺顺序存序存储储在在一个一个结结构体数构体数组组中。中。33.7.2.2 邻邻接表接表ln n个个领领接点接点单链单链表的表表的表头结头结点点结结构均构均为为：含有：含有两个域，一个是两个域，一个是顶顶点域点域，用来存放，用来存放顶顶点点vi vi的信的信息；另一个是息；另一个是指指针针域域，用来指向，用来指向vi vi的的领领接点接点单单链链表中的第一个表中的第一个结结点。点。l在在顶顶点点vi vi的的邻邻接点接点单链单链表中，表中，每个每个结结点均有两点均有两个域，一个是个域，一个是邻邻接点域接点域，用以存放与，用以存放与vi vi的的领领接接点点vj vj的信息；另一个是的信息；另一个是指指针针域域，用来指向与，用来指向与vi vi相相邻邻的下一个的下一个领领接点。接点。34.7.2.2 邻邻接表接表v v0 0v v5 5v v1 1v v2 2v v4 4v v3 32 23 36 61 15 53 34 4 V0V0V1V1V2V2V3V3V4V4V5V55 5 l例例1：图图的的领领接表存接表存储结储结构构l注意注意：图图的的邻邻接矩接矩阵阵表示是唯一的，但其表示是唯一的，但其邻邻接表不唯一接表不唯一35.7.2.2 邻邻接表接表l例例2：图图的的领领接表存接表存储结储结构构V5V3V2V6V1V42 25 55 51 16 66 66 64 43 32 22 24 43 31 1V1V2V3V4V5V636.7.2.2 邻邻接表接表l创创建建领领接表的接表的算法思想算法思想l建立无向建立无向图图的的邻邻接表接表时时，每，每读读入一个入一个顶顶点点对对（i,j）时时，就，就创创建一个建一个邻邻接点序号接点序号为为j的新的新结结点，将其插点，将其插入到入到vi为为表表头结头结点的点的领领接点接点单链单链表中；同表中；同时时生成一生成一个个邻邻接点序号接点序号为为i的新的新结结点，将其插入到点，将其插入到vj为为表表头头结结点的点的单链单链表中。表中。l建立有向建立有向图图的的邻邻接表接表与此与此类类似，只是更加似，只是更加简单简单，每每读读入一个入一个顶顶点点对对序号序号i，j时时，仅仅需生成一个需生成一个邻邻接点序号接点序号为为j的新的新结结点，将其插入到点，将其插入到vi为为表表头结头结点的点的领领接点接点单链单链表中即可。表中即可。l若若建立网建立网络络的的邻邻接表接表，则则需在需在链链表的每个表的每个结结点中点中增加一个存增加一个存储边储边上的上的权值权值的数据域。的数据域。37.7.2.2 邻邻接表接表l领领接表存接表存储结储结构的构的结论结论l在在无向无向图图的的领领接表接表中中 顶顶点点vivi的度等于的度等于vivi的的邻邻接点接点链链表中的表中的结结点个数点个数l在在有向有向图图的的领领接表接表中中l顶顶点点vivi的出度等于的出度等于vivi的的邻邻接点接点链链表中的表中的结结点个点个数；数；顶顶点点vivi的入度等于的入度等于v vi i在所有在所有领领接点接点链链表中出表中出现现的次数；的次数；38.7.2.2 邻邻接表接表l对对于于有向有向图图G中的每个中的每个顶顶点点vj，把所有，把所有邻邻接到接到vj的的顶顶点点vi链链成一个成一个单链单链表，表，这这个个单链单链表就称表就称为顶为顶点点vj的的逆逆邻邻接表接表。l如下例如下例2 21 16 62 26 64 43 31 12 23 34 45 56 639.7.3 图图的遍的遍历历l和和树树的遍的遍历类历类似，似，图图的遍的遍历历也是从某个也是从某个顶顶点出点出发发,沿着某条搜索路径沿着某条搜索路径访问图访问图中所有中所有顶顶点，且每个点，且每个顶顶点点仅仅被被访问访问一次。若一次。若给给定的定的图图是是连连通通图图，则则从从图图中任一中任一顶顶点出点出发发均可以均可以访问访问到到该图该图的所有的所有顶顶点。点。l由于由于图图中的任一中的任一顶顶点都可能和其余点都可能和其余顶顶点相点相邻邻接，接，故在故在访问访问了某个了某个顶顶点之后，可能点之后，可能顺顺着某条回路又着某条回路又回到了回到了该顶该顶点。因此，在遍点。因此，在遍历图历图的的过过程中，程中，为为了了避免重复避免重复访问访问同一个同一个顶顶点，必点，必须记须记住每个住每个顶顶点是点是否被否被访问过访问过。为为此，可此，可设设置一个置一个辅辅助数助数组组visitednvisitedn，它的初，它的初值为值为全全为为0 0，一旦，一旦访问访问了了顶顶点点vi vi，便将，便将visitedivisitedi置置为为1 1。l通常通常图图的遍的遍历历有两种路径：有两种路径：深度深度优优先搜索先搜索和和广度广度优优先搜索。先搜索。40.7.3.1 图图的深度的深度优优先搜索先搜索l深度深度优优先搜索先搜索类类似于似于树树的先序遍的先序遍历历。假。假设给设给定定图图G G的初的初态态是所有是所有顶顶点均未点均未访问过访问过，在，在G G中任中任选选一一顶顶点点vi vi作作为为初始出初始出发发点，点，则则深度深度优优先搜索先搜索可定可定义为义为：l首先，首先，访问访问出出发发点点vi vi，并将其，并将其标记标记为为已已访问过访问过，然后，依次从然后，依次从vi vi的的未曾未曾访问过访问过的的邻邻接点接点出出发继发继续进续进行深度行深度优优先搜索先搜索,直到直到图图中所有与中所有与vi vi有路径有路径相通的相通的顶顶点都被点都被访问访问到；到；l若此若此时图时图中中还还有有顶顶点未被点未被访问访问（即当（即当图为图为非非连连通通图时图时），），则则另另选图选图中一个未曾被中一个未曾被访问访问的的顶顶点点作起始点，重复上述作起始点，重复上述过过程，直到程，直到图图中所有中所有顶顶点点都被都被访问访问到到为为止。止。41.7.3.1 图图的深度的深度优优先搜索先搜索l例例1:图图的的深度深度优优先搜索先搜索1 12 23 34 45 56 67 78 8图图7.13(a)7.13(a)深度深度优优先搜索先搜索结结果果:v1-v2-v4-v8-v5-v3-v6-v7v1-v2-v4-v8-v5-v3-v6-v742.7.3.1 图图的深度的深度优优先搜索先搜索l深度深度优优先搜索算法如下：先搜索算法如下：lvoidDFSTraverse(GraphG,intv)lfor(v=0;vG.vexnum;v+)visitedv=0;lfor(v=0;vnext;l43.7.3.2 图图的的广广度度优优先搜索先搜索l广度广度优优先搜索先搜索类类似于似于树树的按的按层层次遍次遍历历。设图设图G G的初的初态态是所有是所有顶顶点均未点均未访问过访问过，在，在G G中任中任选选一一顶顶点点Vi Vi 为为初始出初始出发发点，点，则则广度广度优优先搜索的基本思想是：先搜索的基本思想是：l首先首先访问访问出出发发点点ViVi，接着依次，接着依次访问访问vi vi的所有的所有邻邻接点接点wlwl，w2w2，wtwt，然后，再依次，然后，再依次访问访问与与wlwl，w2w2，wtwt邻邻接的所有未曾接的所有未曾访问过访问过的的顶顶点，依此点，依此类类推，推，直至直至图图中所有和出中所有和出发发点点v v有路径相通的有路径相通的顶顶点都已点都已访访问问到到为为止止;l若此若此时图时图中尚有中尚有顶顶点未被点未被访问访问（即当（即当图为图为非非连连通通图图时时），则则另另选图选图中一个未曾被中一个未曾被访问访问的的顶顶点作起始点，点作起始点，重复上述重复上述过过程，直到程，直到图图中所有中所有顶顶点都被点都被访问访问到到为为止。止。44.7.3.2 图图的的广广度度优优先搜索先搜索l例例1:图图的广的广度度优优先搜索先搜索1 12 23 34 45 56 67 78 8图图7.13(a)7.13(a)广度广度优优先搜索先搜索结结果：果：v1-v2-v3-v4-v5-v6-v7-v8v1-v2-v3-v4-v5-v6-v7-v845.7.3.2 图图的的广广度度优优先搜索先搜索l广度广度优优先搜索先搜索算法如下：算法如下：lvoidBFS(GraphG,intv）lInitQueue(Q);lvisitedv=1;printf(“d”，v);lEnQueue(Q,v);lwhile(!QueueEmpty(Q)lDelQueue(Q,u);lfor(w=FirstAdjVex(G,u);w;w=wnext)lif(!visitedw)lvisitedw=1;printf(“d”，w);lEnQueue(Q,w);ll46.7.3.2 图图的的广广度度优优先搜索先搜索lvoidBFSTraverse(GraphG,intv)llfor(v=0;vG.vexnum;v+)visitedv=false;lfor(v=0;vG.vexnum;v+)lif(!visitedv)BFS(G,v);l47.7.4 图图的的连连通性通性问题问题l7.4.1 无向无向图图的的连连通分量和生成通分量和生成树树l l在无向在无向在无向在无向图图图图的遍的遍的遍的遍历历历历算法中，若从某个算法中，若从某个算法中，若从某个算法中，若从某个顶顶顶顶点出点出点出点出发访发访发访发访问问问问下一个下一个下一个下一个顶顶顶顶点点点点时时时时增加增加增加增加这这这这两个两个两个两个顶顶顶顶点之点之点之点之间间间间的的的的边边边边，则则则则可得到可得到可得到可得到连连连连通通通通图图图图的一棵生成的一棵生成的一棵生成的一棵生成树树树树或不或不或不或不连连连连通的通的通的通的图图图图的生的生的生的生成森林。成森林。成森林。成森林。l l由深度由深度由深度由深度优优优优先遍先遍先遍先遍历历历历得到的生成得到的生成得到的生成得到的生成树树树树称称称称为为为为深度深度深度深度优优优优先生先生先生先生成成成成树树树树。l l由广度由广度由广度由广度优优优优先遍先遍先遍先遍历历历历得到的生成得到的生成得到的生成得到的生成树树树树称称称称为为为为广度广度广度广度优优优优先生先生先生先生成成成成树树树树。48.7.4.2 最小生成最小生成树树l图图的生成的生成树树不是唯一的，从不同的不是唯一的，从不同的顶顶点出点出发进发进行遍行遍历历，可以得到不同的生成，可以得到不同的生成树树。l对对于于连连通网通网G G(V(V，E)E)而言，而言，图图中的中的边边是是带权带权的，因的，因而而G G的生成的生成树树的各条的各条边边也是也是带权带权的。我的。我们们把生成把生成树树各各条条边边的的权值总权值总和称和称为为生成生成树树的的权权（或称代价），并（或称代价），并把把权权最小最小的生成的生成树树称称为为G G的的最小生成最小生成树树。l生成生成树树和最小生成和最小生成树树有有许许多重要的多重要的应应用。例如：令用。例如：令图图G G的的顶顶点表示城市，点表示城市，边边表示表示连连接两个城市之接两个城市之间间的通的通讯线讯线路。路。n n个城市之个城市之间间最多可最多可设设立立n(n-1)n(n-1)2 2条条线线路，路，把把n n个城市个城市连连接起来至少要接起来至少要n-1n-1条条线线路路,则图则图G G的生成的生成树树表示了建立通表示了建立通讯讯网网络络的可行方案。的可行方案。49.7.4.2 最小生成最小生成树树l如果如果给图给图中的中的边边都都赋赋予予权权，而，而这这些些权权可表示两个可表示两个城市之城市之间间通通讯线讯线路的路的长长度或建造代价，那么，如度或建造代价，那么，如何何选择选择n-1n-1条条线线路，使得建立的通路，使得建立的通讯讯网网络络其其线线路路的的总长总长度最短或度最短或总总代价最小呢代价最小呢?这这就就转换为转换为如何如何构造构造该图该图的一棵最小生成的一棵最小生成树树的的问题问题。l以下我以下我们们只只讨论讨论无向无向图图的最小生成的最小生成树问题树问题。50.7.4.2 最小生成最小生成树树V1V2V4V3V5V6613555664251.7.4.2 最小生成最小生成树树l构造最小生成构造最小生成树树可以有多种算法，其中大多数可以有多种算法，其中大多数构造算法都是利用了最小生成构造算法都是利用了最小生成树树的下述的下述性性质质：设设G G(V,E E)是一个是一个连连通通带权图带权图，U是是顶顶点集点集V V的一个真子集。若的一个真子集。若边边(u,v)(u,v)（uU，vV-U）是是图图G G的所有的所有边边中中权值权值最小的一条最小的一条边边，则则一定一定存在存在图图G G的一棵最小生成的一棵最小生成树树包含此包含此边边(u,v)(u,v)。这这个性个性质质称称为为MSTMST性性质质。可用反。可用反证证法法证证明明(略略)l下面将重点介下面将重点介绍绍两个利用两个利用MSTMST性性质质构造最小生构造最小生成成树树的算法：的算法：普里姆（普里姆（PrimPrim）算法）算法和和克克鲁鲁斯卡斯卡尔尔（KruskalKruskal）算法）算法。52.7.4.2 最小生成最小生成树树lPrim算法算法的基本思想是：的基本思想是：l假假设设G=(V，E）是）是连连通网，通网，设设T=(U，TE)是是最小生成最小生成树树l初始情况下初始情况下设设Uu0(u0V）,TE.l重复重复执执行下述操作：行下述操作：在所有的在所有的uU，vVU的的边边(u，v)E中，中，找一条找一条权值权值最小的最小的边边（u0,v0)，将其并入集合，将其并入集合TE，同，同时时将将v0并入集合并入集合U，直至，直至UV为为止，止，此此时时TE中必有中必有n1条条边边，则则T=(U,TE)即即为为G的的一棵最小生成一棵最小生成树树。53.7.4.2 最小生成最小生成树树PrimPrimPrimPrim算法求最小生成算法求最小生成算法求最小生成算法求最小生成树树树树：1.1.1.1.（1,21,21,21,2）被）被）被）被选选选选中中中中 U=1,2 U=1,2 U=1,2 U=1,22.2.2.2.（2,52,52,52,5）被）被）被）被选选选选中中中中 U=1,2,5U=1,2,5U=1,2,5U=1,2,53.3.3.3.（2,32,32,32,3）被）被）被）被选选选选中中中中 U=1,2,3,5 U=1,2,3,5 U=1,2,3,5 U=1,2,3,54.4.4.4.（1,41,41,41,4）被）被）被）被选选选选中中中中 U=1,2,3,4,5 U=1,2,3,4,5 U=1,2,3,4,5 U=1,2,3,4,56.6.6.6.（5,75,75,75,7）被）被）被）被选选选选中中中中 U=1,2,3,4,5,6,7U=1,2,3,4,5,6,7U=1,2,3,4,5,6,7U=1,2,3,4,5,6,77.7.7.7.（7,87,87,87,8）被）被）被）被选选选选中中中中 U=1,2,3,4,5,6,7,8U=1,2,3,4,5,6,7,8U=1,2,3,4,5,6,7,8U=1,2,3,4,5,6,7,85.5.5.5.（3,63,63,63,6）被）被）被）被选选选选中中中中 U=1,2,3,4,5,6 U=1,2,3,4,5,6 U=1,2,3,4,5,6 U=1,2,3,4,5,6U=1,TE=U=1,TE=U=1,TE=U=1,TE=1 2 1 2 1 2 1 2 3143145353 4 9 4 9 4 9 4 9 1058910589 6 6 6 6 1 1 1 12 2 2 23 3 3 31 1 1 14 4 4 45 5 5 56 6 6 654.7.4.2 最小生成最小生成树树lKruskal算法算法的基本思想：的基本思想：l假假设设G=(V，E）是）是连连通网，通网，设设T=(U，TE)是要求是要求的最小生成的最小生成树树。l初始情况下初始情况下设设UV,TE.并将并将连连通网中的