数据结构课件严冬梅2017春-07图

主讲：严冬梅第7章图（Graph）数据结构（DataStructure）第7章图

图是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素最多只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间存在明显的层次关系，并且每层的元素可能和下一层的多个元素相邻，但只能和上一层的一个元素相邻。而在图形结构中，结点之间的关系可以是任意的，图中的任意两个元素之间都可能相邻。图是计算机应用过程中对实际问题进行数学抽象和描述的强有力的工具，数据结构中对图的讨论侧重于在计算机中如何表示图以及如何实现图的操作和应用等。第7章图和广义表7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径7.1图的定义和术语图由一个顶点的有穷非空集合V(G)和一个弧的集合E(G)组成，通常记做G=(V,E)。

V是顶点的非空有限集；

E是边(V中顶点的有序或无序偶对)的有限集有向图：弧<v,w>

v为弧尾或始点，w为弧头或终点无向图：边(v,w)

表示<v,w>和<w,v>7.1图的定义和术语图G1是一个有向图，G1=(V1,{A1})。其中:V1={A,C,B,F,D,E,G}A1={<A,B>,<B,C>,<B,F>,<B,E>,<C,E>,<E,D>,<D,C>,<E,B>,<F,G>}ACBFDGE有向图G1ViVj弧<Vi,Vj>弧尾(起始点)Vi邻接到VjVj邻接自Vi弧头(终端点)7.1图的定义和术语图G2是一个无向图，G2=(V2,{E2})。其中：

V2={A,B,C,D,E,F}E2={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,E)}ABCDEF无向图G2ViVj边(Vi,Vj)或(Vj,Vi)顶点Vi与Vj互为邻接点7.1图的定义和术语

在实际应用中，图的弧或边往往与具有一定意义的数相关，称这些数为权(weight)。分别称带权的有向图和无向图为有向网和无向网。123456712345671918212756103311706475806018069584331324430无向网有向网

子图假设有两个图G=(V,{E})和G’=(V’,{E’})，若V’V且E’E，则称G’为G的子图。7.1图的定义和术语V1V3V4V2GV1G’’’V1V4V2G’’V1V2G’

稀疏图和稠密图假设用n表示图中顶点数目，用e表示边或弧的数目。若不考虑顶点到其自身的弧或边，则对于无向图，边数e的取值范围是0到n(n-1)/2。称具有n(n-1)/2条边的无向图为完全图。对于有向图，弧的数目e的取值范围是0到n(n-1)。称具有n(n-1)条弧的有向图为有向完全图。若e<nlogn，则称为稀疏图，反之称为稠密图。7.1图的定义和术语有向完全图：e=n(n-1)无向完全图：

e=n(n-1)/2V1V2V3V4V1V2V3V4e＝12e＝67.1图的定义和术语7.1图的定义和术语度、入度和出度入度ID(v)：邻接到某顶点v的弧的数目出度OD(u)：从顶点u出发的弧的数目度TD(v)：

有向图顶点v的入度和出度之和无向图中顶点的度定义为与该顶点相连的边数ID(B)=2OD(B)=3TD(B)=5ACBFDGE7.1图的定义和术语路径和回路有向路径：若有向图G中k+1个顶点之间都有弧存在，则这个顶点序列{v0,v1,…vk}为从顶点v0到顶点vk的一条有向路径，路径中弧的数目定义为路径长度。简单路径：序列中顶点不重复的路径

