数据结构简明教程（第3版）课件 第7章图(上)

第7章图7.1图的基本概念7.2图的存储结构7.3图的遍历7.4生成树和最小生成树7.5最短路径7.6拓扑排序7.7AOE网与关键路径第7章图1/887.1图的基本概念7.1.1图的定义无论多么复杂的图都是由顶点和边构成的。采用形式化的定义，图G（Graph）由两个集合V（Vertex）和E（Edge）组成，记为G=(V,E)，其中V是顶点的有限集合，记为V(G)，E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。7.1图的基本概念2/88对于含有n个顶点的图，通常用字母或自然数来唯一标识图中顶点（顶点的编号）。本书约定用数字i（0≤i≤n-1）表示第i个顶点的编号。7.1图的基本概念3/88

【例7.1】一个图G1=(V1，E1)，其中：

V1={0，1，2，3，4}E1={(0,1)，(1,2)，(2,3)，(3,4)，(2,4)，(0,3)}另一个图G2=(V2，E2)，其中：

V2={0，1，2，3，4}

E2={<0,1>，<1,2>，<1,3>，<2,4>，<0,4>，<4,3>，<3,2>}画出这两个图的逻辑结构。7.1图的基本概念4/88

它们的逻辑结构如图7.1所示，从中看到图G1是无向图，图G2是有向图。V1={0，1，2，3，4}E1={(0,1)，(1,2)，(2,3)，(3,4)，(2,4)，(0,3)}0124301243V2={0，1，2，3，4}E2={<0,1>，<1,2>，<1,3>，<2,4>，<0,4>，<4,3>，<3,2>}7.1图的基本概念5/887.1.2图的基本术语（1）无向图和有向图

对于一个图G，若边集E(G)为无向边的集合，则称该图为无向图。例如，图7.1(a)中的图就是一个无向图。对于一个图G，若边集E(G)为有向边的集合，则称该图为有向图。例如，图7.1(b)中的图就是一个有向图。01243012437.1图的基本概念6/88（2）端点和相邻点在一个无向图中，若存在一条边(i,j)，则称顶点i、j为该边的两个端点，并称它们互为相邻点（或者邻接点）。

例如，图7.1(a)中，顶点0和顶点1是两个端点，它们互为相邻点。01243注意：端点和相邻点是相对一条边的7.1图的基本概念7/88在一个有向图中，若存在一条边<i,j>，则称此边是顶点i的一条出边，同时也是顶点j的一条入边，称顶点i和j分别为此边的起始端点（简称为起点）和终止端点（简称终点）。

例如，图7.1(b)中，对于边<0,1>，该边是顶点0的出边，顶点1的入边，同时，顶点0称为起点，顶点1称为终点。012437.1图的基本概念8/88（3）度、入度和出度顶点v的度记为D(v)。对于无向图，每个顶点的度定义为以该顶点为一个端点的边数。

对于有向图，顶点v的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。

例如，图7.1(a)中，D(0)=2。012437.1图的基本概念9/88在图7.1(b)中，顶点4的入度为2，出度为1，所以D(4)=3。012437.1图的基本概念10/88若一个图（无论有向图或无向图）中有n个顶点和e条边，每个顶点的度为di（0≤i≤n-1），则有：也就是说，一个图中所有顶点的度之和等于边数的两倍。因为图中每条边分别作为两个相邻点的度各计一次。e＝7.1图的基本概念11/88

【例7.2】一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则该图至少有（）个顶点。

A.10

B.11 C.12 D.13设该图有n个顶点，图中度为i的顶点数为ni（0≤i≤4），n4=3，n3=4。要使顶点数最少，该图应是连通的，即n0=0，n=n4+n3+n2+n1+n0=7+n2+n1，即n2+n1=n-7。度之和=4×3+3×4+2×n2+n1=24+2n2+n1≤24+2(n2+n1)=24+2×(n-7)=10+2n。而度之和=2e=32，所以有10+2n≥32，即n≥11。7.1图的基本概念12/88（4）子图设有两个图G=(V,E)和G'=(V',E')，若V'是V的子集，即V'

