Python算法揭秘：图的表示与遍历，解锁数据之美

测试开发囤货

发布于 2023-08-08 09:39:07

2700

发布于 2023-08-08 09:39:07

文章被收录于专栏：测试开发囤货

Python算法揭秘：图的表示与遍历，解锁数据之美！

图的表示与遍历

图是由一组节点和连接这些节点的边组成的数据结构。图可以用于表示现实世界中的各种关系和网络。

图的基本概念和表示方法

图由节点（顶点）和边组成。节点表示图中的对象或实体，边表示节点之间的关系或连接。

图可以分为有向图和无向图。有向图中的边是有方向的，表示节点之间的单向关系。无向图中的边是无方向的，表示节点之间的双向关系。

图可以使用邻接矩阵或邻接表来表示。邻接矩阵是一个二维数组，其中的元素表示节点之间是否存在边。邻接表是一个由链表或数组构成的列表，其中的每个元素表示一个节点及其相邻节点的列表。

深度优先遍历和广度优先遍历的原理和实现步骤

深度优先遍历（Depth-First Search，DFS）和广度优先遍历（Breadth-First Search，BFS）是图的两种常见遍历方式。

深度优先遍历（DFS）：从起始节点开始，沿着一条路径一直遍历到最后一个节点，然后回溯并探索其他路径。DFS使用栈来实现遍历过程。
广度优先遍历（BFS）：从起始节点开始，先遍历与起始节点直接相邻的节点，然后逐层遍历其他节点。BFS使用队列来实现遍历过程。

示例

用Python编写图的遍历算法示例

下面是用Python编写的深度优先遍历和广度优先遍历的示例：

from collections import deque

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

# 深度优先遍历
def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            stack.extend(graph[node])

# 广度优先遍历
def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            queue.extend(graph[node])

# 测试示例
print("深度优先遍历:")
dfs(graph, 'A')
print("\n广度优先遍历:")
bfs(graph, 'A')

在这个示例中，我们使用邻接表的方式表示图。然后，分别实现了深度优先遍历函数dfs和广度优先遍历函数bfs。