实际上就是我们在一个复杂的地图中寻找一条能够从起点到达终点的路径。可以看到从起点开始，每到一个路口，可能都会出现多个分叉，可能有的分叉就会走进死胡同，有的分叉就会走到下一个路口。

那么我们人脑是怎么去寻找到正确的路径呢？
示意图
我们首先还是会从起点开始看，我们会尝试去走分叉路的每一个方向，如果遇到死胡同，那么我们就退回到上一个路口，再去尝试其他方向，直到能一直往下走为止。经过不断重复上述的操作，最后我们就肯定能够到达迷宫的出口了。

而图的搜索，实际上也是类似于迷宫这样的形式，我们需要从图的某一个顶点出发，去寻找到图中对应顶点的位置，这一部分，我们将对图的搜索算法进行讨论。
示意图

深度优先搜索（DFS）

什么是DFS

比如现在我们要从A开始寻找下图中的I：
示意图
那么我们的路线可以是这样的：
示意图
此时顶点B有三个方向，那么我们可以先随便选一个方向（当然，一般情况下为了规范，推荐按照字母排列顺序来走，这里为了演示，就随便走了）看看：
示意图
此时来到K，我们发现K已经是一个死胡同，没有其他路了，那么此时我们就需要回到上一个路口，继续去探索其他的路径：
示意图
此时我们接着往下一个相邻的顶点G走，发现G有其他的分叉，那么我们就继续向前：
示意图
此时走到F发现又是死路，那么退回到G，走其他的方向：
示意图
运气太垃了，又到死胡同了，同样的，回到G继续走其他方向：
示意图
走到C之后，我们有其他的路，我们继续往后走：
示意图
此时走到顶点H，发现H只有一条路，并且H再向前是已经走过的顶点B，那么此时不能再向前了，所以说直接退回到C，走另一边：
示意图
此时来到E，又有两条路，那么继续随便选一条走：
示意图
此时来到顶点J，发现又是死胡同，退回到E，继续走另一边：
示意图
好了，经过了这么多试错，终于是找到了I顶点，这种方式就是深度优先搜索（DFS）了。

代码实操

初始化

那么我们就来打个代码玩玩吧，这里我们构建一个简单一点的图：
示意图
这里我们使用邻接表表示图，因为邻接表直接保存相邻顶点，所以说到达顶点时遍历相邻顶点会更快（能够到达 O(V+E)O(V+E) 线性阶）而如果使用邻接矩阵的话，我们得完整遍历整个二维数组，就比较费时间了（需要 O(V2)O(V2) 平方阶）。

比如现在我们想从A开始查找顶点F，首先先把图给建好（注意有6个顶点，记得容量写好）：

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
    Graph graph = create();
    for (int c = 'A'; c <= 'F' ; ++c)
        addVertex(graph, (char) c);
    addEdge(graph, 0, 1);   //A -> B
    addEdge(graph, 1, 2);   //B -> C
    addEdge(graph, 1, 3);   //B -> D
    addEdge(graph, 1, 4);   //D -> E
    addEdge(graph, 4, 5);   //E -> F

    printGraph(graph);
}

示意图

搜索

然后就是我们的深度优先搜索算法了：

1
2
3
4
5
6
7
8
9
10
/**
 * 深度优先搜索算法
 * @param graph 图
 * @param startVertex 起点顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 已到达过的顶点数组
 */
void dfs(Graph graph, int startVertex, int targetVertex, int * visited){

}

我们先将深度优先遍历写出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 深度优先搜索算法（无向图和有向图都适用）
 * @param graph 图
 * @param startVertex 起点顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 已到达过的顶点数组
 */
void dfs(Graph graph, int startVertex, int targetVertex, int * visited) {
    visited[startVertex] = 1;   //走过之后一定记得mark一下
    printf("%c -> ", graph->vertex[startVertex].element);   //打印当前顶点值
    Node node = graph->vertex[startVertex].next;   //遍历当前顶点所有的分支
    while (node) {
        if(!visited[node->nextVertex])   //如果已经到过（有可能是走其他分支到过，或是回头路）那就不继续了
            dfs(graph, node->nextVertex, targetVertex, visited);  //没到过就继续往下走，这里将startVertex设定为对于分支的下一个顶点，按照同样的方式去寻找
        node = node->next;
    }
}

int main(){
    ...

    int arr[graph->vertexCount];
    for (int i = 0; i < graph->vertexCount; ++i) arr[i] = 0;
    dfs(graph, 0, 5, arr);
}

深度优先遍历结果如下：
示意图
路线如下：
示意图
现在我们将需要查找的顶点进行判断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 深度优先搜索
 * @param graph 图
 * @param startVertex 起点顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 已到达过的顶点数组
 * @return 搜索结果，如果找到返回1，没找到返回0
 */
_Bool dfs(Graph graph, int startVertex, int targetVertex, int * visited) {
    visited[startVertex] = 1;
    printf("%c -> ", graph->vertex[startVertex].element);
    if(startVertex == targetVertex) return 1;   //如果当前顶点就是要找的顶点，直接返回
    Node node = graph->vertex[startVertex].next;
    while (node) {
        if(!visited[node->nextVertex])
            if(dfs(graph, node->nextVertex, targetVertex, visited))  //如果查找成功，直接返回1，不用再看其他分支了
                return 1;
        node = node->next;
    }
    return 0;   //while结束那肯定是没找到了，直接返回0
}