V，且E'是E的子集，即E'

E，则称G'是G的子图。7.1图的基本概念13/88

注意：对于一个图G=(V,E)，V'是V的子集，即V'

V，E'是E的子集，即E'

E。而(V',E')可能不是一个图，所以由V的子集和E的子集并非一定构成G的子图。01243而V'={0,2}，E'={(0,3)，(2,3)}并不是其子图，因为(V',E')本身不是一个图。027.1图的基本概念14/88（5）完全无向图和完全有向图

对于无向图，若具有n(n-1)/2条边，则称之为完全无向图。例如，图7.2(a)是完全无向图G3，这里n=4，边数为6。12307.1图的基本概念15/88对于有向图，若具有n(n-1)条边，则称之为完全有向图。

例如，图7.2(b)是完全有向图G4，这里n=4，边数为12。12307.1图的基本概念16/88（6）稀疏图和稠密图边数较少（边数e<<nlog2n，其中n为顶点数）的图称为稀疏图。边总较多的图称为稠密图。7.1图的基本概念17/88（7）路径和路径长度在一个图G中，从顶点i到顶点j的一条路径是一个顶点序列i=i0、i1、…、im=j，若是无向图，则(ik-1,ik)∈E(G)，（1≤k≤m），若该图是有向图，则<ik-1,ik>∈E(G)，（1≤k≤m），其中顶点i称为该路径的开始点，顶点j称为该路径的结束点。路径长度是指一条路径上经过的边的数目。7.1图的基本概念18/88（8）简单路径若一条路径的顶点序列中顶点不重复出现，称该路径为简单路径。

例如，图7.1(a)中，路径0→1→2→4是一条简单路径，其长度为3。012437.1图的基本概念19/88图7.1(b)中，路径0→1→3→2是一条简单路径，其长度也为3。012437.1图的基本概念20/88（9）回路（环）若一条路径上的开始点和结束点为同一个顶点，则称该路径为回路（环）。除开始点与结束点相同外，其余顶点不重复出现的回路称为简单回路（简单环）。

例如，图7.1(a)中，路径0→1→2→4→3→0是一条回路（环），也是一条简单回路（简单环）。012437.1图的基本概念21/88（10）连通、连通图和连通分量在无向图G中，若从顶点i到顶点j有路径，则称顶点i和j是连通的。若图G中任意两个顶点都是连通的，则称G为连通图，否则为非连通图。无向图G中极大连通子图称为G的连通分量。

例如，图7.1(a)的连通分量就是自身，因为该图是连通图。012437.1图的基本概念22/88（11）强连通图和强连通分量在有向图G中，若任意两个顶点i和j都是连通的，即从顶点i到j和从顶点j到i都存在路径，则称该图是强连通图。有向图G中极大强连通子图称为G的强连通分量。

7.1图的基本概念23/88对于图7.1(b)的有向图，顶点0的入度为0，也就是说其余顶点都没有到达顶点0的路径，所以单个顶点0是一个强连通分量；顶点1只有一条从顶点0到它的入边，除顶点0外其余顶点没有到达顶点1的路径，所以单个顶点1也是一个强连通分量；点2、3、4构成一个有向环，这些顶点之间都有路径，该图的强连通分量。0124301243强连通分量7.1图的基本概念24/88（12）权和网在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为带权图，也称为网。

图7.4中的图G5就是一个带权图。本书中规定所有边的权均为非负数。0132414623757.1图的基本概念25/88

【例7.3】如果图G是一个具有n个顶点的连通图，那么G最多有多少条边？G最少有多少条边？