对无向图，相邻顶点之间存在边的k+1个顶点序列构成一条长度为k的无向路径。回路或环：若v0和vk是同一个顶点，则是一条由某个顶点出发又回到自身的路径，称这种路径为回路或环。路径：V1,V4,V2,V1,V3路径长度＝4V1V7V4V3V5V6V2回路：V1,V2,V5,V6,V2,V1路径长度＝5V1V3V4V27.1图的定义和术语7.1图的定义和术语无向图的连通性连通：如果G中顶点Vi与Vj之间有路径，称Vi与Vj是连通的连通图：无向图G中任意两个顶点之间都连通连通分量：无向图G的极大连通子图称为G的一个连通分量V1V3V4V2AEFDCB连通图G1非连通图G2ADCBEFG2的两个连通分量7.1图的定义和术语有向图的连通性弱连通图：如果有向图G去掉每条边的方向后得到的无向图是连通的，称G是弱连通图。单向连通图：如果G中任意两个顶点之间至少一个可达另一个，则称G是单向连通图。强连通：如果Vi到Vj有路径，Vj到Vi也有路径，称Vi到Vj是强连通的；强连通图：有向图G中任意两个顶点之间都强连通；强连通分量：有向图G的极大强连通子图称为G的一个强连通分量。强连通图一定是单向连通图；单向连通图一定是弱连通图。V1V4V2V3V1V4V2V3V1V4V2V3强连通图所有顶点互相可达单向连通图v1无法到达v2、v4V3无法到达v1、v2弱连通图v1、v4无通路7.1图的定义和术语弱连通图单向连通图强连通图非强连通图G3G3的两个强连通分量V1V3V4V2V1V3V4V2V3V1V4V27.1图的定义和术语图论中对树的定义：无回路的连通图（n个顶点，n-1条边）7.1图的定义和术语无向连通图的生成树：设G（V，E）是具有n个顶点的无向连通图，G的生成树是G的一个极小连通子图，它包含了G的n个顶点及构成树的n-1条边。V1V7V4V3V5V6V2V1V7V4V3V5V6V2V1V7V4V3V5V6V2对非连通图G而言，其每个连通分量都具有相应的生成树，构成了G的生成森林。7.1图的定义和术语7.1图的定义和术语图的抽象数据类型ADTGraph{

数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。数据关系R:R={VR}VR={<v,w>|v,w∈P(v,w),<v,w>表示从v到w的弧,

谓词P(v,w)定义了弧<v,w>的意义或信息}

基本操作：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestoryGraph(&G)初始条件：图G存在。操作结果：销毁图G。more7.1图的定义和术语LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。GetVex(G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的值。PutVex(&G,v,value)初始条件：图G存在，v是G中的某个顶点。操作结果：对v赋值value。more7.1图的定义和术语FirstAdjVex(G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的第一个邻接点，若该顶点在G中无邻接点，则返回空。NextAdjVex(G,v,w)初始条件：图G存在，v是G中的某个顶点，w是v的邻接顶点。操作结果：返回v的(相对于w的)下一个邻接点。若w是v的最后一个邻接点，则返回空。InsertVex(&G,v)

初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。more7.1图的定义和术语DeleteVex(&G,v)

初始条件：图G存在，v是G中的某个顶点。操作结果：删除G中顶点v及其相关的弧。

InsertArc(&G,v,w)

初始条件：图G存在，v和w是G中的两个顶点。操作结果：在图G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>。

DeleteArc(&G,v,w)

初始条件：图G存在，v和w是G中的两个顶点。操作结果：在图G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>。more7.1图的定义和术语

DFSTraverse(G,v,visit())

初始条件：图G存在，v是G中的某个顶点，visit是针对顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。

BFSTraverse(G,v,visit())

初始条件：图G存在，v是G中的某个顶点，visit是针对顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。}ADTGraph7.2图的存储结构图是一种典型的复杂结构，图中顶点可能同任意一个其他顶点之间存在关系。因此，图没有顺序映象的存储结构。图有两种常用的存储结构。邻接矩阵表示法邻接表表示法7.2图的存储结构7.2.1图的数组(邻接矩阵)存储表示邻接矩阵是用于描述图中顶点之间的关系(及弧或边的权)的矩阵，假设图中顶点数为n，则邻接矩阵A=(ai,j)m*n定义为：A[i][j]=1若Vi和Vj之间有弧或边存在0Vi和Vj之间没有弧或边存在A[i][j]=wij

若Vi和Vj之间有弧或边存在∞

Vi和Vj之间没有弧或边存在7.2.1图的数组(邻接矩阵)存储表示ACBFDGEABCDEF有向图G1无向图G2G1的邻接矩阵G2的邻接矩阵7.2.1图的数组(邻接矩阵)存储表示一般情况下，图中没有邻接到自身的弧，因此矩阵中主对角线全为零。由于无向图中一条边视为一对弧，则无向图的邻接矩阵必然是对称矩阵。网的邻接矩阵定义中，当vi到vj有弧相邻接时，ai,j的值为该弧上的权值，否则为∞。12345677064758060180695843313244307.2.1图的数组(邻接矩阵)存储表示有向图的邻接矩阵大多为稀疏矩阵，可以采用压缩存储表示,用二维数组表示更为方便.constINFINITY_INT_MAX=MAX;//最大值∞设为MAXconstMAX_VERTEX_NUM=20;//最大顶点个数typedef

enum{DG,DN,AG,AN}GraphKind;//图类型(有向图、有向网、无向图、无向网)typedefstructArcCell{ VRTypeadj;//VRType为顶点的关系类型。对无权图，//用1或0表示是否相邻；对带权图则为权值类型

InfoType*info;//指向该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//描述顶点的数组

AdjMatrixarcs;//邻接矩阵

intvexnum,arcnum;//图的当前顶点数和弧(边)数

GraphKindkind;//图的种类标志}MGraph;vexs[0]……vexs[MAX_VERTEX_NUM-1]arcs[0][0].adj

arcs[0][0].info

……arcs[MAX_VERTEX_NUM-1][MAX_VERTEX_NUM-1].adjarcs[MAX_VERTEX_NUM-1][MAX_VERTEX_NUM-1].infovexnumarcnumkind此项可以省略7.2.1图的数组(邻接矩阵)存储表示voidCreateMGragh(MTGragh&G)//建立(无向网)的邻接矩阵{cin>>G.vexnum>>G.arcnum>>IncInfo;//输入顶点数和边数

for(i=0;i<G.vexnum;i++)

cin>>G.vexs[i];//读入顶点信息，建立顶点表

for(i=0;i<G.vexnum;i++)

for(j=0;j<G.vexnum;j++)G.arcs[i][j]={INFINITY,NULL}//邻接矩阵初始化

for(k=0;k<G.arcnum;k++){//读入e条边建立邻接矩阵

cin>>i>>j>>w;//cin>>u>>v>>w

//i=LocateVex(G,u);j=LocateVex(G,v);G.arcs[i][j].adj=w;//w是边(i,j)上的权if(IncInfo)cin>>G.arcs[j][i].info=w;G.arcs[j][i]=G.arcs[i][j];}//空间复杂性：S=O(n+n2)}//时间复杂性：T=O(n+n2+e)。当e<n2,T=O(n2)V1V7V4V3V5V6V2V1V2V3V4V5V6V70123456012345600111000110001112100000131000000401000105010010060110000G.arcs=G.vexs=无向图的邻接矩阵存放顶点的数组表示边的矩阵7.2.1图的数组(邻接矩阵)存储表示7.2.1图的数组(邻接矩阵)存储表示无向图邻接矩阵的特点：对称矩阵顶点Vi的度等于第i行非零元个数，或第i列非零元个数：矩阵非零元总数等于边数的2倍V1V2V3V4V5V6V7V80123456701234567001110000100101100200000100300100110400000001500001010600000001700000000G.arcs=G.vexs=V1V7V4V3V5V6V2V8有向图的邻接矩阵存放顶点的数组表示弧的矩阵V4的出边邻接点V4的入边邻接点7.2.1图的数组(邻接矩阵)存储表示有向图邻接矩阵的特点：是非对称矩阵第i行非零元个数等于顶点Vi的出度；第i列非零元个数等于顶点Vi的入度：矩阵非零元总数等于边数

7.2.1图的数组(邻接矩阵)存储表示7.2.2图的数组(邻接矩阵)存储表示邻接矩阵的优点:容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等邻接矩阵的缺点:n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。7.2.2图的邻接表存储表示邻接表是图的一种链式存储表示方法，它类似于树的孩子链表。在有向图的邻接表中，从同一个顶点出发的弧链接在同一链表中，邻接表中结点的个数恰好为图中弧的个数。在无向图的邻接表中，同一条边有两个结点，分别出现在和它相关的两个顶点的链表中，因此无向图的邻接表中结点个数是边的两倍。7.2.2图的邻接表存储表示ACBFDGE有向图G1MAX_VERTEX_NUMABCEDFG^……--01234561^3^6^12^4^245^7.2.2图的邻接表存储表示MAX_VERTEX_NUMABCEDF……--012345ABCDEF无向图G22^1024015^345^2^125^124^7.2.2图的邻接表存储表示constMAX_VERTEX_NUM=20;typedefstructArcNode{

intadjvex;//该弧所指向的顶点的位置

structArcNode*nextarc;//指向下一条弧的指针

InfoType*info; //指向该弧相关信息的指针}ArcNode; typedefstructVNode{VertexTypedata;//顶点信息

ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;

intvexnum,arcnum;//图的当前顶点数和弧数

intkind; //图的种类标志}ALGraph;adjvexnextarcinfodatafirstarcvoid

CreateUDG(ALGraph&G){//采用邻接表存储表示，构造无向图G(G.kind=UDG)cin>>G.vexnum>>G.arcnum>>Incinfo;

for(i=0;i<G.vexnum;++i){ //构造表头向量

cin>>G.vertices[i].data; //输入顶点值

G.vertices[i].firstarc=NULL; //初始化链表头指针为空

}//for

for

(k=0;k<G.arcnum;++k){ //输入各边并构造邻接表

cin>>v1>>v2; //输入一条弧的始点和终点

//确定v1和v2在G中的位置，即顶点在G.Vertices中的序号

i=LocateVex(G,v1);j=LocateVex(G,v2);

pi=newArcNode;pi->adjvex=j;//对弧结点赋邻接点“位置”信息

pi->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=pi;//插入链表G.vertices[i]pj=newArcNode;pj->adjvex=i;//对弧结点赋邻接点“位置”信息

pj->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=pj;//插入链表G.vertices[j]

if

(IncInfo){//若弧含有相关信息，则输入

cin>>pj->info;pi->info=pj->info;}}//for}//CreateUDG算法7.1V1V7V4V3V5V6V2data0V11V22V33V44V55V66V7891∧321∧5∧4∧601∧0firstarc645∧0∧21G.vertices无向图的邻接表：adjvexnextarc7.2.2图的邻接表存储表示有向图的邻接表：V1V7V4V3V5V6V2V8data0V11V22V33V44V55V66V78V8∧91∧32∧7∧6∧54firstarcadjvexnextarc54∧2∧724∧5G.vertices7.2.2图的邻接表存储表示有向图的逆邻接表：data0V1∧1V22V33V44V55V66V78V891∧32∧0∧5∧01firstarcadjlistnextarcG.vertices01∧3∧53∧74V1V7V4V3V5V6V2V87.2.2图的邻接表存储表示ADCB68314592data0A1B2C3D4firstarcG.vertices11adjvexnextarcweight43∧9223∧305183∧62∧有向网的邻接表：7.2.2图的邻接表存储表示1．从无向图的邻接表可以得到如下结论

（1）第i个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。2．从有向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。7.2.2图的邻接表存储表示7.2.2图的邻接表存储表示邻接表的优点:空间效率高；容易寻找顶点的邻接点；邻接表的缺点:判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便讨论：邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)7.2.3有向图的十字链表存储表示constMAX_VERTEX_NUM=20;typedefstructArcNode{

inttailvex,headvex;//弧尾、弧头在表头数组中位置

structArcNode*hlink；//指向弧头相同的下一条弧

structArcNode*tlink;//指向弧尾相同的下一条弧}ArcNode;//弧结点typedefstructVexNode{

intdata;//存与顶点有关信息

structArcNode*firstin;//以该顶点为弧头的第一个结点

structArcNode*firstout;//以该顶点为弧尾的第一个结点}VexNode;//顶点结点typedefstruct{VexNodexlist[MAX_VERTEX_NUM20];

intvexnum,arcnum;}OLGraph;tailvexheadvexhlinktlinkdatafirstinfirstout例bdacabcd123413123431434241^^^^^^^^7.2.3有向图的十字链表存储表示7.2.4无向图的邻接多重表存储表示constMAX_VERTEX_NUM=20;typedefenum{unvisited,visited}VisitIf;typedefstructEbox{

intmark;//标志域

intivex,jvex;//该边依附的两个顶点在表头数组中位置

structEBox*ilink,*jlink;//指向依附于ivex和jvex的下一条边}EBox;typedefstructVexBox{VexTypedata;//存与顶点有关的信息

EBox*firstedge;//指向第一条依附于该顶点的边}VexBox;typedefstruct{VexBoxadjmulist[];intvexnum,edgenum;}AMLGraph;markivexilinkjvexjlinkdatafirstedge例aecbd1234acdb5e121434323552^^^^^7.2.4无向图的邻接多重表存储表示分析:在图的链接存储(邻接表、逆邻接表、十字链表和邻接多重表)中，表头向量需要占用n个存储单元，所有边结点需要占用2e或e存储单元，所以最多需要（n+2e）个存储单元，稀疏图采用这种存储方式可节省存储空间。7.2.4无向图的邻接多重表存储表示7.3图的遍历图结构也有遍历操作，即从某个顶点出发，沿着某条路径对图中其余顶点进行访问，且使每一个顶点只被访问一次。为了避免同一顶点被重复访问，在遍历过程中，必须为已经访问过的顶点加上标识，以便再次途经这样的顶点时不再重复访问。为此，需附设一维数组visited[0..n-1]，令其每个分量对应图中一个顶点，各分量的初值均设为FALSE，一旦访问了某个顶点，便将visited中相应分量的值置为TRUE或被访问时的序号。通常，对图进行遍历可有两种搜索路径：深度优先搜索和广度优先搜索。7.3.1图的深度优先搜索遍历深度优先搜索遍历(DepthFirstSearch)类似于树的先根遍历，可以看成是先根遍历的推广。假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到，若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。7.3.1图的深度优先搜索遍历例如，从v3出发对下图进行深度优先搜索，首先访问顶点v3，然后从v3的邻接顶点v2出发进行深度优先搜索，先后访问v4、v9和v1，由于v3的第二个邻接顶点v1已经被访问过，则不再从v1出发进行搜索，而v3的下一个邻接点v6未被访问，则再从v6出发进行搜索。V1DFS访问序列：V3V2V4V9V1V6V5V2V4V3V6V5V8V7V9V8V77.3.1图的深度优先搜索遍历算法7.2FirstAdjVex(G,v)返回图G中顶点v的第一个邻接点NextAdjVex(G,v,w)返回图G中v相对于w的下一个邻接点boolvisited[MAX];voidDFSTraverse(GraphG,Status(*visit)(intv)){VisitFunc=visit;//VisitFunc为全局变量

for(v=0;v<G.vexnum;v++)visited[v]=false;

for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);}//DFSTraversevoidDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图Gvisited[v]=true;VisitFunc(v);//访问第v个顶点

for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))

if(!visited[w])

DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS}//DFS7.3.1图的深度优先搜索遍历在实际应用中，首先要为图选定存储结构，假设采用邻接矩阵表示图，则算法7.2具体化为算法7.4。voidDFS(MGraphG,inti){//从顶点i出发遍历

