-
算法设计：深度优先遍历和广度优先遍历实现
深度优先遍历过程
1
、图的遍历
和树的遍历类似，图的遍历也是从某个顶点出发，沿
着某条搜索路径对图中每个顶
点各做一次且仅做一次访问。它是许多图的算法的基础。<
/p>
深度优先遍历和广度优先遍
历是最为重要的两种遍历图的方法。它们对无向图和有
向图均适用。
注意：
以下假定遍历过程中访问顶点的操作是简单地输出顶点。
2
、布尔向量
visited[0
．．
n-1]
的
设置
图中任一顶点都可能
和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回
路又回到了该顶点。为了避
免重复访问同一个顶点，必须记住每个已访问的顶点。为
此，可设一布尔向量
visited[0
．．
n-1]
，其初值为假，一旦访问了顶点
Vi
之后，便将
visited[i]
置为真。
--------------------------
深度优先遍历
(Depth-First
Traversal)
1
．图的深度优先遍历的递归定义
假设给定图
G
的初态是所有顶点均未曾访问过。在
G
中任选一顶点
v
为初始出发
点
(
源点
)
，则深度优先遍历可定义如
下：首先访问出发点
v
，并将其标记为已访问过；
然后依次从
v
出发搜索
v<
/p>
的每个邻接点
w
。若
w
未曾访问过，则以
w
为新的出发
点继
续进行深度优先遍历，直至图中所有和源点
v
有路径相通的顶点
(
亦称为从源点可达的
顶点
)
均已被访问为止。若此时图中仍有未访问的
顶点，则另选一个尚未访问的顶点作
为新的源点重复上述过程，直至图中所有顶点均已被
访问为止。
图的深度优先
遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深
方向进行搜索。这种
搜索方法称为深度优先搜索
(Depth-First Search)
。相应地，用此
方法遍历图就很自然地称之为图的深度优先遍历。
2
、深度优先搜索的过程
设
x
是当前被访问顶点，在对
x
做过访问标记后，选择一条从
x
出发的未检测过的
边
(x
，
y)
。若发现顶点
y
已访问过，则重新选择另一条从
x
出发的未检测过的边，否则
沿边
(x
，
y)
到达未曾访问过的
y
，对
y
访问并将其标记为已访问过；然
后从
y
开始搜索，
直到搜索完从
y
出发的所有路径，即访问完所有从
y
出发可达的顶点之后，才回溯到
顶点
x
，并且再选择一条从
x
出发的未检测过的边。
上述过程直至从
x
出发的所有边都
已检
测过为止。此时，若
x
不是源点，则回溯到在
< br>x
之前被访问过的顶点；否则图中
所有和源点有路径相通
的顶点
(
即从源点可达的所有顶点
)<
/p>
都已被访问过，若图
G
是连
通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的
< br>搜索过程。
3
、深度优先遍历的递归算法
（
1
）深度优先遍历算法
typedef enum{FALSE
，
TRUE}Boolean
；
//FALSE<
/p>
为
0
，
TRUE
为
1
Boolean
visited[MaxVertexNum]
；
//
访问标志向量是全局量
void DFSTraverse(ALGraph *G)
{ //
深度优先遍历以邻接表表示的图
G
，而以邻接矩
阵表示
G
时，算法完全与此相同
int i
；
for(i=0;i
visited[i]=FALSE
；
//
标志向量初始化
for(i=0;i
；
i++)
if(!visited[i])
//vi
未访问过
DFS(G
，
i)
；
< br> //
以
vi
为源点开始
DFS
搜索
}//DFSTraverse
（
2
）邻接表表示的深度优先搜索算法
void DFS(ALGraph *G
，
int i){
//
以
vi
< br>为出发点对邻接表表示的图
G
进行深度优先搜索
EdgeNode
*p
；
printf(
：％
c
，
G->a
djlist[i].vertex)
；
//
< br>访问顶点
vi
visited[i]=TRUE
；
//
标记
vi
已访问
p=G->adjlist[i].firstedge
；
/
/
取
vi
边表的头指针
while(p){//
依次搜索
vi
的邻接点
vj
，这
里
j=p->adjvex
if (!visi
ted[p->adjvex])//
若
vi
< br>尚未被访问
DFS(G
，
p->adjvex);//
则以
Vj
为出发点向纵深搜索
p=p->next
；
//
找
vi
的下一邻接点
}
}//DFS
（
3
）邻接矩阵表示的深度优先搜索算法
void DFSM(MGraph
*G
，
int i)
{ //<
/p>
以
vi
为出发点对邻接矩阵表示的图
G
进行
DFS
搜索
，设邻接矩阵是
0,l
矩阵
int j
；
printf(
：％
c
，
G->vexs[i])
；
//
访问顶点
vi
visited[i]=TRUE
；
for(j=0
；
j
；
j++) //
依次搜索
vi
的邻接点
if(G->edges[i][j]==1&&!visited[j])
DFSM(G
，
j)//(vi
，
vj)
∈
E
，且<
/p>
vj
未访问过，故
vj
< br>为新出发点
}//DFSM
注意：
遍历操作不会修改图
G
的内容，故上述
算法中可将
G
定义为
ALGraph<
/p>
或
MGraph
类型的参数，而不一定要
定义为
ALGraph
和
MGraph
的指针类型。但基于效率上的考
虑，选择指针类型的参数为宜。
4
、深度优先遍历序列
对图进行深度优先遍历时，按访问顶点的先后次序得
到的顶点序列称为该图的深度
优先遍历序列，或简称为
DFS<
/p>
序列。
（
1<
/p>
）一个图的
DFS
序列不一定惟一
当从某顶点
x
出发搜索时，若
x
的邻接点有多
个尚未访问过，则我们可任选一个访
问之。
（
2
）源点
和存储结构的内容均已确定的图的
DFS
序列惟一
①
邻接矩阵表示的图确
定源点后，
DFS
序列惟一
DFSM
算法中，当从
vi<
/p>
出发搜索时，是在邻接矩阵的第
i
行上从
左至右选择下一个
未曾访问过的邻接点作为新的出发点，若这样的邻接点多于一个，则选
中的总是序号
较小的那一个。
②
只有给出了邻接表的内容及初始出发点，才能惟一确定其
DFS
序列
邻接表作为给定图的存储结构时，其表示不惟一。因为邻接表上边表里的邻接点域
的内容
与建表时的输入次序相关。
因此，只有给出了邻接表的内容及初始出发点，才能惟一确定其
DFS
序列。
3
）栈在深度优先遍历算法中的作用
深度优先遍历过程中，后访问的顶点其邻接点被先访问
，故在递归调用过程中使用
栈（系统运行时刻栈）来保存已访问的顶点。
5
、算法分析
对于具有
n
< br>个顶点和
e
条边的无向图或有向图，遍历算法
DFSTraverse
对图中每顶
点至多调用一
次
DFS
或
DFSM
< br>。从
DFSTraverse
中调用
DFS(
或
DFSM)
及
DFS(
或
DFSM)
内部递归调用自己的总次数为
n
。
当访问某顶点
vi
时，
DFS(
或
DFSM
)
的时间主要耗费在从该顶点出发搜索它的所有邻
接点上。用邻
接矩阵表示图时，其搜索时间为
O(n)
；用邻接表表示图时，
需搜索第
i
个边表上的所有结点。因此，对所有
n
个顶点访问，在邻接矩阵上共需检查
n2
个矩阵
元素，在邻接表上需将边表中所有
O(e)
个结点检查一遍。
所以，
DFSTraverse
的时间复杂度为
O(n2)
（调用
DFSM
）或
0(n+e)
（调用
DFS
）。
< br>----------------------------------------------- ----------------------------
1
、广度优先遍历的递归定义
设图
G
的初态是所有顶点均未访问过。在
G
中任选一顶点
v
为源点，则广度优先
遍历可以定义为：首先访
问出发点
v
，接着依次访问
v
的所有邻接点
w1
，
w
2
，
…
，
wt
，
然后再依次访问与
wl
，
w2
，
…
，
wt
邻接的所有未曾访问过的顶点。依此类推，直至
图
中所有和源点
v
有路径相通的顶点都
已访问到为止。此时从
v
开始的搜索过程结束。
若
G
是连通图，则遍历完成；否则，在图
C
中另选一个
尚未访问的顶点作为新源
点继续上述的搜索过程，直至
G
中所有顶点均已被访问为止。
<
/p>
广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进
行搜索，故称其为广度优先搜索
(Breadth-FirstSear
ch)
。相应的遍历也就自然地称为广
度优先遍历。
2
、广度优先搜索过程
在广度优先搜索过程中，设
x<
/p>
和
y
是两个相继要被访问的未访问过的顶
点。它们的
邻接点分别记为
x1
，
x2
，
…
，
xs
和
y1
，
y2
，
…
，
yt
。
<
/p>
为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用
FI
FO
队列来保存已
访问过的顶点。当访问
x
和
y
时，这两个顶点相继入队。此
后，当
x
和
y
相继出队时，
我们分别从
x
和
y
出发搜索其邻接点
x1
，
x2
，
…
，
xs
和
y1
，
y2
，
…
，
yt
，对其中未访
者进行访问并将其人
队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至
多只有一次人队。
3
、广度优先搜索算法
(1)
邻接表表示图的广度优先搜索算法
void
BFS(ALGraph*G
，
int k)
{//
以
vk
< br>为源点对用邻接表表示的图
G
进行广度优先搜索
int
i
；
CirQueue
Q
；
//
须将队列定义中
DataType
改为
int
EdgeNode *p
；
InitQueue(&Q)
；
//
队列初始化
//
访问源点
vk
pri
ntf(
：％
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(
< br>令
p->adjvex=j)
if(!visited[p->adivex]){ //
若
vj
未访问过
printf(
：％
c
，
C->adjlistlp->adjvex].vertex)
；
//
访问
vj
visited[p->adjvex]=TRUE
；
EnQueue(&Q
，
p->adjvex)
；
//
访问过的
vj
人队
}//endif
p=p->next
；
//
找
vi
的下一邻接点
}//endwhile
}//endwhile
}//end of BFS
（
2
）邻接矩阵表示的图的广度优先搜索算法
void BFSM(MGraph
*G
，
int k)
{
以
vk
为源点对用邻接矩阵表示的图
G
进行广度优先搜索
int
i
，
j
；
CirQueue Q
；
InitQueue(&Q)
；
printf(
：％
c
，
G->vexs[k])
；
< br> //
访问源点
vk
visited[k]=TRUE
；
EnQueue(&Q
，
k)
；
while(!QueueEmpty(&Q)){
i=DeQueue(&Q)
；
//vi
出队
for(
j=0;j
依次搜索
vi
的邻接点
vj
if(G-
>edges[i][j]==1&&!visited[j]){//vi
未访问
printf(
< br>：％
c
，
G->vexs[j]
)
；
//
访问
vi
visited[j]=TRUE
；
EnQueue(&Q
，
j)
；
//
访问过的
vi
人
队
}
}//endwhile
}//BFSM
（
3
）广度
优先遍历算法
类似于
DFSTraverse
。
4
、图的广度优先遍历序列
广度优先遍历图所得的顶点序列，定义为图的广度优
先遍历序列，简称
BFS
序列。
（
1
）一个图的
B
FS
序列不是惟一的
（
2
）给定了源点及图的存储结构时，算法
BFS
和
BFSM
所给出
BFS
序列就是惟一的。
5
、算法分析
对于具有
n
个顶点和
e
条边的无向图或有向图，每个顶点均入队一
次。广度优先遍
历
(BFSTraverse)
图的时间复杂度和
DFSTraverse
算法相同。
当图是连通图时，
BFSTraverse
算法只需调用一次
B
FS
或
BFSM
即可完成遍历操作，<
/p>
此时
BFS
和
B
FSM
的时间复杂度分别为
O(n+e)
和
0(n2)
。来源：
(/s/bl
og_) -
深度优先搜索遍历与广度
优先搜索遍历
_christina_
新浪博客
--------------------------
------------------------------
//
深度优先遍历算法实现：
//
返回顶点
v
在顶
点向量中的位置
int
LocateVex(ALGraph G, char v)
{
int i;
for(i
= 0; v != es[i].data && i < i++)
;
if(i >= )
return -1;
return i;
}
//
构造邻接链表
Status CreateDN(ALGraph &G)
{
int i,j;
ArcNode *s;
printf(
输入有向图顶点数
:
scanf(
printf(
输入有向图边数
:
-
-
-
-
-
-
-
-
-
上一篇：CFX用户手册-User Fortran
下一篇：苦累面前莫低头(部队苦累关教育)