深度优先搜索(Depth First Search, DFS)
深度优先遍历图的方法是，从图中某顶点v出发：
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
可以看到这里面运用了递归的思想，下面给出了DFS算法基于邻接矩阵与邻接表的不同算法。对于基于邻接矩阵的算法，由于其是一个二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此其时间复杂度为O(n^2)，而基于邻接表的DFS算法的时间复杂度则为O(n+e)。
基于邻接矩阵的DFS算法实现：
#include "邻接矩阵.h"
#define TRUE 1
#define FALSE 0
typedef int Boolean;
Boolean visited[MAXVEX];
void DFS(MGraph G, int i) {
int j;
visited[i] = TRUE;
printf("%c", G.vexs[i]); /*输出访问顶点*/
for(j = 0; j < G.numVertexes; j++){
if(G.vexs[i][j] >= 1 && !visited[j]){
/*为什么是>=1?因为可能是网，带有权值*/
/*倘若(vi,vj)有边而且顶点j未被访问过则:*/
DFS(G, j);
}
}
}
void DFSTraverse(MGraph G){
int i;
/*初始化visited数组，置所有顶点访问状态为FALSE*/
for(i = 0; i < G.numVertexes; i++){
visited[i] = FALSE;
}
for(i = 0; i < G.numVertexes; i++){
/*对应连通图，这个循环只会执行一次，对于非连通图执行的次数为连通分量的个数，循环直到所有顶点都被访问。*/
if(!visited[i]){
DFS(G, i);
}
}
}
基于邻接表的DFS算法实现：
#include "邻接表.h"
#define TRUE 1
#define FALSE 0
typedef int Boolean;
Boolean visited[MAXVEX];
void DFS(GraphAdjList G, int i){
EdgeNode * e;
visited[i] = TRUE;
printf("%c", G->adjList[i].data);
e = G->adjList[i].firstEdge;
while(e){
if(!visited[e->adjVex]){
DFS(G, e->adjVex);
}
e = e->next;
}
}
void DFSTraverse(GraphAdjList G){
int i;
/*初始化visited数组，置所有顶点访问状态为FALSE*/
for(i = 0; i < G->numVertexes; i++){
visited[i] = FALSE;
}
for(i = 0; i < G->numVertexes; i++){
/*对应连通图，这个循环只会执行一次，对于非连通图执行的次数为连通分量的个数，循环直到所有顶点都被访问。*/
if(!visited[i]){
DFS(G, i);
}
}
}
广度优先搜索(Breadth First Search, BFS)
1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到，结束程序。 [1]
基于邻接矩阵的BFS算法实现：
#include "邻接矩阵.h"
#define TRUE 1
#define FALSE 0
typedef int Boolean;
Boolean visited[MAXVEX];
void BFSTraverse(MGraph G){
int i, k, j;
Queue Q;
for(i = 0; i < G.numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q);
for(i = 0; i < G.numVertexes; i++){
if(!visited[i]){
visited[i] = TRUE;
printf("%c", G.vexs[i]);
Enqueue(&Q, i);
while(!QueueEmpty(Q)){
Dequeue(&Q, &k);/*队首出队赋给i*/
/*判断其他所有顶点若与当前顶点存在边且未访问过*/
for(j = 0; j < G.numVertexes; j++){
if(G.arc[k][j] >= 1 && visited[j]){
visited[j] = TRUE;
printf("%c", G.vexs[j]);
Enqueue(&Q, j);
}
}
}
}
}
}
基于邻接表的BFS算法实现：
#include "邻接表.h"
#define TRUE 1
#define FALSE 0
typedef int Boolean;
Boolean visited[MAXVEX];
void BFSTraverse(GraphAdjList G, int i){
EdgeNode * e;
int i, k;
Queue Q;
for(i = 0; i < G->numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q);
for(i = 0; i < G->numVertexes; i++){
if(!visited[i]){
visited[i] = TRUE;
printf("%c", G->adjList[i].data);
Enqueue(&Q, i);
while(!QueueEmpty(Q)){
Dequeue(&Q, &k);
e = G->adjList[k].firstEdge;
while(e){
if(!visited[e->adjvex]){
visited[e->adjvex] = TRUE;
printf("%c", G->adjList[e->adjvex].data);
Enqueue(&Q, e->adjvex);/*将此顶点入队*/
}
p = p->next;/*指向下一个邻接点*/
}
}
}
}
}
DFS BFS两者的区别举例说明
假设我们要在家里找某一样找不到的东西，我们会有很多种寻找的方案，如果我们采用深度优先搜索，就可以这样去理解：先到卧室，寻找柜子，再寻找搜索柜子里的抽屉，再寻找抽屉里的收纳盒。。。以此类推直到我们已经寻遍卧室的每一个角落。再去搜索书房。。。就类似于树的前序遍历。而对于广度优先算法我们可以这样理解：第一轮先搜索卧室的柜子、书房的柜子、客厅的柜子,第二轮寻找卧室的柜子里的抽屉、书房的柜子的抽屉、客厅的柜子的抽屉。。。以此类推。和树的层序遍历很相似。
网友评论