如果图G'是一个具有n个顶点的强连通图，那么G'最多有多少条边？G'最少有多少条边？图G为完全无向图时边最多，即图G最多有n(n-1)/2条边；图G为一棵树时边最少，即G最少有n-1条边。0123n=47.1图的基本概念图G为连通图：26/88图G为完全有向图时边最多，即图G最多有n(n-1)条边；图G为一棵树时边最少，即G最少有n条边。0123n=47.1图的基本概念图G为强连通图:27/887.1.3图的基本操作图的基本运算如下：建立图CreateGraph(G)：建立图G的某种存储结构。销毁图DestroyGraph(G)：释放图G占用的内存空间。输出图DispGraph(G)：显示图G的结构。求顶点的度Degree(G,v)：求图G中顶点v的度。7.1图的基本概念28/887.2图的存储结构7.2.1邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，顶点编号依次为0、1、…、n-1，则G的邻接矩阵是具有如下定义的n阶方阵A。7.2图的存储结构A[i][j]=对于无向图，(i,j)或(j,i)∈E(G)；对于有向图，<i,j>∈E(G)i=j其他情况100若G是不带权的图：29/88A[i][j]=对于无向图，(i,j)或(j,i)∈E(G)；对于有向图，<i,j>∈E(G)i=j其他情况wij0∞若G是带权图或网，则邻接矩阵可定义为（其中wij为边(i,j)或<i,j>的权）：7.2图的存储结构30/8801243A1=01234001010110100201011310101400110无向图时一定为对称矩阵顶点1的度为27.2图的存储结构31/88A2=01234001001100110200001300100400010有向图时不一定为对称矩阵顶点1的出度为201243顶点1的入度为17.2图的存储结构32/88A3=0123400126∞1∞0∞452∞∞0∞33∞∞∞0∞4∞∞∞70有向图时不一定为对称矩阵顶点1的出度为2顶点1的入度为10132414623757.2图的存储结构33/88图邻接矩阵的特点：对于n个顶点e条边的图采用邻接矩阵存储时占用存储空间为O(n2)，与边数e无关（不考虑压缩存储），特别适合存储稠密图；任何图的邻接矩阵表示是唯一的；图采用邻接矩阵存储时判断两个顶点i、j之间是否有边十分容易。7.2图的存储结构34/88图的邻接矩阵类型声明：#defineMAXVEX100

//图中最大顶点个数typedefcharVertexType[10];

//定义VertexType为字符串类型typedefstructvertex{intadjvex;

//顶点编号

VertexTypedata;

//顶点的信息}VType;

//顶点类型typedefstructgraph{intn,e;

//n为实际顶点数,e为实际边数

VType

vexs[MAXVEX];

//顶点集合

intedges[MAXVEX][MAXVEX];

//边的集合}

MatGraph;

//图的邻接矩阵类型7.2图的存储结构35/88在邻接矩阵上实现图的主要基本运算的算法如下。（1）建立图的邻接矩阵运算算法由邻接矩阵数组A、顶点数n和边数e建立图G的邻接矩阵存储结构。voidCreateGraph(MatGraph&g,intA[][MAXVEX],intn,inte){inti,j;

g.n=n;g.e=e;

for(i=0;i<n;i++)for(j=0;j<n;j++)

g.edges[i][j]=A[i][j];}7.2图的存储结构36/88（2）销毁图运算算法这里邻接矩阵是图的一种顺序存储结构，其内存空间是由系统自动分配的，在不再需要时由系统自动释放其空间。所以对应的函数不含任何语句。voidDestroyGraph(MatGraphg){}7.2图的存储结构37/88（3）输出图运算算法将图G的邻接矩阵存储结构输出到屏幕上。voidDispGraph(MatGraphg){inti,j;

for(i=0;i<g.n;i++)

{for(j=0;j<g.n;j++)

{if(g.edges[i][j]<INF)

printf("%4d",g.edges[i][j]);

else

printf("%4s","∞");}printf("\n");}}7.2图的存储结构38/88（4）求顶点度运算算法对于无向图和有向图，求顶点度有所不同。依据定义，求无向图G中顶点v的度的算法如下：intDegree1(MatGraphg,intv)

