Python数据结构高级：图的表示与遍历

一、图的基本概念

1.1 图的定义与分类

图（Graph）是由顶点（Vertex）集合和边（Edge）集合组成的数据结构，形式化表示为 G = (V, E)

主要分类：

无向图 vs 有向图

# 无向图示例：A-B-C
# 有向图示例：A→B→C

权重图 vs 非权重图

# 权重图示例：A-(5)-B-(3)-C
# 非权重图示例：A-B-C

1.2 典型应用场景

社交网络：用户为顶点，关注关系为边
交通网络：城市为顶点，路线为带权边
知识图谱：实体为顶点，关系为边
推荐系统：用户-商品交互关系建模

二、图的表示方法

2.1 邻接矩阵

使用二维数组表示顶点间的连接关系

class AdjMatrixGraph:
    def __init__(self, vertices):
        self.size = len(vertices)
        self.vertices = vertices
        self.matrix = [[0]*self.size for _ in range(self.size)]
        self.index_map = {v:i for i,v in enumerate(vertices)}

    def add_edge(self, u, v, weight=1):
        i = self.index_map[u]
        j = self.index_map[v]
        self.matrix[i][j] = weight
        # 若是无向图需添加反向
        # self.matrix[j][i] = weight

时间复杂度分析：

查询相邻节点：O(1)
遍历所有边：O(V²)
空间复杂度：O(V²)

2.2 邻接表

使用字典+链表存储连接关系（更节省空间）

from collections import defaultdict

class Graph:
    def __init__(self):
        self.adj_list = defaultdict(list)
    
    def add_edge(self, u, v, weight=None):
        self.adj_list[u].append((v, weight))
        # 若是无向图需添加反向
        # self.adj_list[v].append((u, weight))

时间复杂度分析：

查询相邻节点：O(1)平均
遍历所有边：O(V+E)
空间复杂度：O(V+E)

三、图的遍历算法

3.1 深度优先搜索（DFS）

def dfs(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            # 逆序压栈保证顺序一致性
            for neighbor in reversed(graph.adj_list[vertex]):
                if neighbor[0] not in visited:
                    stack.append(neighbor[0])

应用场景：

拓扑排序
检测环路
寻找连通分量

3.2 广度优先搜索（BFS）

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            for neighbor in graph.adj_list[vertex]:
                if neighbor[0] not in visited:
                    queue.append(neighbor[0])

应用场景：

最短路径查找（未加权图）
社交网络的好友推荐
网页爬虫的URL遍历

四、完整代码示例

class Graph:
    def __init__(self):
        self.adj_list = defaultdict(list)
    
    def add_edge(self, u, v, weight=None):
        self.adj_list[u].append((v, weight))
    
    def dfs(self, start):
        visited = set()
        self._dfs_recursive(start, visited)
    
    def _dfs_recursive(self, vertex, visited):
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            for neighbor in self.adj_list[vertex]:
                self._dfs_recursive(neighbor[0], visited)
    
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        
        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                print(vertex, end=' ')
                visited.add(vertex)
                for neighbor in self.adj_list[vertex]:
                    if neighbor[0] not in visited:
                        queue.append(neighbor[0])

# 使用示例
if __name__ == "__main__":
    g = Graph()
    g.add_edge('A', 'B')
    g.add_edge('A', 'C')
    g.add_edge('B', 'D')
    g.add_edge('C', 'E')
    g.add_edge('D', 'E')
    
    print("DFS遍历结果：")
    g.dfs('A')  # 输出：A B D E C 
    
    print("\nBFS遍历结果：")
    g.bfs('A')  # 输出：A B C D E

五、每日挑战：路径存在性判断

def has_path(graph, start, end):
    visited = set()
    stack = [start]
    
    while stack:
        current = stack.pop()
        if current == end:
            return True
        if current not in visited:
            visited.add(current)
            for neighbor in graph.adj_list[current]:
                if neighbor[0] not in visited:
                    stack.append(neighbor[0])
    return False

# 测试用例
g = Graph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')

print(has_path(g, 'A', 'D'))  # 输出：True
print(has_path(g, 'D', 'A'))  # 输出：False

算法选择建议：

最短路径问题 → BFS
拓扑排序 → DFS
存在性判断 → 两者均可

六、扩展应用

加权图的最短路径（Dijkstra算法）
最小生成树（Prim/Kruskal算法）
社交网络分析（使用NetworkX库）
图数据库应用（Neo4j的Python接口）

# Dijkstra算法示例
import heapq

def dijkstra(graph, start):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        current_dist, current_vertex = heapq.heappop(heap)
        
        if current_dist > distances[current_vertex]:
            continue
            
        for neighbor, weight in graph[current_vertex]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    
    return distances