哈希表

数据结构教程 · 第 7 章 · 7 次浏览

图由顶点和边组成，表达"关系"：社交网络（谁认识谁）、地图（城市间路径）、依赖关系（谁先编译）。

存储方式

邻接矩阵：二维数组，查两点是否相连 O(1)，费内存
邻接表：每个顶点存邻居列表，省内存，常用

遍历

深度优先 DFS（递归/栈，一条路走到底）和广度优先 BFS（队列，逐层扩散，最短路径）。

代码示例

from collections import deque

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

# BFS 广度优先（找最短路径）
def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        print(node, end=" ")
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)

# DFS 深度优先
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)

print("BFS:", end=" ")
bfs(graph, "A")           # A B C D E
print("\nDFS:", end=" ")
dfs(graph, "A")           # A B D C E

📚 Python 语法速查

常用条目速查，完整版见对应教程章节。可复制代码到在线运行中测试。

写法 / 语法	作用
`print("hello")`	输出到控制台
`name = "张三"`	变量赋值（无需声明类型）
`if x > 0: ...`	条件判断（注意冒号和缩进）
`for i in range(10): ...`	循环（缩进是语法的一部分）
`while x < 10: ...`	条件循环
`def fn(a, b): return a + b`	定义函数
`class Person: ...`	定义类
`list = [1, 2, 3]`	列表（可改）
`tuple = (1, 2)`	元组（不可改）
`dict = {"key": "value"}`	字典（键值对）
`set = {1, 2, 3}`	集合（去重）
`len(obj)`	取长度
`str(x) / int(x) / float(x)`	类型转换
`s.split(",")`	字符串按分隔符拆分
`" ".join(list)`	列表拼接成字符串
`import os`	导入模块
`from math import sqrt`	从模块导入指定函数
`try: ... except Exception as e: ...`	异常捕获
`with open("a.txt", "r") as f: ...`	文件读取（自动关闭）
`f"你好 {name}"`	f-string 格式化
`lambda x: x * 2`	匿名函数
`list(map(fn, arr))`	函数式处理列表
`range(start, stop, step)`	生成数字序列
`if __name__ == "__main__":`	主入口判断
`pip install 包名`	安装第三方包（命令行）