//求无向图中顶点的度{inti,d=0;

if(v<0||v>=g.n)return-1;

//顶点编号错误返回-1

for(i=0;i<g.n;i++){if(g.edges[v][i]>0&&g.edges[v][i]<INF)

d++;

//统计第v行既不为0也不为∞的边数即度

}returnd;}7.2图的存储结构39/88求有向图G中顶点v的度的算法如下：intDegree2(MatGraphg,intv)

//求有向图中顶点的度{inti,d1=0,d2=0,d;

if(v<0||v>=g.n)return-1; //顶点编号错误返回-1for(i=0;i<g.n;i++){if(g.edges[v][i]>0&&g.edges[v][i]<INF)

d1++;

//统计第v行既不为0也不为∞的边数即出度

}for(i=0;i<g.n;i++){if(g.edges[i][v]>0&&g.edges[i][v]<INF)

d2++;

//统计第v列既不为0也不为∞的边数即入度

}d=d1+d2;

returnd;}7.2图的存储结构40/887.2.2邻接表邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个带头结点的单链表，把该顶点的所有相邻点串起来。所有的头结点构成一个数组，称为头结点数组，用adjlist表示，第i个单链表adjlist[i]中的结点表示依附于顶点i的边，也就是说头结点数组元素的下标与顶点编号一致。

7.2图的存储结构41/88每个单链表中每个结点由3个域组成：为了统一，对于不带权图，weight域均置为1；对于带权图，weight置为相应边的权值。顶点域adjvex（用以指示该相邻点在头结点数组中的下标）权值域weight（存放对应边的权值）指针域nextarc（用以指向依附于顶点i的下一条边所对应的结点）7.2图的存储结构adjvexweightnextarc**42/8801243v01131∧v10121∧v2113141∧v3012141∧v42131∧datafirstarcadjvexweightnextarc头结点边结点01234头结点数组adjlist顶点1的度为27.2图的存储结构43/8801243v01141∧v12131∧v241∧v321∧v431∧012347.2图的存储结构44/88013241462375v01136∧022v134145∧v243∧2v3∧3v437∧47.2图的存储结构45/88图邻接表的特点：对于n个顶点e条边的图采用邻接表存储时占用存储空间为O(n+e)，与边数e有关，特别适合存储稀疏图；图的邻接表表示不一定是唯一的，这是因为邻接表的每个单链表中，各结点的顺序是任意的；图采用邻接表存储时查找一个顶点的所有相邻顶点十分容易。7.2图的存储结构46/88一个图的邻接表存储结构的类型声明如下：typedefcharVertexType[10]; //VertexType为字符串类型typedefstructedgenode{intadjvex;

//相邻点序号

intweight;

//边的权值

structedgenode*nextarc;

//下一条边的顶点}ArcNode; //每个顶点建立的单链表中边结点的类型typedefstructvexnode{VertexTypedata;

//存放一个顶点的信息

ArcNode*firstarc;

//指向第一条边结点}VHeadNode; //单链表的头结点类型typedefstruct{intn,e;

//n为实际顶点数,e为实际边数

VHeadNode

adjlist[MAXVEX];

//单链表头结点数组}AdjGraph;

//图的邻接表类型7.2图的存储结构47/88图编程要领：牢牢掌握数据的存储结构。基本算法设计思路。并用C/C++语句实现。7.2图的存储结构48/88在邻接表上实现图的主要基本运算的算法如下。（1）建立图的邻接表运算算法由邻接矩阵数组A、顶点数n和边数e建立图G的邻接表存储结构。先创建邻接表头结点数组，并置所有头结点的firstarc为NULL。遍历邻接矩阵数组A，当A[i][j]≠0且A[i][j]≠∞时，说明有一条从顶点i到顶点j的边，建立一个边结点p，置其adjvex域为j，其weight域为A[i][j]（aij），将p结点插入到顶点i的单链表头部。7.2图的存储结构基本思路49/88头结点边结点注意：图中每个顶点有一个头结点，每条边有一个边结点（无向图一条边对应2个边结点）。vi****∧ijaijp…顶点i到j有边：实现语句：p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;引用方式：G->adjlist[i].firstarc7.2图的存储结构50/88voidCreateGraph(AdjGraph*&G,intA[][MAXVEX],intn,inte){inti,j;

