图的遍历

· · 个人记录

图的遍历

图

简单的来说，图就是由一些小圆点（顶点）和连接这些点的直线（边）组成的图形。如下图：

就是由四个点(A,B,C,D)和四条边(A-B)(A-D)(B-C)(C-D)组成的 而图的遍历，就是把整个图走一遍

图的遍历

一般来说，有几种遍历方式：

深搜

深搜的基本思路：一条路走到死，走完之后回到上一个顶点看看有没有别的路，没有就再往上一个顶点，直到有，就往下遍历即可。
而存储，一般使用矩阵进行存储，我们假定连着是1，没连是\infty，自己本身用0

首先，是遍历本身：

//cur是当前所在的顶点编号
//二维数组e是存储整个图的矩阵
//book数组是存储顶点是否访问过的数组
//访问过为1，没访问过为0
//sum用来记录已经访问过多少点
//变量n存储的是图的顶点总个数
void dfs(int cur)
{
    printf("%d ",cur);
    sum++;//每访问一个顶点sum就加1
    if (sum == n)
    {
        return;//所有的顶点都已经访问过则直接退出
    }
    for (int i = 1; i <= n; i++)
    {
        //判断当前顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
        if (e[cur][i] == 1 && book[i] == 0)
        {
            book[i] = 1;//标记顶点i已经访问过
            dfs(i);//从顶点i再出发开始遍历
        }
    }
    return;
}

完整代码如下

#include <stdio.h>
//cur是当前所在的顶点编号
//二维数组e是存储整个图的矩阵
//book数组是存储顶点是否访问过的数组
//访问过为1，没访问过为0
int book[101]={0}, sum, n, e[101][101]={{0}};
void dfs(int cur)//cur是当前所在的顶点编号 
{
    int i;
    printf("%d ",cur);
    sum++;//每访问一个顶点sum就加1
    if (sum == n)
    {
        return ;//所有的顶点都已经访问过则直接退出
    }
    for (int i = 1; i <= n; i++)//从1号到n号顶点依次尝试，看哪些与当前的顶点cur相连
    {
        //判断当前顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
        if (e[cur][i] == 1 && book[i] == 0)
        {
            book[i] = 1;//标记顶点i已经访问过
            dfs(i);//从顶点i再出发开始遍历
        }
    }
    return ;
}
int main()
{
    int i, j, m, a, b;
    scanf("%d %d", &n, &m);
    //初始化二维矩阵
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
            {
                e[i][j] = 0;
            }
            else
            {
                e[i][j] = 99999999;//假定99999999为正无穷
            }
        }
    }
    //读入顶点之间的边
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1;//这里是无向图，所以需要将e[a][b]也赋为1
    }
    //从1号顶点出发
    book[1] = 1;//标记1号顶点已访问
    dfs(1);//从1号顶点开始遍历
    return 0;
}

广搜

广搜的基本思路：从1号（第一层）顶点开始，先遍历所有与1号相连的顶点（全部入队）再从++head开始，遍历与当前head对应的顶点相连的顶点，直到遍历到底为止
存储基本与深搜无异。

遍历：

#include <stdio.h>
//cur是当前所在的顶点编号
//二维数组e是存储整个图的矩阵
//book数组是存储顶点是否访问过的数组
//访问过为1，没访问过为0

int main()
{
    int i, j, n, m, a, b, cur, book[101] = { 0 }, e[101][101];
    int que[10001], head, tail;
    scanf("%d %d", &n, &m);
    //初始化二维矩阵
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
            {
                e[i][j] = 0;
            }
            else
            {
                e[i][j] = 99999999;//设99999999为正无穷
            }
        }
    }
    //读入顶点的边
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1;//无向图，所以需要将e[b][a]也赋值为1
    }
    //队列初始化
    head = 1;
    tail = 1;
    //从1号顶点出发，将1号顶点加入队列
    que[tail] = 1;
    tail++;
    book[1] = 1;//标记1号顶点已访问
    //当队列不为空的时候循环
    while (head < tail && tail <= n)
    {
        cur = que[head];//当前正在访问的顶点编号
        for (i = 1; i <= n; i++)//从1~n依次尝试
        {
            //判断从顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
            if (e[cur][i] == 1 && book[i] == 0)
            {
                //如果从顶点cur到顶点i有边，而且顶点i没有被访问过，则将顶点i入队
                que[tail] = i;
                tail++;
                book[i] = 1;
            }
            //如果tail大于n，表明所有顶点都已经被访问过
            if (tail > n)
            {
                break;
            }
        }
        head++;//千万不要忘记当一个顶点扩展完之后，要将父亲出队（head++），然后才能继续往下扩展
    }
    for (int i = 1; i < tail; i++)
    {
        printf("%d ", que[i]);
    }
    return 0;
}