intj;VisitFunc(G.vexs[i].data);//输出访问顶点

visited[i]=true;//访问标记置1表示已经访问

for(j=0;j<G.vexnum;j++)

if((G.arcs[i][j].adj==1)&&(!visited[j]))

DFS(G,j);}7.3.1图的深度优先搜索遍历在实际应用中，首先要为图选定存储结构，假设采用邻接表表示图，则算法7.2具体化为算法7.3。voidDFS(ALGraphG,intv){//从第v个顶点出发递归地深度优先遍历图Gvisited[v]=true;VisitFunc(G.vertices[v].data);

for(p=G.vertices[v].firstarc;p;p=p->nextarc;){w=p->adjvex;

if(!visited[w])

DFS(G,w);//对v未访问过的邻接顶点w递归调用DFS}//for}//DFSV1V7V4V3V5V6V2V8data8∧V87V76V65V54V43V32V21V101∧32∧7∧6∧54firstarc24∧5∧725∧6G.verticesDFS访问序列：V1V2V3V6V5V8V7V4出发点7.3.1图的深度优先搜索遍历V8V3V1V7V4V9V5V6V2出发点DFS访问序列：V1V9V7V2V5V6V4data87V76V65V54V43V92V21V108∧311∧5∧4∧601∧2firstarc054∧6∧81V8V3∧7∧0V3V87.3.1图的深度优先搜索遍历7.3.1图的深度优先搜索遍历查找的顺序为：1、2、4、8、5、6、3、71211241248124851248612483612480000000012345678111111116124837124386124861248124121124583676563712487.3.1图的深度优先搜索遍历深度优先搜索遍历的非递归算法（邻接矩阵）voidDFS(MGraphG,intv){LinkStackS;intw; InitStack_L(S);Push_L(S,v);//布置初始任务

visited[v]=true;(*VisitFunc)(G.Vexs[v]);

while(!StackEmpty(S)){GetTop_L(S,v);

for(w=0;w<G.vexnum;w++){

if(G.arcs[v][w].adj&&visited[w]==false){visited[w]=true;(*VisitFunc)(G.Vexs[v]);Push_L(S,w);break;}//if}//for

if(w==G.vexnum)Pop_L(S,v);}//while}//DFS7.3.1图的深度优先搜索遍历深度优先搜索遍历的非递归算法（邻接矩阵）voidDFS(MGraphG,intv){LinkStackS;intw;InitStack_L(S);Push_L(S,v);visited[v]=true;//布置初始任务

while(!StackEmpty(S)){//每次处理一项任务

Pop_L(S,v);(*VisitFunc)(G.Vexs[v]);

for(w=G.vexnum-1;w>=0;w--)

if(G.arcs[v][w].adj&&visited[w]==false){visited[w]=true;Push_L(S,w);}}//while}//DFS7.3.1图的深度优先搜索遍历深度优先搜索遍历的非递归算法（邻接表）voidDFS(ALGraphG,intv){LinkStackS;InitStack_L(S);intw;Push_L(S,v);visited[v]=true;//布置初始任务

while(!StackEmpty(S)){//每次处理一项任务

Pop_L(S,v);(*VisitFunc)(G.Vexs[v]);

for(p=G.vertices[v].firstarc;p;p=p->nextarc){w=p->adjvex;if(visited[w]==false){visited[w]=true;Push_L(S,w);}}//for}//while}//DFSV1V7V4V3V5V6V2出发点DFS访问序列：V1V2V5V6V7V3V47.3.1图的深度优先搜索遍历7.3.2图的广度优先搜索遍历

广度优先搜索(BreadthFirstSearch)的基本思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问”，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。7.3.2图的广度优先搜索遍历一层三层访问序列为：v3->v2->v1->v6->v4->v5->v9->v8->v7

321645987V1V2V4V3V6V5V8V7V9二层7.3.2图的广度优先搜索遍历可见，图的广度优先搜索过程类似于树的层次遍历。和深度优先搜索类似，在遍历的过程中也需要借助于访问标志数组visited。并且为了实现按照顶点被访问的先后次序查询它们的邻接点，需附设一个队列依访问次序存储已被访问的顶点。对以邻接矩阵表示方法存储的图进行广度优先遍历的算法如7.5所示。7.3.2图的广度优先搜索遍历voidBFSTraverse(MGraphG,void(*visit)()){boolvisited[G.vexnum];//附设访问标志数组

SqQueueQ;InitQueve(Q,G.vexnum);//附设循环队列Q

for(v=0;v<G.vexnum;++v)visited[v]=false;

for(v=0;v<G.vexnum;++v)

if(!visited[v]){visited[v]=true;(*visit)(G.vex[v]);//访问第v个顶点

EnQueue_Sq(Q,v);//v入队列

while(!QueueEmpty_Sq(Q)){DeQueue_Sq(Q,u);//队头元素出队并置为u

for(w=0;w<G.vexnum;w++)

if(G.arcs[u,w].adj&&!visited[w]){visited[w]=true;(*visit)(G.vex[w]);//访问顶点w

EnQueue_Sq(Q,w);//当前访问的顶点w入队列Q}//if}//while}//if}//BFSTraverse算法图的广度优先搜索遍历voidBFS(ALGraphG)//邻接表的广度优先搜索{boolvisited[G.vexnum];//附设访问标志数组

SqQueueQ;InitQueve(Q,G.vexnum);//附设循环队列Q

for(v=0;v<G.vexnum;v++)visited[v]=false;

for(v=0;v<G.vexnum;v++)

if(!visited[v]){visited[v]=true;VisitFunc(G.vertices[v]);EnQueue_Sq(Q,v);//v入队列

while(!QueueEmpty_Sq(Q)){DeQueue_Sq(Q,u);//队头元素出队并置为u

for(p=G.vertices[u].firstarc;p;p=p->nextarc){w=p->adjvex;

if(!visited[w]){visited[w]=true;VisitFunc(w);//访问图中第w个顶点

EnQueue_Sq(Q,w);//当前访问的顶点w入队列Q}//if

}//for}//while}//if}//BFSV1V7V4V3V5V6V2V8访问序列：V1V2V4V5V6V7V8出发点V3data8∧V87V76V65V54V43V32V21V101∧32∧7∧6∧54firstarc24∧5∧725∧67.3.2图的广度优先搜索遍历7.3.2图的广度优先搜索遍历从以上几个算法中可以看出，遍历图的过程实质上是通过边或弧找邻接点的过程，其消耗时间取决于所采用的存储结构。因此若采用同样的存储结构，广度优先遍历的时间复杂度和深度优先搜索相同。由于算法7.5中的存储结构为邻接矩阵，因此算法7.5的时间复杂度为O(n2)。图遍历是图的基本操作，也是一些图的应用问题求解算法的基础，以此为框架可以派生出许多应用算法。7.4图的连通性问题7.4.1

无向图的连通分量和生成树

7.4.2

有向图的强连通分量

7.4.3

连通网的最小生成树7.4.1无向图的连通分量和生成树

对于连通图从任一顶点出发进行深度（广度）优先遍历，即可访问到图的所有顶点；对于非连通图需要从多个顶点出发进行遍历。(a)非连通图(b)非连通图的两个极大连通分量ABCDEFACDBEF具有n个顶点的连通图至少有n-1条边7.4.1无向图的连通分量和生成树

设连通图G边的集合为E(G)，将E(G)分为两个集合T(G)和B(G)，T(G)为遍历图过程中经历的边的集合，B(G)为剩余的边。T(G)和G中所有顶点一起构成连通图G的极大连通子图，是连通图的生成树。如果遍历采用深度优先搜索，则得到的深度优先生成树；如果遍历采用广度优先搜索，则得到的广度优先生成树。而非连通图只有生成树林。(a)连通图12345678（b）深度优先生成树12485673(c)广度优先生成树765482317.4.2有向图的强连通分量

在有向图G中，如果对于每一对vi,vj∈V，vi,≠vj

，从vi到vj和从vj到vi都存在路径，则G是强连通图。有向图中的最大连通子图称作有向图的强连通分量。(a)非强连通图(b)非强连通图三个强连通分量ACBFDGECBDEAFG具有n个顶点的强连通图至少有n条弧7.4.3连通网的最小生成树

在一个含有n个顶点的连通图中，必能从中选出n-1条边构成一个极小连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边，称这棵树为连通图的生成树。例如，对下图(a)进行深度优先搜索遍历过程中经过的边和全部顶点构成的极小连通子图(b)即为(a)的一棵生成树。124987563124987563(a)(b)7.4.3连通网的最小生成树

在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。例如，对于如右图所示的连通网可以有多棵权值总和不相同的生成树。abcdefg1216431489106527abcdefg1639627abcdefg1243827abcdefg1216414810(a)权值总和为43(b)权值总和为36(c)权值总和为64权值序列：23456789101214167.4.3连通网的最小生成树构造连通网的最小生成树的算法主要有两种。1.克鲁斯卡尔(Kruskal)算法基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。abcdefg1216431489106527abcdefg1243827(c,e)产生回路(c,f)产生回路(f,g)产生回路(b,c)产生回路已选出n-1条边7.4.3连通网的最小生成树2.普里姆(Prim)算法假设G=(V,E)为一网，其中V为网中所有顶点的集合，E为网中所有带权边的集合。设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。令U的初值为U={u0}(假设从顶点u0出发构造最小生成树)，令T的初值为空，T={}。普里姆算法的思想是：从所有u∈U，v∈V-U的边中选取权值最小的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。7.4.3连通网的最小生成树例如，利用Prim算法对下图从顶点a开始构造最小生成树。abcdefg1216431489106527abcdefgU:{a}T:{}(a,b):12(a,f):16(a,g):1412U:{a,b}T:{(a,b)}(a,f):16(a,g):14(b,c):10(b,f):77U:{a,b,f}T:{(a,b),(b,f)}(a,g):14(b,c):10(f,c):6(f,e):2(f,g):92U:{a,b,e,f}T:{(a,b),(b,f),(f,e)}(a,g):14(b,c):10(e,c):5(e,d):4(e,g):8(f,c):6(f,g):94U:{a,b,d,e,f}T:{(a,b),(b,f),(f,e),(e,d)}(a,g):14(e,g):8(f,g):9(b,c):10(d,c):3(e,c):5(f,c):63U:{a,b,c,d,e,f}T:{(a,b),(b,f),(f,e),(e,d),(d,c)}(a,g):14(e,g):8(f,g):98U:{a,b,c,d,e,f,g}T:{(a,b),(b,f),(f,e),(e,d),(d,c),(e,g)}此时，所有顶点都已加入集合U，即U＝V，最小生成树构造完毕。7.4.3连通网的最小生成树比较以上两种算法可见：Kurskal算法主要对边进行操作，又称为“加边法”，其时间复杂度为O(e)。这种方法比较适用于稀疏图。Prim算法主要对顶点进行操作，又称为“加点法”，其时间复杂度为O(n2)。比较适用于稠密图。7.5有向无环图及其应用一个无环的有向图称为有向无环图（directedacyclinegraph），简称DAG。abced有向无环图是描述一项系统或工程的进行过程的有效工具，常用来判断工程能否顺利进行及估算完成时间。7.5.1拓扑排序有向无环图在工程计划和管理方面有着广泛的应用。一项工程往往可以分解为一些具有相对独立性的子工程，称这些子工程为活动。子工程之间在进行的时间上有着一定的相互制约关系。可以用有向图表示子工程及其相互制约关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为活动在顶点上的网络，简称活动顶点网络(ActivityOnVertexNetwork)，或AOV网。7.5.1拓扑排序什么是拓扑排序？若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。设R是集合X上的偏序，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。v2v1v4v3v2v1v4v37.5.1拓扑排序例如，在课程计划中，每门课程的学习就是一项活动，一门课程可能以其他某几门课程为先修基础，而它本身又可能是另一些课程的先修基础，各课程之间的先修关系可用活动顶点网络表示。课程号课程名先修课C1C语言程序设计无C2计算机导论无C3数据结构C1，C13C4计算机系统结构C2C5编译原理C3C6操作系统C3，

C4C7计算机网络C5C8数据库C5，

C6C9高等数学无C10数值分析C1，C9C11C++语言C1C12软件工程C7，C8C13离散数学C9C2C1C9C3C11C4C6C12C8C7C5C13C107.5.1拓扑排序在活动网络中不允许出现回路，因为回路意味着某项活动的开始将以自己工作的完成为先决条件，这种情况称为死锁现象。检测有向图中是否存在回路的方法之一是求有向图中顶点的一个排列，这个排列满足：若在有向图中从u到v有一条弧，则在此序列中u一定排在v之前，称有向图的这个操作为拓扑排序，所得顶点序列为拓扑有序序列。7.5.1拓扑排序例如，下面两个序列就是左图的拓扑有序序列：C1,C9,C10,C13,C3,C11,C2,C4,C5,C6,C7,C8,C12

C2,C4,C1,C9,C13,C3,C6,C5,C8,C7,C10,C11,C12通常，顶点的拓扑有序序列是不唯一的。但如果AOV网中存在回路，则不可能得到拓扑有序序列。C2C1C9C3C11C4C6C12C8C7C5C13C107.5.1拓扑排序

如何进行拓扑排序？

从其定义可知，在拓扑有序序列中的第一个顶点必定是在AOV网中没有前驱的结点，则首先在AOV网中选取一个没有前驱的顶点，输出它并从AOV网中删去所有以它为尾的弧，重复此操作直至所有顶点都被输出为止。如果在此过程中找不到没有前驱的顶点，则说明尚未输出的子图中必有回路。12678543输出22输出55输出77输出11输出33输出44输出66输出887.5.1拓扑排序在计算机中实拓扑排序算法时，需要以“入度为零”作为“没有前驱”的量度，而删除结点及以它为尾的弧的操作不必真正对图的存储结构进行，可用弧头顶点的入度减1来实现，算法如下所示：建有向图的邻接表并统计各顶点的入度;取入度为0的顶点v;

while(v<>0){//尚有入度为零的顶点存在

cout<<v;++m;//输出入度为零的顶点，并记数

w=FirstAdj(v);

//w为v的邻接点

while(w<>0){//尚有v的邻接点存在

inDegree[w]--;//w的入度减一

w=NextAdj(v,w);//取V的下一个邻接点

}

取下一个入度为0的顶点v;}

if(m<n)cout<<(“图中有回路”)7.5.1拓扑排序intInDegree[MAX_VERTEX_NUM];booltag[MAX_VERTEX_NUM];voidCountInDegree(MGraphG,int*d){for(i=0;i<G.vexnum;i++)InDegree[i]=0;

for(i=0;i<G.vexnum;i++)

for(j=0;j<G.vexnum;j++)

if(G.arcs[i][j].adj)InDegree[j]++;}intFirstDegree0(MGraphG,int*indgree){for(inti=0;i<G.vexnum;i++)

if(!tag[i]&&InDegree[i]==0)

returni;

return-1;}若为邻接矩阵7.5.1拓扑排序boolTopSort(MGraphG){CountInDegree(G,InDegree);//统计各顶点的入度;

for(i=0;i<G.vexnum;i++)tag[i]=false;v=FirstDegree0(G,InDegree);//取入度为0的顶点v;

while(v!=-1){//尚有入度为零的顶点存在

//输出入度为零的顶点，并记数cout<<setw(3)<<G.Vexs[v];tag[v]=true;m++;

if(m==G.vexnum)returntrue;

for(w=0;w<G.vexnum;w++)

if(G.arcs[v][w].adj)//W为V的邻接点

InDegree[w]--;//W的入度减一

v=FirstDegree0(G,InDegree);//取下一个入度为0的点}

if(m<G.vexnum)returnfalse;}若为邻接矩阵7.5.1拓扑排序voidTopSort(MGraphG){//统计各顶点的入度;

for(i=0;i<G.vexnum;i++){InDegree[i]=0;tag[i]=false;}

for(i=0;i<G.vexnum;i++)

for(j=0;j<G.vexnum;j++)

if(G.arcs[i][j].adj)InDegree[j]++;

for(v=0;v<G.vexnum;v++)//取入度为0的顶点v;

if(InDegree[v]==0)break;

if(v>=G.vexnum)v=-1;while(v!=-1){//尚有入度为零的顶点存在cout<<setw(3)<<G.Vexs[v];tag[v]=true;m++;

if(m==G.vexnum)returntrue;

for(w=0;w<G.vexnum;w++)

if(G.arcs[v][w].adj)InDegree[w]--;//邻接点入度减一

for(v=0;v<G.vexnum;v++)//取下一个入度为0的点

if(InDegree[v]==0&&tag[v]==false)break;

if(v>=G.vexnum)v=-1;}

if(m<G.vexnum)returnfalse;}7.5.2关键路径对于一项工程而言，还可以用弧表示活动，用顶点表示事件，所谓事件是一个关于某(几)项活动开始或完成的断言：指向它的弧所表示活动已经完成，从它出发的弧所表示的活动开始进行。每条弧可以带有权值，以表示活动进行需要的时间等。称这种网络为活动在边上的网络，简称为活动边网络，或AOE网。源点汇点afdbcehgka1=6a7=8a5=1a3=5a6=2a11=4a9=4a2=4a4=1a8=7a10=2如左图所示的AOE网，ai表示第i(i=1,2…,11)项活动，弧上的数字表示完成子工程所需要的天数。a表示整个工程的开始，其入度为零，通常称其为源点；k表示整个工程的结束，其出度为零，通常称其为汇点。一个工程的AOE网应该是一个单源点和单汇点的有向无环图。7.5.2关键路径在AOE网络中，一条路径上各弧权值之和称为该路径的带权路径长度。由于AOE网络中某些活动可以并行进行，则完成整个工程的最短时间即为从源点到汇点最长的带权路径长度的值，称这样的路径为关键路径，关键路径上的弧称为关键活动。afdbcehgka1=6a7=8a5=1a3=5a6=2a11=4a9=4a2=4a4=1a8=7a10=2例如，左图中从源点a到汇点k共有5条路径，带权路径长度如下：

a-b-e-g-k:17 a-b-e-h-k:18 a-c-e-g-k:15 a-c-e-h-k:16 a-d-f-h-k:15{a,b,e,h,k}为关键路径a1,a4,a8,a11为关键活动7.5.2关键路径如何求关键路径？首先定义四个描述量。假设顶点V1为源点，Vn为汇点，事件V1的发生时刻作为事件原点(0时刻)。ve(j)：事件Vj可能发生的最早时刻，它是从V1到Vj的最长带权路径长度

0j=1

ve(j)=max{ve(i)+w(ViàVj)}j=2,3,…,nViàVj是弧其中，w(ViàVj)表示该弧的权值。对于一个特定的顶点Vj(2≤j≤n)，上式表示考察Vj的所有前驱结点Vi1，Vi2，…，Vip，在ve(i1)+w(Vi1àVj),…,ve(ip)+w(VipàVj)中选最大值。计算ve时，应该按顶点的拓扑有序次序从源点开始向下推算至汇点。7.5.2关键路径

vl(i)：在保证不延误整个工期，即保证Vn在ve(n)时刻发生的前提下，事件Vi发生所允许的最晚时刻。它等于ve(n)减去Vi到Vn的最长带权路径长度。

ve(n)i=nvl(i)=min{vl(j)-w(ViàVj)}i=n-1,…,2,1

ViàVj是弧对于一个特定的顶点Vi(1≤i≤n-1)，上式考察Vi的所有后继结点Vj1，Vj2，…

，Vjq，在vl(j1)-w(ViàVj1),…,vl(jq)-w(ViàVjq)中选最小值。计算vl时，顺序和ve相反，从汇点开始向回推算至源点。7.5.2关键路径ee(k)：活动ak(令ak是ViàVj)可能开始的最早时刻。显然，它应该是事件Vi可能发生的最早时刻ve(i)，即

ee(k)=ve(i)(k=1,2,…,mm为弧的数目)el(k)：活动ak(令ak是ViàVj)在保证