算法设计深度优先遍历和广度优先遍历.docx
《算法设计深度优先遍历和广度优先遍历.docx》由会员分享，可在线阅读，更多相关《算法设计深度优先遍历和广度优先遍历.docx（15页珍藏版）》请在冰点文库上搜索。
算法设计深度优先遍历和广度优先遍历
深度优先遍历过程
1、图的遍历
和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
它是许多图的算法的基础。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
它们对无向图和有向图均适用。
以下假定遍历过程中访问顶点的操作是简单地输出顶点。
2、布尔向量visited[0．．n-1]的设置图中任一顶点都可能和其它顶点相邻接。
在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。
为了避免重复访问同一个顶点，必须记住每个已访问的顶点。
为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。
深度优先遍历（Depth-FirstTraversal）
1．图的深度优先遍历的递归定义
假设给定图G的初态是所有顶点均未曾访问过。
在G中任选一顶点V为初始出发
点（源点），则深度优先遍历可定义如下：
首先访问出发点V,并将其标记为已访问过；
然后依次从V出发搜索V的每个邻接点W。
若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。
若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。
采用的搜索方法的特点是尽可能先对纵深方向进行搜索。
这种搜索方法称为深度优先搜索（Depth-FirstSearch）。
相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。
2、深度优先搜索的过程
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的
边（X,y）。
若发现顶点y已访问过，则重新选择另一条从X出发的未检测过的边，否则
沿边（X，y）到达未曾访问过的y,对y访问并将其标记为已访问过；然后从y开始搜索,直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到
顶点X,并且再选择一条从X出发的未检测过的边。
上述过程直至从X出发的所有边都
已检测过为止。
此时，若X不是源点，则回溯到在X之前被访问过的顶点；否则图中
所有和源点有路径相通的顶点（即从源点可达的所有顶点）都已被访问过，若图G是连
通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
3、深度优先遍历的递归算法
（1）深度优先遍历算法
typedefenum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Booleanvisited[MaXVerteXNum]；//访问标志向量是全局量
voidDFSTraverse（ALGraph*G）
{//深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时，算法完全与此相同
inti；
for（i=0;in;i++）
visited[i]=FALSE；//标志向量初始化
for（i=0;in；i++）
if（!
visited[i]）//vi未访问过
DFS（G，i）；Il以Vi为源点开始DFS搜索
}//DFSTraverse
（2）邻接表表示的深度优先搜索算法
VoidDFS（ALGraph*G，inti）{
Il以Vi为出发点对邻接表表示的图G进行深度优先搜索
EdgeNode*p；
printf（"VisitVerteX：
％c"，G->adjlist[i].VerteX）；II访问顶点Vi
Visited[i]=TRUE；II标记Vi已访问
p=G->adjlist[i].firstedge；II取Vi边表的头指针
While（P）{//依次搜索Vi的邻接点Vj,这里j=p->adjvex
if（!
Visited[p->adjVeX]）II若Vi尚未被访问
DFS（G，p->adjVeX）;//则以Vj为出发点向纵深搜索
p=p->neXt；//找Vi的下一邻接点
}
}//DFS
3）邻接矩阵表示的深度优先搜索算法
voidDFSM（MGraph*G，inti）
{Zz以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,1矩阵
intj；
Printf（"visitVerteX:
%c",G->vexs[i]）;ZZ访问顶点Vi
Visited[i]=TRUE；
for（j=0；jn；j++）ZZ依次搜索vi的邻接点if（G->edges[i][j]==1&&!
visited[j]）
DFSM（G,j）ZZ（vi,Vj）∈E,且Vj未访问过，故Vj为新出发点
}ZZDFSM
遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraPh或MGraPh类型的参数,而不一定要定义为ALGraPh和MGraPh的指针类型。
但基于效率上的考虑,选择指针类型的参数为宜。
4、深度优先遍历序列对图进行深度优先遍历时,按访问顶点的先后次序得到的顶点序列称为该图的深度
优先遍历序列，或简称为DFS序列。
（1）一个图的DFS序列不一定惟一
当从某顶点X出发搜索时，若X的邻接点有多个尚未访问过，则我们可任选一个访问之。
（2）源点和存储结构的内容均已确定的图的DFS序列惟一
1邻接矩阵表示的图确定源点后，DFS序列惟一
DFSM算法中，当从Vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点,若这样的邻接点多于一个,则选中的总是序号较小的那一个。
2只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列
邻接表作为给定图的存储结构时,其表示不惟一。
因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关。
因此，只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列。
3）栈在深度优先遍历算法中的作用
深度优先遍历过程中,后访问的顶点其邻接点被先访问,故在递归调用过程中使用栈（系统运行时刻栈）来保存已访问的顶点。
5、算法分析
对于具有n个顶点和e条边的无向图或有向图,遍历算法DFSTraVerse对图中每顶点至多调用一次DFS或DFSMO从DFSTraVerSe中调用DFS（或DFSM）及DFS（或
DFSM）内部递归调用自己的总次数为n
当访问某顶点Vi时，DFS（或DFSM）的时间主要耗费在从该顶点出发搜索它的所有邻接点上。
用邻接矩阵表示图时，其搜索时间为O（n）；用邻接表表示图时，需搜索第i
个边表上的所有结点。
因此，对所有n个顶点访问，在邻接矩阵上共需检查n2个矩阵
元素，在邻接表上需将边表中所有O（e）个结点检查一遍。
所以，DFSTraVerSe的时间复杂度为0（n2）（调用DFSM）或0（n+e）（调用DFS）
1、广度优先遍历的递归定义
设图G的初态是所有顶点均未访问过。
在G中任选一顶点V为源点，则广度优先
遍历可以定义为：
首先访问出发点V,接着依次访问V的所有邻接点w1,w2,…，Wt,
然后再依次访问与wl,w2,…，Wt邻接的所有未曾访问过的顶点。
依此类推，直至图中所有和源点V有路径相通的顶点都已访问到为止。
此时从V开始的搜索过程结束。
若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源
点继续上述的搜索过程，直至G中所有顶点均已被访问为止。
广度优先遍历类似于树的按层次遍历。
采用的搜索方法的特点是尽可能先对横向进行搜索,故称其为广度优先搜索（Breadth-FirstSearch）。
相应的遍历也就自然地称为广度优先遍历。
2、广度优先搜索过程
在广度优先搜索过程中，设X和y是两个相继要被访问的未访问过的顶点。
它们的邻接点分别记为x1,x2,…,xs和y1,y2,…,yt。
为确保先访问的顶点其邻接点亦先被访问,在搜索过程中使用FIFO队列来保存已访问过的顶点。
当访问X和y时，这两个顶点相继入队。
此后，当X和y相继出队时，
我们分别从X和y出发搜索其邻接点x1,x2,…，XS和y1,y2,…，yt,对其中未访者进行访问并将其人队。
这种方法是将每个已访问的顶点人队，故保证了每个顶点至多只有一次人队。
3、广度优先搜索算法
（1）邻接表表示图的广度优先搜索算法
VoidBFS（ALGraph*G，intk）
{//以Vk为源点对用邻接表表示的图G进行广度优先搜索
inti；
CirQueueQ；//须将队列定义中DataType改为int
EdgeNode*p；
InitQueue（&Q）；//队列初始化
//访问源点vk
printf（"visitvertex：
％e"，G->adjlist[k].vertex）；
visited[k]=TRUE；
EnQueue（&Q，k）；//vk已访问，将其人队。
（实际上是将其序号人队）while（!
QueueEmpty（&Q））{//队非空则执行
i=DeQueue（&Q）；//相当于vi出队p=G->adjlist[i].firstedge；//取vi的边表头指针while（p）{//依次搜索vi的邻接点vj（令p->adjvex=j）if（!
visited[p->adivex]）{//若vj未访问过
printf（"visitvertex：
％c"，C->adjlistlp->adjvex].vertex）；//访问vj
visited[p->adjvex]=TRUE；
EnQueue（&Q，p->adjvex）；//访问过的vj人队}//endifp=p->next；//找vi的下一邻接点
}//endwhile
}//endwhile
}//endofBFS
2）邻接矩阵表示的图的广度优先搜索算法voidBFSM（MGraph*G，intk）
{以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
inti，j；CirQueueQ；
InitQueue（&Q）；
printf（"VisitVertex：
％c"，G->Vexs[k]）；//访问源点VkVisited[k]=TRUE；
EnQueue（&Q，k）；while（!
QueueEmpty（&Q））{i=DeQueue（&Q）；//Vi出队for（j=0;jn;j++）//依次搜索Vi的邻接点Vjif（G->edges[i][j]==1&&!
Visited[j]）{//Vi未访问
printf（"VisitVertex：
％c"，G->Vexs[j]）；//访问Vi
Visited[j]=TRUE；
EnQueue（&Q，j）；//访问过的Vi人队
}
}//endwhile
}//BFSM
（3）广度优先遍历算法
类似于DFSTraverse。
4、图的广度优先遍历序列广度优先遍历图所得的顶点序列，定义为图的广度优先遍历序列，简称BFS序列。
（1）一个图的BFS序列不是惟一的
（2）给定了源点及图的存储结构时，算法BFS和BFSM所给出BFS序列就是惟一的。
5、算法分析
对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次。
广度优先遍
历（BFSTraVerSe）图的时间复杂度和DFSTraVerSe算法相同。
当图是连通图时，BFSTraVerSe算法只需调用一次BFS或BFSM即可完成遍历操作,
此时BFS和BFSM的时间复杂度分别为0（n+e）和0（n2）。
来源：
（http:
//blog.S-深度优先搜索遍历与广度优先搜索遍历_chriStina_新浪博客
//深度优先遍历算法实现：
//返回顶点V在顶点向量中的位置
intLocateVex（ALGraphG,charV）{
inti;
for（i=0;V!
=G.VerticeS[i].data&&iif（i>=G.Vexnum）
return-1;returni;
}
//构造邻接链表
StatuSCreateDN（ALGraph&G）{
inti,j;
ArcNode*S;
printf（"输入有向图顶点数:
"）;
Scanf（"%d",&G.Vexnum）;
printf（"输入有向图边数:
"）;
scanf（"%d",&G.arcnum）;getchar（）;
for（i=0;i{
printf（"输入第%d个顶点信息:
",i+1）;
scanf（"%c",&G.vertices[i]）;//构造顶点向量G.vertices[i].firstarc=NULL;getchar（）;
}
charv1,v2;
for（intk=0;k{
printf（"输入第%d条边依附的顶点v1:
",k+1）;scanf（"%c",&v1）;
getchar（）;
printf（"输入第%d条边依附的顶点v2:
",k+1）;scanf（"%c",&v2）;
getchar（）;
inti=LocateVex（G,v1）;
intj=LocateVex（G,v2）;//确定v1,v2在G中的位置
s=（ArcNode*）malloc（sizeof（ArcNode））;
s->adjvex=j;//该边所指向的顶点的位置为js->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;
}
returnOK;
}
StatusPrintAdjList（ALGraph&G）
{
inti;
ArcNode*p;
printf（"%4s%6s%12s\n","编号","顶点","相邻边编号"）;
for（i=0;i{
printf（"%4d%6c",i,G.vertices[i].data）;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
printf（"%4d",p->adjvex）;
printf（"\n"）;
}
returnOK;
voidDFS（ALGraphG,intv,int*visited）{
intw;
ArcNode*s;
visited[v]=1;
printf（"%c->",G.vertices[v].data）;s=G.vertices[v].firstarc;
while（s!
=NULL）
{
w=s->adjvex;if（visited[w]==0）
DFS（G,w,visited）;
s=s->nextarc;
}
}
Zz对图G做深度优先遍历
StatusDFSTraverse（ALGraphG）
{
intv;
intvisited[MAX_VERTEX_NUM];
for（v=0;vfor（v=0;vif（visited[v]==0）
DFS（）
DFS（G,v,visited）;ZZ对未访问的顶点调用
printf（"完成\n"）;
returnOK;
}
广度优先遍历算法实现。
ZZ返回顶点v在顶点向量中的位置intLocateVex（ALGraphG,charv）{
inti;
for（i=0;v!
=G.vertices[i].data&&iif（i>=G.vexnum）return-1;
returni;
//构造无向图邻接链表
StatusCreateUDN（ALGraph&G）
{
inti,j;
ArcNode*s,*t;printf（"输入有向图顶点数:
"）;scanf（"%d",&G.vexnum）;printf（"输入有向图边数:
"）;scanf（"%d",&G.arcnum）;
getchar（）;
for（inti=0;i{printf（"输入第%d个顶点信息:
",i+1）;scanf（"%c",&G.vertices[i]）;//构造顶点向量G.vertices[i].firstarc=NULL;
getchar（）;
}
charv1,v2;
for（intk=0;k{
printf（"输入第%d条边依附的顶点v1:
",k+1）;scanf（"%c",&v1）;
getchar（）;
printf（"输入第%d条边依附的顶点v2:
",k+1）;scanf（"%c",&v2）;
getchar（）;
inti=LocateVex（G,v1）;
intj=LocateVex（G,v2）;//确定v1,v2在G中的位置s=（ArcNode*）malloc（sizeof（ArcNode））;
t=（ArcNode*）malloc（sizeof（ArcNode））;
s->adjvex=j;//该边所指向的顶点的位置为js->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=s;
t->adjvex=i;//该边所指向的顶点的位置为j
t->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=t;
}returnOK;
}
StatusInitQueue（SqQueue&Q）{
sizeof（QElemType））;
队列已满
Q.base=（QElemType*）malloc（MAXQSIZEif（!
Q.base）
{
printf（"分配地址失败！
"）;return0;
}Q.front=Q.rear=0;returnOK;
}
//已访问图顶点入队
StatusEnQueue（SqQueue&Q,QElemTypee）{
if（（Q.rear+1）%MAXQSIZE==Q.front）//{
printf（"队列已满!
"）;return0;
}Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;returnOK;
}
//判断队列是否为空StatusQueueEmpty（SqQueueQ）
{if（Q.front==Q.rear）returnOK;
elsereturn0;
}
//辅助队列队头顶点出队charDeQueue（SqQueue&Q）
{QElemTypee;if（Q.front==Q.rear）//队列为空{
printf（"队列为空!
"）;return0;
}
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;returne;
}
StatusPrintAdjList（ALGraph&G）{
inti;
编号","顶点","相邻边编号"）;
ArcNode*p;printf（"%4s%6s%12s\n","
for（inti=0;i{
printf（"%4d%6c",i,G.vertices[i].data）;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）printf（"%4d",p->adjvex）;
printf（"\n"）;
}
returnOK;
voidDFS（ALGraphG,intv,int*visited）{
intw;
ArcNode*s;
visited[v]=1;
printf（"%c->",G.vertices[v].data）;s=G.vertices[v].firstarc;
while（s!
=NULL）
{
w=s->adjvex;if（visited[w]==0）
DFS（G,w,visited）;
s=s->nextarc;
}
}
Zz对图G做广度优先遍历
StatusBFSTraverse（ALGraphG）
{
intv,u,w;
intvisited[MAX_VERTEX_NUM];
ArcNode*s;
chare;
SqQueueQ;ZZ辅助队列
for（v=0;vInitQueue（Q）;
for（v=0;vvisited[v]=1;
printf（"%c->",G.vertices[v].data）;
EnQueue（Q,G.vertices[v].data）;ZZ已访问顶点入队
while（!
QueueEmpty（Q））ZZ辅助队列非空{
u=LocateVex（G,e）;
s=（ArcNode*）malloc（sizeof（ArcNode））;
s=G.vertices[u].firstarc;
while（s!
=NULL）//*顶点e还有邻接顶点
{w=s->adjvex;if（visited[w]==0）{visited[w]=1;printf（"%c->",G.vertices[w].data）;EnQueue（Q,G.vertices[w]
升级会员 