深度优先搜索(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两者的区别举例说明

假设我们要在家里找某一样找不到的东西，我们会有很多种寻找的方案，如果我们采用深度优先搜索，就可以这样去理解：先到卧室，寻找柜子，再寻找搜索柜子里的抽屉，再寻找抽屉里的收纳盒。。。以此类推直到我们已经寻遍卧室的每一个角落。再去搜索书房。。。就类似于树的前序遍历。而对于广度优先算法我们可以这样理解：第一轮先搜索卧室的柜子、书房的柜子、客厅的柜子,第二轮寻找卧室的柜子里的抽屉、书房的柜子的抽屉、客厅的柜子的抽屉。。。以此类推。和树的层序遍历很相似。