ArcNode*p;

G=(AdjGraph*)malloc(sizeof(AdjGraph));

G->n=n;G->e=e;

for(i=0;i<G->n;i++) //邻接表中所有头结点的指针域置空G->adjlist[i].firstarc=NULL;

for(i=0;i<G->n;i++) //检查A中每个元素{for(j=G->n-1;j>=0;j--)

{if(A[i][j]>0&&A[i][j]<INF)

//存在一条边

{p=(ArcNode*)malloc(sizeof(ArcNode));//创建结点pp->adjvex=j;

p->weight=A[i][j];

p->nextarc=G->adjlist[i].firstarc;//头插法插入p

G->adjlist[i].firstarc=p;

}}}}7.2图的存储结构51/88（2）销毁图运算算法邻接表的头结点和边结点都是采用malloc函数分配的，在不再需要时应用free函数释放所有分配的空间。7.2图的存储结构

基本思路：通过adjlist数组遍历每个单链表，释放所有的边结点，最后释放adjlist数组的空间。52/88voidDestroyGraph(AdjGraph*&G) //销毁图{inti;

ArcNode*pre,*p;

for(i=0;i<G->n;i++) //遍历所有的头结点

{pre=G->adjlist[i].firstarc;

if(pre!=NULL)

{p=pre->nextarc;

while(p!=NULL)//释放adjlist[i]的所有边结点

{free(pre);

pre=p;p=p->nextarc;

}

free(pre);

}

}

free(G);

//释放G所指的头结点数组的内存空间}7.2图的存储结构53/88（3）输出图运算算法输出图G的邻接表存储结构。voidDispGraph(AdjGraph*G)

//输出图的邻接表{ArcNode*p;

inti;

for(i=0;i<G->n;i++) //遍历所有的头结点{ printf("[%2d]",i); p=G->adjlist[i].firstarc; //p指向第一个相邻点

if(p!=NULL)

printf("→"); while(p!=NULL)

{printf("%d(%d)",p->adjvex,p->weight);

p=p->nextarc;

//p移向下一个相邻点

} printf("\n");

}}7.2图的存储结构54/88（4）求顶点度运算算法对于无向图和有向图，求顶点度有所不同。依据定义，求无向图G中顶点v的度的算法如下：intDegree1(AdjGraph*G,intv)//求无向图G中顶点v的度{intd=0;

ArcNode*p;

if(v<0||v>=G->n)return-1; //顶点编号错误返回-1

p=G->adjlist[v].firstarc;

while(p!=NULL) //统计v顶点的单链表中边结点个数即度

{d++;

p=p->nextarc;

}

returnd;}7.2图的存储结构55/88求有向图G中顶点v的度的算法如下：intDegree2(AdjGraph*G,intv)//求有向图G中顶点v的度{inti,d1=0,d2=0,d;ArcNode*p;

if(v<0||v>=G->n)

return-1;

//顶点编号错误返回-1

p=G->adjlist[v].firstarc;

while(p!=NULL)

//统计v的单链表中边结点个数即出度

{d1++;

p=p->nextarc;

}

for(i=0;i<G->n;i++)//统计边结点中adjvex为v的个数即入度

{p=G->adjlist[i].firstarc;

while(p!=NULL)

{if(p->adjvex==v)d2++;

p=p->nextarc;

}

}

d=d1+d2;

