当前位置:   article > 正文

算法详解——图的深度优先遍历和广度优先遍历

深度优先遍历

一、图结构

  图结构指的是如下图所示的由节点和边组成的数据。

在这里插入图片描述

二、深度优先遍历

2.1 图的遍历

  图的遍历任务指的是从图中某个节点开始,遍历得到图中所有节点的过程。

2.2 深度优先遍历过程

  假设我们从1号节点开始进行深度优先遍历。遍历的步骤如下:首先,我们选择1号顶点作为起始点。从1号顶点开始,我们尝试沿着边访问尚未到达过的顶点。我们发现2号顶点是未到达过的,所以我们移动到2号顶点。现在,以2号顶点为起点,我们继续尝试访问其他未到达过的顶点。这样,我们又到达了4号顶点。接着,以4号顶点为起点,我们尝试访问其他未到达过的顶点。然而,此时我们无法再通过4号顶点的边访问其他未到达过的顶点,所以我们需要回到2号顶点。回到2号顶点后,我们发现沿着2号顶点的边也无法再访问其他未到达过的顶点。因此,我们需要继续回到1号顶点。现在,我们继续检查1号顶点的边,看看是否还有其他未到达过的顶点。这时我们到达了3号顶点,然后以3号顶点为起点继续访问其他未到达过的顶点,最后到达了5号顶点。此时,所有顶点都已经被访问过,遍历结束。遍历的顺序如下图所示:

在这里插入图片描述

2.3 深度优先遍历核心思想

  深度优先遍历的核心思想在于:首先选择一个未被访问过的顶点作为起始点,然后沿着当前顶点的边前进到未被访问过的顶点。当当前顶点没有未访问过的邻居顶点时,则回溯到上一个顶点,继续试探访问其他顶点,直到所有的顶点都被访问过为止。显然,深度优先遍历是沿着图的某一条分支遍历直到末端,然后回溯,再沿着另一条分支进行同样的遍历,直到所有的顶点都被访问过为止。

2.4 深度优先遍历实现

  如何将这一过程用代码实现呢?在讨论代码实现之前,我们需要先解决如何存储一个图的问题。最常用的方法是使用一个二维数组 e e e 来表示,具体如下所示:

在这里插入图片描述

  上图中的二维数组中,第 i i i行第 j j j列表示从顶点 i i i到顶点 j j j是否存在一条边。其中, 1 1 1表示存在边, ∞ ∞ 表示不存在边。我们将自己到自己的路径(即 i i i等于 j j j)设为 0 0 0。这种图的存储方式被称为邻接矩阵存储法。

  注意观察的同学会发现,这个二维数组沿主对角线对称。这是因为上述图是无向图。无向图指的是图的边没有方向性,例如边1-5表示,1号顶点可以到达5号顶点,同时5号顶点也可以到达1号顶点。

  接下来,我们将解决如何使用深度优先搜索来实现图的遍历。

// C 代码

#include <stdio.h>

int book[101], sum, n, e[101][101];

