数据结构——图的遍历

第一种方式：广度优先搜索

一、介绍

在图论中，广度优先搜索（Breadth-First Search，简称BFS）是一种用于图的遍历的算法。它从图的某个顶点开始，逐层遍历图的节点，直到遍历完所有可达节点。广度优先搜索使用队列来实现，保证了节点的访问顺序是按照层级逐个访问的。

二、算法步骤

广度优先搜索的算法步骤如下：

1. 创建一个队列，用于存储待访问的节点。
2. 将起始节点放入队列中。
3. 创建一个集合，用于存储已访问的节点。
4. 当队列不为空时，执行以下步骤：
   • 从队列中取出一个节点作为当前节点。
   • 将当前节点标记为已访问。
   • 将当前节点的所有未访问邻居节点加入队列。
5. 重复步骤4，直到队列为空。

三、代码实现

下面是使用Python实现广度优先搜索的代码示例：

from collections import deque

def bfs(graph, start):
    visited = set()  # 存储已访问的节点
    queue = deque([start])  # 创建队列，并将起始节点放入队列中
    visited.add(start)  # 标记起始节点为已访问

    while queue:
        node = queue.popleft()  # 从队列中取出一个节点作为当前节点
        print(node)  # 输出当前节点

        for neighbor in graph[node]:  # 遍历当前节点的邻居节点
            if neighbor not in visited:  # 如果邻居节点未访问过
                queue.append(neighbor)  # 将邻居节点加入队列
                visited.add(neighbor)  # 标记邻居节点为已访问

# 创建一个图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 从节点A开始进行广度优先搜索
bfs(graph, 'A')
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

四、应用场景

广度优先搜索在图的遍历中有广泛的应用，常见的应用场景包括：

• 寻找图中两个节点之间的最短路径。
• 在无权图中寻找从起点到终点的路径。
• 在迷宫中寻找从起点到终点的最短路径。

五、总结

广度优先搜索是一种图的遍历算法，通过逐层遍历图的节点，保证了节点的访问顺序是按照层级逐个访问的。它使用队列来实现，可以应用于寻找最短路径等问题。

希望本文对你理解广度优先搜索有所帮助！

第二种方式：深度优先搜索

一、介绍

在图论中，深度优先搜索（Depth-First Search，简称DFS）是一种用于图的遍历的算法。它从图的某个顶点开始，沿着一条路径一直走到底，直到不能再继续下去，然后回退到上一个节点，继续探索其他路径，直到遍历完所有可达节点。深度优先搜索使用栈来实现，保证了节点的访问顺序是按照深度逐个访问的。

二、算法步骤

深度优先搜索的算法步骤如下：

1. 创建一个栈，用于存储待访问的节点。
2. 将起始节点放入栈中。
3. 创建一个集合，用于存储已访问的节点。
4. 当栈不为空时，执行以下步骤：
   • 从栈中取出一个节点作为当前节点。
   • 将当前节点标记为已访问。
   • 将当前节点的所有未访问邻居节点加入栈。
5. 重复步骤4，直到栈为空。

三、代码实现

下面是使用Python实现深度优先搜索的代码示例：

def dfs(graph, start):
    visited = set()  # 存储已访问的节点
    stack = [start]  # 创建栈，并将起始节点放入栈中

    while stack:
        node = stack.pop()  # 从栈中取出一个节点作为当前节点

        if node not in visited:  # 如果当前节点未访问过
            visited.add(node)  # 标记当前节点为已访问
            print(node)  # 输出当前节点

            for neighbor in graph[node]:  # 遍历当前节点的邻居节点
                if neighbor not in visited:  # 如果邻居节点未访问过
                    stack.append(neighbor)  # 将邻居节点加入栈

# 创建一个图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 从节点A开始进行深度优先搜索
dfs(graph, 'A')
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

四、应用场景

深度优先搜索在图的遍历中有广泛的应用，常见的应用场景包括：

• 寻找图中两个节点之间的路径。
• 在有权图中寻找从起点到终点的路径。
• 在迷宫中寻找从起点到终点的路径。

五、总结

深度优先搜索是一种图的遍历算法，通过沿着一条路径一直走到底，然后回退到上一个节点，继续探索其他路径，直到遍历完所有可达节点。它使用栈来实现，可以应用于寻找路径等问题。

希望本文对你理解深度优先搜索有所帮助！

邻接矩阵存储结构

一、概述

邻接矩阵是一种常用的图的存储结构，它使用二维数组来表示图中节点之间的边的关系。在邻接矩阵中，数组的大小为n×n，n表示图中节点的个数，矩阵中的元素a[i][j]表示节点i和节点j之间的边的关系，通常可以用0和1来表示，0表示没有边，1表示有边。对于无向图来说，邻接矩阵是对称的，即a[i][j]等于a[j][i]；对于有向图来说，邻接矩阵不一定是对称的。

二、存储结构

邻接矩阵存储结构可以使用二维数组来表示，其中数组的大小为n×n，n表示图中节点的个数。邻接矩阵中的元素a[i][j]表示节点i和节点j之间的边的关系，通常可以用0和1来表示，0表示没有边，1表示有边。对于无向图来说，邻接矩阵是对称的，即a[i][j]等于a[j][i]；对于有向图来说，邻接矩阵不一定是对称的。

三、图的遍历

在图的遍历中，可以使用邻接矩阵存储结构来实现深度优先搜索（DFS）和广度优先搜索（BFS）。下面分别介绍这两种遍历算法的实现。

1. 深度优先搜索（DFS）

深度优先搜索使用栈来实现，保证了节点的访问顺序是按照深度逐个访问的。

def dfs(graph, start):
    visited = set()  # 存储已访问的节点
    stack = [start]  # 创建栈，并将起始节点放入栈中

    while stack:
        node = stack.pop()  # 从栈中取出一个节点作为当前节点

        if node not in visited:  # 如果当前节点未访问过
            visited.add(node)  # 标记当前节点为已访问
            print(node)  # 输出当前节点

            for i in range(len(graph[node])):  # 遍历当前节点的邻接节点
                if graph[node][i] == 1 and i not in visited:  # 如果邻接节点存在且未访问过
                    stack.append(i)  # 将邻接节点加入栈

# 创建一个图的邻接矩阵表示
graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]
]

# 从节点0开始进行深度优先搜索
dfs(graph, 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

2. 广度优先搜索（BFS）

广度优先搜索使用队列来实现，保证了节点的访问顺序是按照层级逐个访问的。

from collections import deque

def bfs(graph, start):
    visited = set()  # 存储已访问的节点
    queue = deque([start])  # 创建队列，并将起始节点放入队列中

    while queue:
        node = queue.popleft()  # 从队列中取出一个节点作为当前节点

        if node not in visited:  # 如果当前节点未访问过
            visited.add(node)  # 标记当前节点为已访问
            print(node)  # 输出当前节点

            for i in range(len(graph[node])):  # 遍历当前节点的邻接节点
                if graph[node][i] == 1 and i not in visited:  # 如果邻接节点存在且未访问过
                    queue.append(i)  # 将邻接节点加入队列

# 创建一个图的邻接矩阵表示
graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]
]

# 从节点0开始进行广度优先搜索
bfs(graph, 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

四、应用场景

邻接矩阵存储结构在图的遍历中有广泛的应用，常见的应用场景包括：

• 网络拓扑结构分析
• 社交网络分析
• 路径规划和最短路径问题求解

五、总结

邻接矩阵存储结构是一种常用的图的存储结构，它可以方便地进行图的遍历操作。在实际应用中，需要根据具体的场景选择合适的遍历算法来解决问题。