returnd;}7.2图的存储结构56/88【例7.7】对于具有n个顶点的有向图G，设计以下两个算法：（1）设计一个将邻接矩阵g转换为邻接表G的算法；（2）设计一个将邻接表G转换为邻接矩阵g的算法。先分配G的内存空间并将所有头结点的firstarc域置为NULL。遍历邻接矩阵g，查找元素值不为0且不为∞的元素g.edges[i][j]，找到这样的元素后创建一个边结点p，将其插入到G->adjlist[i]单链表的首部。7.2图的存储结构（1）设计一个将邻接矩阵g转换为邻接表G的算法。57/88voidMatToAdj(MatGraphg,AdjGraph*&G)

//将邻接矩阵g转换成邻接表G{inti,j;ArcNode*p;

G=(AdjGraph*)malloc(sizeof(AdjGraph));

for(i=0;i<g.n;i++) //邻接表中所有头结点的指针域置初值G->adjlist[i].firstarc=NULL;

for(i=0;i<g.n;i++) //检查邻接矩阵中每个元素

{

for(j=g.n-1;j>=0;j--){if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)//有一条边

{p=(ArcNode*)malloc(sizeof(ArcNode));//创建结点p

p->adjvex=j;

p->weight=g.edges[i][j];

p->nextarc=G->adjlist[i].firstarc;//头插法插入pG->adjlist[i].firstarc=p;}

}}

G->n=g.n;G->e=g.e;

//置顶点数和边数}7.2图的存储结构58/88先将邻接矩阵g中所有元素初始化：对角线元素置为0，其他元素置为∞。然后遍历邻接表的每个单链表，当访问到G->adjlist[i]单链表的结点p时，将邻接矩阵g的元素g.edges[i][p->adjvex]修改为p->weight。7.2图的存储结构（2）设计一个将邻接表G转换为邻接矩阵g的算法59/88voidAdjToMat(AdjGraph*G,MatGraph&g) //将邻接表G转换成邻接矩阵g{inti,j;

ArcNode*p;

for(i=0;i<G->n;i++){for(j=0;j<G->n;j++){if(i==j)g.edges[i][i]=0; //对角线置为0

elseg.edges[i][j]=INF;}}for(i=0;i<G->n;i++)

{p=G->adjlist[i].firstarc;

while(p!=NULL)

{g.edges[i][p->adjvex]=p->weight;

p=p->nextarc;

}

}

g.n=G->n;g.e=G->e;

//置顶点数和边数}7.2图的存储结构60/887.3图的遍历给定一个图G=(V,E)和其中的任一顶点v，从顶点v出发，访问图G中的所有顶点而且每个顶点仅被访问一次，这一过程称为图的遍历。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此设一个辅助数组visited[]，用以标记顶点是否被访问过，初始均为0（false）。一个顶点i被访问，则visited[i]=1（true）。7.3图的遍历61/887.3.1深度优先遍历算法深度优先遍历（DepthFirstSearch，简称DFS）：访问顶点v；选择一个与顶点v相邻且没被访问过的顶点w，从w出发深度优先遍历。直到图中与v相邻的所有顶点都被访问过为止。7.3图的遍历62/88例如，对于图7.8(a)的邻接表，从顶点0出发的深度优先遍历序列是0、1、2、3、4。v01131∧v10121∧v2113141∧v3012141∧v42131∧头结点边结点012347.3图的遍历63/88实现深度优先遍历的递归算法如下：visited[MAXVEX]={0}; //全局变量voidDFS(AdjGraph*G,intv){intw;ArcNode*p;

printf("%d",v); //访问v顶点

visited[v]=1;

p=G->adjlist[v].firstarc; //找v的第一个相邻点

while(p!=NULL) //找v的所有相邻点

