第七章-图.ppt

第七章第七章-图图第七章第七章 图图l在在线性结构线性结构中，数据元素之间是一对一的线性中，数据元素之间是一对一的线性关系，除第一个数据元素和最后一个数据元素关系，除第一个数据元素和最后一个数据元素之外，每个数据元素只有一个直接前驱和一个之外，每个数据元素只有一个直接前驱和一个直接后继。直接后继。l在在树型结构树型结构中，数据元素之间是一对多的层次中，数据元素之间是一对多的层次和分支的关系，除根结点外，每个数据元素都和分支的关系，除根结点外，每个数据元素都只有一个直接前驱（即双亲结点），但每个数只有一个直接前驱（即双亲结点），但每个数据元素都可能有多个直接后继（即孩子结点）。据元素都可能有多个直接后继（即孩子结点）。l然而在然而在图型结构图型结构中，数据元素之间的关系是任中，数据元素之间的关系是任意的，是多对多的关系，既图中任意两个结点意的，是多对多的关系，既图中任意两个结点之间都可能相关。之间都可能相关。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只有顶点而没有边。只有顶点而没有边。图可分为图可分为无向图无向图和和有向图有向图两类。两类。7.1 图的定义和术语图的定义和术语l无向图无向图：图中的每条边都是无方向的。图中的每条边都是无方向的。l在无向图中，一条无向边是由两个顶点组成的在无向图中，一条无向边是由两个顶点组成的无序对无序对，通常用，通常用圆括号圆括号表示。例如（表示。例如（vi，vj）表示一条无向边，表示一条无向边，在无向图中，（在无向图中，（vi，vj）和）和（vj，vi）是两条相同的无向边。）是两条相同的无向边。l（无向）完全图（无向）完全图：任意两个顶点之间都有一条任意两个顶点之间都有一条无向边的无向图。无向边的无向图。l（无向）完全图是（无向）完全图是含有含有n n个顶点和个顶点和n(n-1)/2n(n-1)/2条边条边的无向图。的无向图。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相关联相关联。7.1 图的定义和术语图的定义和术语l有向图有向图：图中的每条边都是有方向的。图中的每条边都是有方向的。l在有向图中，一条有向边是由两个顶点组成的在有向图中，一条有向边是由两个顶点组成的有序对有序对，通常用，通常用尖括号尖括号表示。例如表示。例如表表示一条有向边，示一条有向边，vi是边的起始点，是边的起始点，vj是边的终是边的终点。因此，点。因此，和和是两条不同的是两条不同的有向边。有向边。l有向边也称为有向边也称为弧弧，边的起始点称为，边的起始点称为弧尾弧尾，终点，终点称为称为弧头弧头。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.1 图的定义和术语图的定义和术语l有向完全图有向完全图：任意两个顶点之间都有一对相向的任意两个顶点之间都有一对相向的有向边的有向图。即含有有向边的有向图。即含有n n个顶点和个顶点和n(n-1)n(n-1)条弧（有条弧（有向边）的有向图。向边）的有向图。ABECF1597211132l权权：与图的边或弧相关的数。：与图的边或弧相关的数。这些权可以表示从一个顶点到这些权可以表示从一个顶点到另一个顶点的距离或者耗费。另一个顶点的距离或者耗费。l网网：弧（或边）带权的图称为：弧（或边）带权的图称为网。网。7.1 图的定义和术语图的定义和术语l子图子图：给定给定图G1=G1=（V1V1，E1E1）、）、图G2=G2=（V2V2，E2E2），若），若V1V1是是V2V2的子集，的子集，E1E1是是E2E2的子集，则的子集，则称称G1G1是是G2G2的的子图子图。l例：例：ABECF图图G GAB图图G1G1CF图图G3G3E图图G2G2CE图图G4G47.1 图的定义和术语图的定义和术语l无向图中顶点无向图中顶点v v的的度：度：指的是和指的是和v v相关联的相关联的边的数目边的数目，通常记为通常记为D(v)D(v)。BCAFED例：在右图中例：在右图中D(B)=D(F)3D(A)=D(C)=D(D)=D(E)=2结论结论无向图中：顶点的度之和无向图中：顶点的度之和=边数的两倍边数的两倍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)。7.1 图的定义和术语图的定义和术语l例：在下面的例：在下面的有向有向图中图中lID(A)=1；OD(A)=2;D(A)=3lID(C)=1；OD(C)=1;D(C)=3ABECF结论结论有向图中：顶点入度之和有向图中：顶点入度之和=顶点出度之和顶点出度之和=弧数弧数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可以相同外，其余顶点均不可以相同外，其余顶点均不相同，则称此路径为相同，则称此路径为简单回路简单回路或或简单环简单环。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，它，它是一条简单回路是一条简单回路。ABECF7.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的一个的一个连通连通分量。分量。显然，任何连通图的连通分量只有一个，显然，任何连通图的连通分量只有一个，就是它自身，而非连通的无向图有多个连通分就是它自身，而非连通的无向图有多个连通分量。量。7.1 图的定义和术语图的定义和术语l例如：下图所示为两个无向图例如：下图所示为两个无向图G1G1和和G2G2，其中，其中:G1 G1是一个连通图是一个连通图 G2 G2是由是由4 4个连通分量组成的非连通图。个连通分量组成的非连通图。BCAFED无向图无向图G1G1BEADCGHIFJ无向图无向图G2G27.1 图的定义和术语图的定义和术语l在有向图在有向图G中，若对于其中的任意两个不同的中，若对于其中的任意两个不同的顶点顶点vi和和vj，从，从vi到到vj和从和从vj到到vi都存在路径，都存在路径，则称则称G是是强连通图强连通图。l有向图有向图G的极大强连通子图称为的极大强连通子图称为G的的强连通分强连通分量量。显然，强连通图只有一个强连通分量，即。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分是其自身。非强连通的有向图有多个强连通分量。量。7.1 图的定义和术语图的定义和术语l例如：下图所示为两个有向图例如：下图所示为两个有向图G1G1和和G2G2，其中，其中:G1 G1是一个强连通图，是一个强连通图，G2 G2是由是由3 3个强连通分量组成的非连通图。个强连通分量组成的非连通图。ABECF有向图有向图G1G1ABECF有向图有向图G2G27.1 图的定义和术语图的定义和术语l结论结论l有有n个顶点的个顶点的有向图有向图最多有最多有条边，最少条边，最少有有 条边。条边。l有有n个顶点的个顶点的无向图无向图最多有最多有条边，最条边，最少有少有条边。条边。l有有n个顶点的个顶点的连通图连通图最少有最少有条边，若少于条边，若少于条边，图一定是非连通图，多于条边，图一定是非连通图，多于条边，条边，连通图中一定有环路存在。连通图中一定有环路存在。n(n-1)n(n-1)/200n-1n-1n-17.1 图的定义和术语图的定义和术语l生成树生成树：一个：一个连通图连通图的生成树是一个的生成树是一个极小连通子图极小连通子图，它含有图中全部顶点，但只含有足以构成一棵树的它含有图中全部顶点，但只含有足以构成一棵树的n-1n-1条边。条边。l如图所示：连通图如图所示：连通图G G的一棵生成树的一棵生成树l注意注意:一棵有一棵有n n个顶点的生成树一定有个顶点的生成树一定有n-1n-1条边。但有条边。但有n n个个顶点和顶点和n-1n-1条边的图，一定是一棵生成树吗？条边的图，一定是一棵生成树吗？ABECFABECF1 1棵生成树棵生成树7.2 图的存储结构图的存储结构l由于图的结构比较复杂，除了要把图的各顶点存由于图的结构比较复杂，除了要把图的各顶点存入计算机，还应该把各顶点之间的关系也输入计入计算机，还应该把各顶点之间的关系也输入计算机，而图中任意两个顶点之间都可能存在联系，算机，而图中任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映象的存储结示元素之间的关系，即图没有顺序映象的存储结构，但可以借助数组的数据类型表示图中顶点之构，但可以借助数组的数据类型表示图中顶点之间的关系，即间的关系，即图的领接矩阵的存储结构图的领接矩阵的存储结构。l另一方面，也可以用链表表示图，如另一方面，也可以用链表表示图，如领接表领接表、领领接多重表接多重表和和十字链表十字链表是图常用的三种链式存储结是图常用的三种链式存储结构。构。7.2 图的存储结构图的存储结构l对于具体问题中的图来说对于具体问题中的图来说,要为其要为其选择最好的存选择最好的存储结构储结构，不仅仅，不仅仅要依赖于图的性质要依赖于图的性质如有向图还如有向图还是无向图是无向图,以及以及图中的数据图中的数据,例如例如:顶点数顶点数,边数等边数等,而且还与而且还与在图上所实施的操作在图上所实施的操作有关，例如对图有关，例如对图中的顶点进行插入或删除操作的频率等中的顶点进行插入或删除操作的频率等.l下面将主要介绍图的下面将主要介绍图的领接矩阵领接矩阵和和领接表领接表这两种这两种存储方式。存储方式。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 反之反之反之反之7.2.1 7.2.1 邻接矩阵邻接矩阵l l例例例例1 1：给定给定给定给定4 4个顶点的有向图个顶点的有向图个顶点的有向图个顶点的有向图7.2.1 7.2.1 邻接矩阵邻接矩阵l例例2：给定给定6个顶点的无向图个顶点的无向图A注注:无向图的邻接矩阵是对称的，即无向图的邻接矩阵是对称的，即 Aij=Aji Aij=Aji7.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为边上的权值为边上的权值为边上的权值为边上的权值 反之反之反之反之7.2.1 7.2.1 邻接矩阵邻接矩阵l l例：给定例：给定例：给定例：给定6 6 6 6个顶点的无向网（无向带权图）个顶点的无向网（无向带权图）个顶点的无向网（无向带权图）个顶点的无向网（无向带权图）5781014124A=55885 107107 41441444 12128108107141271412无向网无向网无向网无向网G1G1G1G1及其领接及其领接及其领接及其领接矩阵存储结构矩阵存储结构矩阵存储结构矩阵存储结构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的领接矩阵存储结构的领接矩阵存储结构的领接矩阵存储结构的领接矩阵存储结构有向带权图有向带权图有向带权图有向带权图G2G27.2.1 7.2.1 邻接矩阵邻接矩阵l结论结论l在在无向图无向图的领接矩阵中的领接矩阵中,顶点顶点vivi的度等于邻接的度等于邻接矩阵中第矩阵中第i i行行(或第或第i i列列)上非零元素的个数；上非零元素的个数；l在在有向图有向图的领接矩阵中，顶点的领接矩阵中，顶点vivi的出度等于邻的出度等于邻接矩阵中的第接矩阵中的第i i行上非零元素的个数行上非零元素的个数;l在在有向图有向图的领接矩阵中，顶点的领接矩阵中，顶点vivi的入度等于邻的入度等于邻接矩阵中的第接矩阵中的第i i列上非零元素的个数列上非零元素的个数.7.2.1 7.2.1 邻接矩阵邻接矩阵l图的领接矩阵存储表示图的领接矩阵存储表示用用邻邻接接矩矩阵阵表表示示法法表表示示图图，除除了了存存储储用用于于表表示示顶顶点点间间相相邻邻关关系系的的邻邻接接矩矩阵阵外外，通通常常还还需需要要用用一一个个顺顺序序表表来来存储图的顶点信息。其形式说明如下：存储图的顶点信息。其形式说明如下：#definen6/*图的顶点数图的顶点数*/#definee8/*图的边（弧）数图的边（弧）数*/typedefstructcharvexsn+1；/*设顶点的数据类型设顶点的数据类型为为char型型*/intarcsn+1n+1；/*设权值类型为设权值类型为int*/Graph；GraphG;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；7.2.1 7.2.1 邻接矩阵邻接矩阵l分析该分析该算法的时间复杂度算法的时间复杂度算法的执行时间是算法的执行时间是O(n+n2+e)，其中，其中O(n2)的时的时间耗费在邻接矩阵的初始化操作上。因为间耗费在邻接矩阵的初始化操作上。因为en2，所以，算法的时间复杂度是，所以，算法的时间复杂度是O(n2)。7.2.2 邻接表邻接表l领接表是图的一种链式存储结构。类似于树的领接表是图的一种链式存储结构。类似于树的孩子链表表示法。孩子链表表示法。l在领接表存储结构中，对于图在领接表存储结构中，对于图G G中的每个顶点中的每个顶点vi vi，把，把vi vi的所有邻接点链成一个单链表，这个的所有邻接点链成一个单链表，这个单链表就称为单链表就称为顶点顶点vi vi的邻接点单链表的邻接点单链表。那么，。那么，若图有若图有n n个顶点，就有个顶点，就有n n个领接点单链表。个领接点单链表。l为了便于为了便于随机访问任一顶点随机访问任一顶点的的邻接点单链表邻接点单链表，通常将所有邻接点单链表的通常将所有邻接点单链表的头结点头结点顺序存储在顺序存储在一个结构体数组中。一个结构体数组中。7.2.2 邻接表邻接表ln n个领接点单链表的表头结点结构均为：含有个领接点单链表的表头结点结构均为：含有两个域，一个是两个域，一个是顶点域顶点域，用来存放顶点，用来存放顶点vi vi的信的信息；另一个是息；另一个是指针域指针域，用来指向，用来指向vi vi的领接点单的领接点单链表中的第一个结点。链表中的第一个结点。l在顶点在顶点vi vi的邻接点单链表中，的邻接点单链表中，每个结点均有两每个结点均有两个域，一个是个域，一个是邻接点域邻接点域，用以存放与，用以存放与vi vi的领接的领接点点vj vj的信息；另一个是的信息；另一个是指针域指针域，用来指向与，用来指向与vi vi相邻的下一个领接点。相邻的下一个领接点。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注意注意：图的邻接矩阵表示是唯一的，但其邻接表不唯一：图的邻接矩阵表示是唯一的，但其邻接表不唯一7.2.2 邻接表邻接表l例例2：图的领接表存储结构：图的领接表存储结构V5V3V2V6V1V42 25 55 51 16 66 66 64 43 32 22 24 43 31 1V1V2V3V4V5V67.2.2 邻接表邻接表l创建创建领接表的领接表的算法思想算法思想l建立无向图的邻接表建立无向图的邻接表时，每读入一个顶点对（时，每读入一个顶点对（i,j）时，就创建一个邻接点序号为时，就创建一个邻接点序号为j的新结点，将其插的新结点，将其插入到入到vi为表头结点的领接点单链表中；同时生成一为表头结点的领接点单链表中；同时生成一个邻接点序号为个邻接点序号为i的新结点，将其插入到的新结点，将其插入到vj为表头为表头结点的单链表中。结点的单链表中。l建立有向图的邻接表建立有向图的邻接表与此类似，只是更加简单，与此类似，只是更加简单，每读入一个顶点对序号每读入一个顶点对序号i，j时，仅需生成一个时，仅需生成一个邻接点序号为邻接点序号为j的新结点，将其插入到的新结点，将其插入到vi为表头结为表头结点的领接点单链表中即可。点的领接点单链表中即可。l若若建立网络的邻接表建立网络的邻接表，则需在链表的每个结点中，则需在链表的每个结点中增加一个存储边上的权值的数据域。增加一个存储边上的权值的数据域。7.2.2 邻接表邻接表l领接表存储结构的结论领接表存储结构的结论l在在无向图的领接表无向图的领接表中中 顶点顶点vivi的度等于的度等于vivi的邻接点链表中的结点个数的邻接点链表中的结点个数l在在有向图的领接表有向图的领接表中中l顶点顶点vivi的出度等于的出度等于vivi的邻接点链表中的结点个的邻接点链表中的结点个数；数；顶点顶点vivi的入度等于的入度等于v vi i在所有领接点链表中出现在所有领接点链表中出现的次数；的次数；7.2.2 邻接表邻接表l对于对于有向图有向图G中的每个顶点中的每个顶点vj，把所有，把所有邻接到邻接到vj的顶点的顶点vi链成一个单链表，这个单链表就称链成一个单链表，这个单链表就称为顶点为顶点vj的的逆邻接表逆邻接表。l如下例如下例2 21 16 62 26 64 43 31 12 23 34 45 56 67.3 图的遍历图的遍历l和树的遍历类似，和树的遍历类似，图的遍历图的遍历也是从某个顶点出发也是从某个顶点出发,沿着某条搜索路径访问图中所有顶点，且每个顶沿着某条搜索路径访问图中所有顶点，且每个顶点仅被访问一次。若给定的图是连通图，则从图点仅被访问一次。若给定的图是连通图，则从图中任一顶点出发均可以访问到该图的所有顶点。中任一顶点出发均可以访问到该图的所有顶点。l由于图中的任一顶点都可能和其余顶点相邻接，由于图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。因此，在遍历图的过程中，为了回到了该顶点。因此，在遍历图的过程中，为了避免重复访问同一个顶点，必须记住每个顶点是避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个辅助数组否被访问过。为此，可设置一个辅助数组visitednvisitedn，它的初值为全为，它的初值为全为0 0，一旦访问了顶点，一旦访问了顶点vi vi，便将，便将visitedivisitedi置为置为1 1。l通常图的遍历有两种路径：通常图的遍历有两种路径：深度优先搜索深度优先搜索和和广度广度优先搜索。优先搜索。7.3.1 图的深度优先搜索图的深度优先搜索l深度优先搜索类似于树的先序遍历深度优先搜索类似于树的先序遍历。假设给定。假设给定图图G G的初态是所有顶点均未访问过，在的初态是所有顶点均未访问过，在G G中任中任选一顶点选一顶点vi vi作为初始出发点，则深度优先搜索作为初始出发点，则深度优先搜索可定义为：可定义为：l首先，访问出发点首先，访问出发点vi vi，并将其，并将其标记标记为已访问过，为已访问过，然后，依次从然后，依次从vi vi的的未曾访问过的邻接点未曾访问过的邻接点出发继出发继续进行深度优先搜索续进行深度优先搜索,直到图中所有与直到图中所有与vi vi有路径有路径相通的顶点都被访问到；相通的顶点都被访问到；l若此时图中还有顶点未被访问若此时图中还有顶点未被访问（即当图为非连（即当图为非连通图时），通图时），则另选图中一个未曾被访问的顶点则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。都被访问到为止。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-v77.3.1 图的深度优先搜索图的深度优先搜索l深度优先搜索算法如下：深度优先搜索算法如下：lvoidDFSTraverse(GraphG,intv)lfor(v=0;vG.vexnum;v+)visitedv=0;lfor(v=0;vnext;l7.3.2 图的图的广广度优先搜索度优先搜索l广度优先搜索类似于树的按层次遍历广度优先搜索类似于树的按层次遍历。设图。设图G G的初的初态是所有顶点均未访问过，在态是所有顶点均未访问过，在G G中任选一顶点中任选一顶点Vi Vi 为初始出发点，则广度优先搜索的基本思想是：为初始出发点，则广度优先搜索的基本思想是：l首先访问出发点首先访问出发点ViVi，接着依次访问，接着依次访问vi vi的所有邻接点的所有邻接点wlwl，w2w2，wtwt，然后，再依次访问与，然后，再依次访问与wlwl，w2w2，wtwt邻接的所有未曾访问过的顶点，依此类推，邻接的所有未曾访问过的顶点，依此类推，直至图中所有和出发点直至图中所有和出发点v v有路径相通的顶点都已访有路径相通的顶点都已访问到为止问到为止;l若此时图中尚有顶点未被访问若此时图中尚有顶点未被访问（即当图为非连通图（即当图为非连通图时）时），则另选图中一个未曾被访问的顶点作起始点，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为重复上述过程，直到图中所有顶点都被访问到为止。止。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-v87.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);ll7.3.2 图的图的广广度优先搜索度优先搜索lvoidBFSTraverse(GraphG,intv)llfor(v=0;vG.vexnum;v+)visitedv=false;lfor(v=0;vG.vexnum;v+)lif(!visitedv)BFS(G,v);l7.4 图的连通性问题图的连通性问题l7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树l l在无向图的遍历算法中，若从某个顶点出发访在无向图的遍历算法中，若从某个顶点出发访在无向图的遍历算法中，若从某个顶点出发访在无向图的遍历算法中，若从某个顶点出发访问下一个顶点时增加这两个顶点之间的边，则问下一个顶点时增加这两个顶点之间的边，则问下一个顶点时增加这两个顶点之间的边，则问下一个顶点时增加这两个顶点之间的边，则可得到连通图的一棵生成树或不连通的图的生可得到连通图的一棵生成树或不连通的图的生可得到连通图的一棵生成树或不连通的图的生可得到连通图的一棵生成树或不连通的图的生成森林。成森林。成森林。成森林。l l由深度优先遍历得到的生成树称为深度优先生由深度优先遍历得到的生成树称为深度优先生由深度优先遍历得到的生成树称为深度优先生由深度优先遍历得到的生成树称为深度优先生成树。成树。成树。成树。l l由广度优先遍历得到的生成树称为广度优先生由广度优先遍历得到的生成树称为广度优先生由广度优先遍历得到的生成树称为广度优先生由广度优先遍历得到的生成树称为广度优先生成树。成树。成树。成树。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的生成树的生成树表示了建立通讯网络的可行方案。表示了建立通讯网络的可行方案。7.4.2 最小生成树最小生成树l如果给图中的边都赋予权，而这些权可表示两个如果给图中的边都赋予权，而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如城市之间通讯线路的长度或建造代价，那么，如何选择何选择n-1n-1条线路，使得建立的通讯网络其线路条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢的总长度最短或总代价最小呢?这就转换为如何这就转换为如何构造该图的一棵最小生成树的问题。构造该图的一棵最小生成树的问题。l以下我们只讨论以下我们只讨论无向图无向图的最小生成树问题。的最小生成树问题。7.4.2 最小生成树最小生成树V1V2V4V3V5V661355566427.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）算法）算法。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的的一棵最小生成树。一棵最小生成树。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 67.4.2 最小生成树最小生成树lKruskal算法算法的基本思想：的基本思想：l假设假设G=(V，E）是连通网，设）是连通网，设T=(U，TE)是要求是要求的最小生成树。的最小生成树。l初始情况下设初始情况下设UV,TE.并将连通网中的所并将连通网中的所有边按权值的非递减次序进行排列，然后执行：有边按权值的非递减次序进行排列，然后执行：依次将连通网中有序排列的各条边（依次将连通网中有序排列的各条边（u,v）作如下）作如下处理：若将（处理：若将（u,v）加入）加入TE中后，中后，TE中的边构成中的边构成了一条回路，则不将（了一条回路，则不将（u,v）加入）加入TE中；否则将中；否则将（u,v）加入）加入TE中。重复上述过程，直至中。重复上述过程