int main(){
    ...

    int arr[graph->vertexCount];
    for (int i = 0; i < graph->vertexCount; ++i) arr[i] = 0;
    printf("\n%d", dfs(graph, 0, 5, arr));
}

得到结果如下：
示意图
再来找一下顶点D呢：
示意图
可以看到到D之后就停止了，因为已经找到了。那么要是去寻找一个没有连接到图中的结点呢？
示意图
可以看到整个图按照深度优先遍历找完了都没找到。

广度优先搜索（BFS）

什么是BFS

前面我们介绍了深度优先搜索，我们接着来看另一种方案。还记得我们在前面二叉树中学习的层序遍历吗？
示意图
层序遍历实际上是优先将每一层进行遍历，而不是像前序遍历那样勇往直前，而图的搜索其实也可以采用这种方案，我们可以先探索顶点所有的分支，然后再依次去看这些分支的所有分支：
示意图
我们先记录一下这三个顶点，同样需要使用队列来完成：H、G、K

注意访问之后不要再继续向下了，接着我们从这三个里面的第一个顶点H开始，按照同样的方法继续：
示意图
此时因为只有一个分支，所以说找到C，继续记录，将C也添加进去：G、K、C

注意此时需要回去，继续看之前三个顶点的第二个顶点G：
示意图
此时C已经看过了，接着就找到了F和D，也是记录一下：K、C、F、D

示意图
此时K已经是死胡同了，那么就结束，然后继续看下一个C：
示意图
时继续将E给记录进去：F、D、E，接着看D和F，也没有后续了，那么最后就只有E了：
示意图
成功找到目标I顶点，实际上广度优先遍历就是尽可能地扩展范围，多去探索广阔的土地，而不是死拽着一根不放。

代码实现

那么按照这个思路，我们就来尝试代码实现一下，首先把队列搬过来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
typedef int T;   //这里将顶点下标作为元素

struct QueueNode {
    T element;
    struct QueueNode * next;
};

typedef struct QueueNode * QNode;

struct Queue{
    QNode front, rear;
};

typedef struct Queue * LinkedQueue;

_Bool initQueue(LinkedQueue queue){
    QNode node = malloc(sizeof(struct QueueNode));
    if(node == NULL) return 0;
    queue->front = queue->rear = node;
    return 1;
}

_Bool offerQueue(LinkedQueue queue, T element){
    QNode node = malloc(sizeof(struct QueueNode));
    if(node == NULL) return 0;
    node->element = element;
    queue->rear->next = node;
    queue->rear = node;
    return 1;
}

_Bool isEmpty(LinkedQueue queue){
    return queue->front == queue->rear;
}

T pollQueue(LinkedQueue queue){
    T e = queue->front->next->element;
    QNode node = queue->front->next;
    queue->front->next = queue->front->next->next;
    if(queue->rear == node) queue->rear = queue->front;
    free(node);
    return e;
}

案例

我们还是以上面的图为例：
示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 广度优先遍历
 * @param graph 图
 * @param startVertex 起点顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 已到达过的顶点数组
 * @param queue 辅助队列
 */
void bfs(Graph graph, int startVertex, int targetVertex, int * visited, LinkedQueue queue) {
    offerQueue(queue, startVertex);  //首先把起始位置顶点丢进去
    visited[startVertex] = 1;   //起始位置设置为已走过
    while (!isEmpty(queue)) {
        int next = pollQueue(queue);
        printf("%c -> ", graph->vertex[next].element);  //从队列中取出下一个顶点，打印
        Node node = graph->vertex[next].next;    //同样的，把每一个分支都遍历一下
        while (node) {
            if(!visited[node->nextVertex]) {   //如果没有走过，那么就直接入队
                offerQueue(queue, node->nextVertex);
                visited[node->nextVertex] = 1;   //入队时就需要设定为1了
            }
            node = node->next;
        }
    }
}

我们来测试一下吧：

1
2
3
4
5
6
7
8
9
int main(){
  	...
      
    int arr[graph->vertexCount];
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < graph->vertexCount; ++i) arr[i] = 0;
    bfs(graph, 0, 5, arr, &queue);
}

成功得到结果：
示意图
如果要指定查找的话，就更简单了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
_Bool bfs(Graph graph, int startVertex, int targetVertex, int * visited, LinkedQueue queue) {
    offerQueue(queue, startVertex);
    visited[startVertex] = 1;
    while (!isEmpty(queue)) {
        int next = pollQueue(queue);
        printf("%c -> ", graph->vertex[next].element);
        Node node = graph->vertex[next].next;
        while (node) {
            if(node->nextVertex == targetVertex) return 1;   //如果就是我们要找的，直接返回1
            if(!visited[node->nextVertex]) {
                offerQueue(queue, node->nextVertex);
                visited[node->nextVertex] = 1;
            }
            node = node->next;
        }
    }
    return 0;   //找完了还没有，那就返回0
}

这样，我们就实现了图的广度优先搜索。

说些什么吧！

twikoo