{ w=p->adjvex; //顶点v的相邻点w if(visited[w]==0) //顶点w未访问过

DFS(G,w);

//从w出发深度优先遍历

p=p->nextarc; //找v的下一个相邻点

}}7.3图的遍历64/88DFS思路：vv1v2v3vm一步一步向前走，当没有可走的相邻顶点时便回退。…7.3图的遍历65/88企业面试题：无向图G=（VE），其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行深度优先排序，得到的顶点序列正确的是（）。

A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，babcdef用R表示回退一次A.a,a→b,b→e,e→d,不应该到cB.a,a→c,c→f,f→d,不应该到eC.a,a→e,e→b,R,e→d,不应该到cD.a,a→e,e→d,d→f,f→c,R,R,R,e→b√7.3图的遍历66/88访问顶点v；访问顶点v的所有未被访问过的相邻点，假设访问次序是vi1，vi2，…，vit。按vi1，vi2，…，vit的次序，访问每个顶点的所有未被访问过的相邻点，直到图中所有和初始点v有路径相通的顶点都被访问过为止。7.3.2广度优先遍历算法广度优先遍历（BreadthFirstSearch，简称BFS）：顺序一致，用队列实现7.3图的遍历67/88例如，对于图7.8(a)的邻接表，从顶点0出发的广度优先遍历序列是0、1、3、2、4。v01131∧v10121∧v2113141∧v3012141∧v42131∧头结点边结点012347.3图的遍历68/88实现广度优先搜索的算法如下：voidBFS(AdjGraph*G,intvi){inti,v,visited[MAXVEX];

ArcNode*p;intQu[MAXVEX],front=0,rear=0; //定义一个循环队列Qufor(i=0;i<G->n;i++)visited[i]=0; //visited数组置初值0printf("%d",vi); //访问初始顶点visited[vi]=1;rear=(rear=1)%MAXVEX;Qu[rear]=vi; //初始顶点进队while(front!=rear) //队不为空时循环{front=(front+1)%MAXVEX;

v=Qu[front]; //出队顶点v

p=G->adjlist[v].firstarc; //查找v的第一个相邻点

while(p!=NULL)

//查找v的所有相邻点

{if(visited[p->adjvex]==0) //未访问过则访问之

{printf("%d",p->adjvex); //访问该点并进队visited[p->adjvex]=1;rear=(rear+1)%MAXVEX;Qu[rear]=p->adjvex;

}p=p->nextarc;

//查找v的下一个相邻点

}

}}7.3图的遍历69/88BFS思路：vi一圈一圈向外走。7.3图的遍历70/887.3.3图遍历算法的应用

【例7.8】假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。先给visited[]数组置初值0。然后从0顶点开始遍历该图。在一次遍历之后，若所有顶点i的visited[i]均为1，则该图是连通的；否则不连通。7.3图的遍历采用某种遍历方法判断无向图G是否连通。这里用深度优先遍历方法。71/88intConnect(AdjGraph*G) //判断无向图G的连通性{inti,flag=1;

DFS(G,0);

//调用DFS算法,从顶点0开始深度优先遍历

for(i=0;i<G->n;i++){if(visited[i]==0)

{flag=0;

break;

}}

returnflag;}7.3图的遍历72/88

【例7.9】假设图G采用邻接表存储，设计一个算法判断顶点u到顶点v（u≠v）之间是否有简单路径。先置全局visited数组的所有元素值为0。从顶点u出发进行深度优先遍历，置visited[u]=1；找到顶点u的一个未访问过的相邻点u1，置visited[u1]=1；找到顶点u1的一个未访问过的相邻点u2，置visited[u2]=1；以此类推。当找到的某个未访问过的相邻点un=v时，说明顶点u到v有一条简单路径，返回1。当整个遍历中都没有找到顶点v，说明u到v没有路径，返回0。7.3图的遍历采用深度优先遍历思路设计求解算法HasaPath(G，u，v)。73/88intvisited[MAXVEX]; //全局数组intHasaPath(AdjGraph*G,intu,intv){ArcNode*p;intw;visited[u]=1;p=G->adjlist[u].firstarc;//p指向u的第一个相邻点while(p!=NULL){w=p->adjvex; //相邻点的编号为wif(w==v) //找到顶点v后返回1return1;if(visited[w]==0) //若顶点w没有访问过{if(HasaPath(G,w,v)) //从w出发进行深度优先遍历return1; //若从w出发找到顶点v返回1}p=p->nextarc; //p指向下一个相邻点}return0; //没有找到顶点v，返回0}7.3图的遍历74/88从递归算法设计的角度求解本问题intvisited[MAXVEX]; //全局数组intHasaPath1(AdjGraph*G,intu,intv){ArcNode*p;intw;

