16-图的深搜和广搜二

图的深搜和广搜

前面一篇是利用深搜和广搜进行图的顶点的遍历，今天我们则是根据起点和终点位置进行路径的搜索。

图的深搜算法

问题：假设现在有一无向图，我现在要给你一个起始点和终点，如果可以走通请输出一条简单路径，不能则返回无路径。

思考：我们可以考虑用深度搜索去求解此问题，我们假设用邻接矩阵存储这个图。我们可以设计一个数组去保存搜索过程的路径。

注意点：算法的设计关键就是利用深搜递归可以回退参数的特点去求解，但是由于c语言的普通数组，传递的参数都是实参，无法进行回退，所以我们需要自定义伪数组去实现真正的形参，这样我们可以回退数组的结果。

深搜步骤

• 设计一个空数组，用于保存搜索整个过程经过的点，数组必须是可以回退的形参(数组作为函数参数比较特殊，它是引用传递，函数的直接修改)
• 在搜索的递归函数开始时，初始将起点添加到数组里，然后凡是和起点有关的都进行递归，于是到了第二层递归时，和起点有关的一个点又作为起点放入新的形参数组继续调用递归，，直到发现某个点等于终点，就输出数组的保存的路径，递归结束。

图示案例

我先用个形象的图，演示下递归处理的过程，假设我们要搜索A到F是否有一条简单路径。
我们就是让A先进去第一层递归，把A放入数组，接着B,C,D都和A有关联，依次进入各自的递归函数，然后进入B，C,D的那些点带着自己的数组，又作为起点将和它相连的点依次进入递归函数，整个过程就有以下搜索过程

• A-->B-->E-->F
• A-->C-->E-->F
• A-->D-->G-->H

graph12.jpg

深搜代码

//深搜的辅助操作
void Find_Path(struct MGraph *g, char obj1, char obj2)
{
    int index1, index2,*temp;
    struct Array arr;
    arr.len = 0;
    temp = (int*)malloc(sizeof(int) * g->numVretexes);
    for (int i = 0; i < g->numVretexes; i++)
    {
        if (g->vetex[i] == obj1)
        {
            index1 = i;
        }
        if (g->vetex[i] == obj2)
        {
            index2 = i;
        }
        temp[i] = 0;
    }
    DFS_Search(g, arr, temp, index1, index2);
}

//深搜的核心
void DFS_Search(struct MGraph *g, struct Array arr,int *temp, int obj1, int obj2)
{
    temp[obj1] = 1;
    arr.data[arr.len++] = obj1;
    if (obj1 == obj2)//找到了路径，输出路径
    {
        for (int i = 0; i < arr.len; i++)
        {
            printf("%c ", g->vetex[i]);
        }
        printf("\n");
    }
    for (int j = 0; j < g->numVretexes; j++)
    {
        if (g->data[obj1][j] != 0 && temp[j]==0)//有关联的点
        {
            DFS_Search(g, arr,temp, j, obj2);
        }
    }
}

图的广搜算法

问题：假设现在有一无向图，我现在要给你一个起始点和终点，请输出一条最短的行走方案。(最短就是指走过的边数最少)

思考：此时的问题已经是在寻找路径的基础上增加了一条最短路径的问题，注意此处的最短路径不是说求带权值的最短路径，此处的最短路径求的是按边的个数计算。走过的边最少的路径。

方案: 因为广度优先遍历，是逐层逐层的找，所以它肯定会在第一时间内找到我们要找的点，当然它对应的路径也就是经过边的个数一定是最少的。我们在进行广度优先遍历的基础上为每个点增加前驱标记，标记每个点的前驱是谁，这样我们就可以回退输出最短路径了。忘记广度优先遍历的可以看前一篇关于广度优先遍历的介绍。

过程演示

graph13.jpg

假设我们要寻找点A到点E的最短路径问题。

1. 初始化队列queue和前驱数组path,并让点A入队列。

队列元素	A

data	A	B	C	D	E	F
前驱顶点

2.出队一个元素，A出队列，和A有关联的点都入队列，即B与F都入队列，修改入队点B和F的前驱是A

队列元素	B	F

data	A	B	C	D	E	F
前驱顶点		A				A

3.出队一个元素，B出队列，和B有关的都入队列，被访问的点不用入队列。所以C和D入队列，修改点C和点D的前驱是B

队列元素	F	C	D

data	A	B	C	D	E	F
前驱顶点		A	B	B		A

4.出队列一个元素，所以F出队列，和F有关的都入队列，所以E入队列，修改点E的前驱是F，此时E节点找到了，直接退出。

队列元素	C	D	E

data	A	B	C	D	E	F
前驱顶点		A	B	B	F	A

好了，我们只需要查看最终的前驱数组，就可以得到最短路径了，终点E的前驱是F，F的前驱是A，到达了起点A，所以最终的最短路径就是A-F-E了。

广搜代码

void Find_Path(struct MGraph *g, char obj1, char obj2)
{
    int index1, index2, *temp,*pre,*queue,front,rear,num;
    temp = (int*)malloc(sizeof(int) * g->numVretexes);
    queue = (int*)malloc(sizeof(int) * g->numVretexes);//辅助队列
    pre = (int*)malloc(sizeof(int) * g->numVretexes);
    front = rear = 0;
    for (int i = 0; i < g->numVretexes; i++)
    {
        temp[i] = 0;
        pre[i] = -1;//前驱顶点
        if (obj1 == g->vetex[i])
        {
            index1 = i;
        }
        if (obj2 == g->vetex[i])
        {
            index2 = i;
        }
    }
    queue[rear++] = index1;
    temp[index1] = 1;
    while (front != rear)
    {
        num = queue[front++];
        if (num == index2)//找到了目标点，逆序打印路径
        {
            while (pre[num]!=-1)
            {
                printf("%c ", g->vetex[num]);
                num = pre[num];
            }
            printf("%c ", g->vetex[num]);
            printf("\n");
        }
        //出队列时，将所有有关联的点入队列
        for (int i = 0; i < g->numVretexes; i++)
        {
            if (g->data[num][i] != 0 && temp[i] == 0)
            {
                temp[i] = 1;
                queue[rear++] = i;
                pre[i] = num;//设置顶点的前驱
            }
        }
    }
}

获取完整代码

我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。

点击查看