void dfs(int cur) // cur 是当前所在的顶点编号
{
    int i;
    printf("%d ", cur);
    sum++; // 每访问一个顶点,sum就加1
    if (sum == n)
        return; // 所有的顶点都已经访问过则直接退出
    for (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, m, a, b;
    scanf("%d %d", &n, &m);
    // 初始化二维矩阵
    for (i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 999999999; // 我们这里假设99999999为正无穷
        }
    }
    // 读入顶点之间的边
    for (i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1; // 这里是无向图,所以需要将e [b] [a]也赋为1
    }
    // 从1号城市出发
    book[1] = 1; // 标记1号顶点已访问
    dfs(1);      // 从1号顶点开始遍历
    getchar();
    getchar();
    return 0;
  • 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
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
# Python 代码

def dfs(cur):
    global sum
    print(cur, end=" ")
    sum += 1
    if sum == n:
        return
    for i in range(1, n + 1):
        if e[cur][i] == 1 and book[i] == 0:
            book[i] = 1
            dfs(i)

if __name__ == "__main__":
    book = [0] * 101
    sum = 0
    n, m = map(int, input().split())
    e = [[0] * 101 for _ in range(101)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = 999999999  # 我们这里假设99999999为正无穷
    for _ in range(m):
        a, b = map(int, input().split())
        e[a][b] = 1
        e[b][a] = 1  # 这里是无向图,所以需要将e [b] [a]也赋为1
    book[1] = 1
    dfs(1)

  • 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

  在上面的代码中变量cur存储的是当前正在遍历的顶点,二维数组e存储的就是图的边(邻接矩阵),数组book用来记录哪些顶点已经访问过,变量sum用来记录已经访问过多少个顶点,变量n存储的是图的顶点的总个数。完整代码如下。

三、广度优先遍历

3.1 广度优先遍历过程

  广度优先遍历结果如下图所示:
在这里插入图片描述

  使用广度优先遍历这个图的过程如下:首先选择一个未被访问过的顶点作为起始顶点,例如以1号顶点为起点。将1号顶点放入队列中,然后将与1号顶点相邻的未访问过的顶点,即2号、3号和5号顶点依次放入队列中。如下图所示:

在这里插入图片描述

  接下来,将2号顶点相邻的未访问过的顶点4号顶点放入队列中。到此,所有顶点都被访问过,遍历结束。如下图所示:

在这里插入图片描述

3.2 广度优先遍历核心思想

  广度优先遍历的主要思想是:首先选择一个未被访问过的顶点作为起始顶点,然后访问其所有相邻的顶点。接着,对于每个相邻的顶点,再访问它们相邻的未被访问过的顶点,直到所有顶点都被访问过,遍历结束。

3.3 广度优先遍历实现

// C 代码

#include <stdio.h>

int main() {
    int i, j, n, m, a, b, cur, e[101][101], book[101] = {0}, que[10001], head, tail;

    scanf("%d %d", &n, &m);

    // 初始化二维矩阵
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999; // 我们这里假设99999999为正无穷
        }
    }

    // 读入顶点之间的边
    for (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号顶点已访问1

    // 当队列不为空的时候循环
    while (head < tail) {
        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; // 标记顶点i已访问
            }
            // 如果tail大于n,则表明所有顶点都已经被访问过
            if (tail > n)
                break;
        }
        head++; // 当一个顶点扩展结束后,head++,然后才能继续往下扩展
    }

    for (i = 1; i < tail; i++)
        printf("%d ", que[i]);

    return 0;
}
  • 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
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
# Python 代码

def main():
    n, m = map(int, input().split())
    e = [[0] * 101 for _ in range(101)]
    book = [0] * 101
    que = [0] * 10001
    head = tail = 1

    # 初始化二维矩阵
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = 99999999  # 我们这里假设99999999为正无穷

    # 读入顶点之间的边
    for _ in range(m):
        a, b = map(int, input().split())
        e[a][b] = 1
        e[b][a] = 1  # 这里是无向图,所以需要将e[b][a]也赋值为1

    # 从1号顶点出发,将1号顶点加入队列
    que[tail] = 1
    tail += 1
    book[1] = 1  # 标记1号顶点已访问

    # 当队列不为空的时候循环
    while head < tail:
        cur = que[head]  # 当前正在访问的顶点编号
        for i in range(1, n + 1):  # 从1~n依次尝试
            # 判断从顶点cur到顶点i是否有边,并判断顶点i是否已经访问过
            if e[cur][i] == 1 and book[i] == 0:
                # 如果从顶点cur到顶点i有边,并且顶点i没有被访问过,则将顶点i入队
                que[tail] = i
                tail += 1
                book[i] = 1  # 标记顶点i已访问
            # 如果tail大于n,则表明所有顶点都已经被访问过
            if tail > n:
                break
        head += 1  # 当一个顶点扩展结束后,head++,然后才能继续往下扩展

    for i in range(1, tail):
        print(que[i], end=" ")

if __name__ == "__main__":
    main()
  • 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
  • 44
  • 45
  • 46
  • 47
  • 48

参考文献

[1]啊哈磊. 2014《啊哈!算法》, 人民邮电出版社

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号