if(u==v)return1;

//找到顶点v后返回1visited[u]=1;p=G->adjlist[u].firstarc; //p指向u的第一个相邻点while(p!=NULL){w=p->adjvex; //相邻点的编号为wif(visited[w]==0) //若顶点w没有访问过{if(HasaPath1(G,w,v))//从w出发进行深度优先遍历return1; //若从w出发找到顶点v返回1}p=p->nextarc; //p指向下一个相邻点}return0; //没有找到顶点v，返回0}7.3图的遍历75/88

【例7.10】假设图G采用邻接表存储，设计一个算法求顶点u到顶点v（u≠v）之间的一条简单路径（假设两顶点之间存在一条或多条简单路径）。

7.3图的遍历76/88采用深度优先遍历思路设计求解算法FindaPath(G，u，v，path，d)，其中用path[0..d]存放图中从顶点u到v的一条简单路径，初始时数组path为空，d为-1。先置visited数组的所有元素值为0。从顶点u开始遍历，置visited[u]=1，…。7.3图的遍历当找到的某个未访问过的邻接点un=v时，说明找到了顶点u到v的一条简单路径，输出path中顶点序列并返回。f(G,u,v,…)f(G,u1,v,…)f(G,v,v,…)…找不到未访问的相邻顶点77/88voidFindaPath(AdjGraph*G,intu,intv,intpath[],intd){ArcNode*p;intw,i;

visited[u]=1;

d++;path[d]=u; //顶点u加入到路径中

if(u==v) //找到一条路径

{for(i=0;i<=d;i++) //输出找到一条路径并返回

printf("%d",path[i]);

printf("\n");

return;

}

p=G->adjlist[u].firstarc; //p指向u的第一个相邻点

while(p!=NULL)

{w=p->adjvex; //相邻点的编号为w

if(visited[w]==0)

FindaPath(G,w,v,path,d);

//递归调用

p=p->nextarc; //p指向下一个相邻点}}7.3图的遍历78/88

【例7.11】假设图G采用邻接表存储，设计一个算法求顶点u到顶点v（u≠v）之间的所有简单路径（假设两顶点之间存在一条或多条简单路径）。7.3图的遍历79/88采用带回溯DFS设计求解算法FindallPath(G,u,v,path,d)。先置visited数组的所有元素值为0。从顶点u开始，置visited[u]=1，…。7.3图的遍历当找到的某个未访问过的邻接点un=v，说明path中存放的是顶点u到v的一条简单路径，输出path。每次输出的path构成顶点u到v的全部简单路径中的一条，所有输出的path构成顶点u到v的全部简单路径。f(G,u,v,…)f(G,u1,v,…)f(G,v,v,…)…visited[v]=0找不到未访问的相邻顶点80/88voidFindallPath(AdjGraph*G,intu,intv,intpath[],intd){ArcNode*p;intw,i;

visited[u]=1;

d++;path[d]=u; //顶点u加入到路径中

if(u==v)

//找到一条简单路径{for(i=0;i<=d;i++) //输出找到一条路径并返回

printf("%d",path[i]);

printf("\n");

visited[u]=0;

//回溯找所有简单路径

}else

{p=G->adjlist[u].firstarc; //