图 Graph：数据结构与算法中的核心抽象

图（Graph）作为非线性数据结构的典型代表，通过顶点（Vertex）和边（Edge）的抽象关系，能够精准建模社交网络、交通系统、知识图谱等复杂场景。本文将从基础定义出发，系统梳理图的存储方式、遍历算法及典型应用场景，为开发者提供完整的理论框架与工程实践指南。

一、图的基础定义与分类

1.1 图的数学表示

图由顶点集 $V$ 和边集 $E$ 构成，记为 $G=(V, E)$。边可分为有向边（Directed Edge）和无向边（Undirected Edge），对应生成有向图（Directed Graph）和无向图（Undirected Graph）。例如，社交网络中用户关系可用无向图表示，而任务依赖关系更适合用有向图建模。

1.2 图的加权特性

当边被赋予权重（Weight）时，图升级为加权图（Weighted Graph）。权重可表示距离、成本或概率等实际意义，例如城市道路网络中的路段长度或网络链路中的延迟值。

1.3 特殊图类型

完全图：任意两顶点间均存在边
二分图：顶点集可划分为两个不相交子集，且所有边均连接不同子集的顶点
强连通图：有向图中任意两顶点互相可达

二、图的存储方式与实现

2.1 邻接矩阵（Adjacency Matrix）

使用二维数组存储顶点间连接关系，时间复杂度为 $O(1)$ 的边查询，但空间复杂度为 $O(|V|^2)$，适合稠密图或需要快速边查询的场景。

class GraphMatrix:
    def __init__(self, vertices):
        self.vertices = vertices
        self.matrix = [[0]*vertices for _ in range(vertices)]
    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        # 无向图需对称设置
        self.matrix[v][u] = weight

2.2 邻接表（Adjacency List）

通过链表或字典存储每个顶点的邻接顶点，空间复杂度为 $O(|V|+|E|)$，适合稀疏图或需要高效遍历的场景。

from collections import defaultdict
class GraphList:
    def __init__(self):
        self.graph = defaultdict(list)
    def add_edge(self, u, v, weight=None):
        self.graph[u].append((v, weight))
        # 无向图需双向添加
        self.graph[v].append((u, weight))

2.3 存储方式对比

特性	邻接矩阵	邻接表
空间复杂度	$O(	V	^2)$	$O(	V	+	E	)$
边查询	$O(1)$	$O(\text{deg}(v))$
遍历效率	全扫描	按需访问
适用场景	稠密图、静态图	稀疏图、动态图

三、图的遍历算法

3.1 深度优先搜索（DFS）

采用递归或栈实现，适用于连通性检测、拓扑排序等场景。时间复杂度为 $O(|V|+|E|)$。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor, _ in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

3.2 广度优先搜索（BFS）

使用队列实现，适合最短路径查找（无权图）和层级遍历。时间复杂度同样为 $O(|V|+|E|)$。

from collections import deque
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor, _ in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

四、经典图算法实现

4.1 最短路径算法

Dijkstra算法：解决单源最短路径问题，要求边权非负，时间复杂度 $O((|V|+|E|)\log|V|)$（优先队列优化后）
```python
import heapq

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


- **Floyd-Warshall算法**：解决所有顶点对最短路径问题，时间复杂度 $O(|V|^3)$，适合小规模稠密图
### 4.2 最小生成树算法
- **Prim算法**：从任意顶点开始，逐步扩展生成树，适合稠密图
- **Kruskal算法**：按边权排序后贪心选择，适合稀疏图
```python
# Kruskal算法示例
def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])
def kruskal(graph):
    result = []
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((u, v, weight))
    edges.sort(key=lambda x: x[2])
    parent = {v: v for v in graph}
    for u, v, weight in edges:
        root_u = find(parent, u)
        root_v = find(parent, v)
        if root_u != root_v:
            result.append((u, v, weight))
            parent[root_v] = root_u
    return result

五、工程实践建议

存储选择：根据图的密度（$|E|/|V|^2$）决定存储方式，稠密图优先邻接矩阵，稀疏图选择邻接表
算法优化：
- 使用优先队列优化Dijkstra算法
- 对大规模图考虑并行化处理（如多线程BFS）
实际应用场景：
- 社交网络分析（社区发现、影响力计算）
- 路径规划（导航系统、物流调度）
- 推荐系统（基于图的协同过滤）

六、性能优化策略

空间压缩：对顶点编号进行连续化处理，减少矩阵存储空间
边排序优化：在Kruskal算法中预先排序边集
路径缓存：对频繁查询的路径结果进行缓存
分布式处理：使用图计算框架（如行业常见技术方案中的分布式图处理系统）处理超大规模图

图数据结构作为复杂系统建模的基础工具，其理论深度与实践价值并存。开发者通过掌握图的存储方式、遍历策略及经典算法，能够高效解决路径优化、资源分配等实际问题。在实际工程中，需结合具体场景选择合适的存储结构与算法变种，并通过性能测试验证优化效果。