9.1 图的定义：顶点、边、有向/无向、权重

图（Graph）是一种非线性数据结构，由顶点（Vertex，也叫节点）和边（Edge）组成。你可以把它想象成一张社交网络——每个人是一个顶点，朋友关系就是边。

图可以分为：

• 无向图：边没有方向，A 和 B 相连，意味着 A 能到 B，B 也能到 A。
• 有向图：边有方向，A → B 不代表 B → A。
• 带权图：每条边有一个数值（权重），比如地图中城市之间的距离。

图的几个关键术语：

• 度（Degree）：一个顶点连接的边数。在有向图中，又分为入度（指向该点的边数）和出度（从该点出发的边数）。
• 路径：从一个顶点到另一个顶点经过的边序列。
• 连通性：无向图中任意两点都有路径，则称图是连通图；有向图中若任意两点都互相可达，则称强连通图。

图在现实中的应用非常广泛：社交网络、导航系统、任务依赖关系（如编译顺序）、推荐系统等，都离不开图。

9.2 邻接表 vs 邻接矩阵存储

图的存储方式主要有两种：邻接矩阵和邻接表。选择哪种，取决于图的“稀疏”程度。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
邻接矩阵表示	matrix[u][v] = weight	用二维数组表示，matrix[i][j] 表示顶点 i 到 j 是否有边（或权重）。适合稠密图，空间复杂度 O(V²)，V 是顶点数。
邻接表表示	adj[u].append((v, weight))	用字典或列表的列表，每个顶点对应一个邻居列表。适合稀疏图，空间复杂度 O(V + E)，E 是边数。

我们来看一个简单的邻接表实现：

# 定义一个图类，使用邻接表存储
class Graph:
    def __init__(self, is_directed=False):
        # 使用字典存储邻接表，键是顶点，值是邻居列表
        self.adj = {}
        # 标记是否为有向图
        self.is_directed = is_directed

    def add_vertex(self, v):
        # 添加顶点，如果不存在则初始化空列表
        if v not in self.adj:
            self.adj[v] = []

    def add_edge(self, u, v, weight=1):
        # 添加边，先确保两个顶点都存在
        self.add_vertex(u)
        self.add_vertex(v)
        # 无向图需要双向添加，有向图只添加一次
        self.adj[u].append((v, weight))
        if not self.is_directed:
            self.adj[v].append((u, weight))

    def get_neighbors(self, v):
        # 获取顶点 v 的所有邻居及权重
        return self.adj.get(v, [])

使用示例：

# 创建一个无向图
g = Graph(is_directed=False)
# 添加边：A-B 权重1，B-C 权重2
g.add_edge('A', 'B', 1)
g.add_edge('B', 'C', 2)

# 获取 A 的邻居
neighbors = g.get_neighbors('A')
print(neighbors)  # 输出: 

# 尝试获取不存在的顶点 D 的邻居
try:
    neighbors_d = g.get_neighbors('D')
    print("D 的邻居:", neighbors_d)
except KeyError as e:
    print("顶点不存在:", e)

注意：邻接表在 Python 中通常用 dict[list[tuple]] 实现，既节省空间又便于遍历。而邻接矩阵虽然查询快（O(1)），但浪费空间，尤其当图很稀疏时。

9.3 深度优先搜索（DFS）：递归与显式栈

深度优先搜索（DFS）就像走迷宫——一条路走到黑，走不通就回退。它可以用递归（隐式调用栈）或显式栈实现。

DFS 的核心思想：

• 从起点开始，访问一个未访问的邻居；
• 对该邻居重复上述过程；
• 直到没有未访问邻居，回溯。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
递归 DFS	dfs_recursive(graph, start, visited)	简洁易写，但可能因递归深度过大导致栈溢出（Python 默认递归限制约1000层）。
显式栈 DFS	dfs_iterative(graph, start)	使用 list 作为栈（append/pop），避免递归限制，更适合大规模图。

递归版 DFS 示例：

def dfs_recursive(graph, start, visited=None):
    # 初始化已访问集合
    if visited is None:
        visited = set()
    # 标记当前节点为已访问
    visited.add(start)
    print(f"访问节点: {start}")
    # 遍历所有邻居
    for neighbor, _ in graph.get_neighbors(start):
        if neighbor not in visited:
            # 递归访问未访问的邻居
            dfs_recursive(graph, neighbor, visited)
    return visited

显式栈版 DFS 示例：

def dfs_iterative(graph, start):
    # 使用集合记录已访问节点
    visited = set()
    # 使用列表作为栈，初始放入起点
    stack = [start]
    
    while stack:
        # 弹出栈顶节点
        node = stack.pop()
        if node not in visited:
            # 标记为已访问并输出
            visited.add(node)
            print(f"访问节点: {node}")
            # 将所有未访问的邻居压入栈（注意顺序会影响遍历顺序）
            for neighbor, _ in graph.get_neighbors(node):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

使用示例：

# 构建一个简单图：A-B-C，A-D
g = Graph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('A', 'D')

print("递归 DFS:")
dfs_recursive(g, 'A')

print("\n显式栈 DFS:")
dfs_iterative(g, 'A')

注意：DFS 不保证最短路径！它只是遍历所有可达节点。如果你需要最短路径，请看 BFS。

9.4 广度优先搜索（BFS）：队列实现与最短路径

广度优先搜索（BFS）像水波扩散——一层一层往外扩展。它使用队列（FIFO）实现，天然适合找无权图中的最短路径。

BFS 的核心思想：

• 从起点开始，先访问所有直接邻居（第1层）；
• 再访问邻居的邻居（第2层）；
• 依此类推，直到遍历完成。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
BFS 遍历	bfs(graph, start)	使用 collections.deque 作为队列，时间复杂度 O(V + E)，能保证首次到达某点的路径是最短的（无权图）。
BFS 求最短路径长度	bfs_shortest_path(graph, start, target)	记录每个节点的距离，一旦找到目标即可返回。

BFS 实现示例：

from collections import deque

def bfs(graph, start):
    # 已访问集合
    visited = set()
    # 队列存储待访问节点
    queue = deque([start])
    visited.add(start)
    
    while queue:
        # 从队列左侧取出节点（FIFO）
        node = queue.popleft()
        print(f"访问节点: {node}")
        # 遍历邻居
        for neighbor, _ in graph.get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

def bfs_shortest_path(graph, start, target):
    # 记录每个节点的距离，起点距离为0
    distance = {start: 0}
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node == target:
            return distance[node]
        for neighbor, _ in graph.get_neighbors(node):
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    # 如果无法到达目标，返回 -1
    return -1

使用示例：

# 构建图：A 连接 B 和 D，B 连接 C
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'D')
g.add_edge('B', 'C')

print("BFS 遍历:")
bfs(g, 'A')

print("\n从 A 到 C 的最短路径长度:")
dist = bfs_shortest_path(g, 'A', 'C')
print(dist)  # 输出: 2 (A->B->C)

注意：BFS 的“最短路径”仅适用于无权图或所有边权重相等的情况。如果边有权重，需要用 Dijkstra 算法。