图论基础概念：构建知识框架

图论作为计算机科学的核心分支，其数据结构由顶点（Vertex）和边（Edge）构成。根据边的特性，图可分为无向图（Undirected Graph）和有向图（Directed Graph），前者边无方向性（如社交网络中的好友关系），后者边具有方向（如网页链接结构）。加权图（Weighted Graph）通过边权重表示距离或成本，在路径规划中应用广泛。

图的存储方式直接影响算法效率。邻接矩阵使用二维数组存储边信息，时间复杂度为O(1)的边查询，但空间复杂度达O(V²)，适合稠密图。邻接表通过链表或数组存储顶点邻接关系，空间复杂度优化至O(V+E)，成为稀疏图的首选。例如，LeetCode 733题（图像渲染）可通过邻接表实现区域填充算法。

图的遍历是算法设计的基础。深度优先搜索（DFS）采用递归或栈实现，适用于连通性检测和拓扑排序。广度优先搜索（BFS）通过队列实现，在无权图最短路径求解中表现优异，如LeetCode 133题（克隆图）的节点复制。

核心算法：破解高频考点

最短路径算法：Dijkstra与Floyd-Warshall

Dijkstra算法通过贪心策略解决单源最短路径问题，适用于非负权图。其核心步骤包括：初始化距离数组、维护优先队列、松弛操作更新最短路径。时间复杂度为O((V+E)logV)，在导航系统路径规划中广泛应用。例如，LeetCode 743题（网络延迟时间）要求计算从源点到所有节点的最短时间，Dijkstra算法通过优先队列优化可高效解决。

Floyd-Warshall算法采用动态规划思想，解决所有节点对的最短路径问题。通过三重循环更新距离矩阵，时间复杂度为O(V³)，适用于负权边（无负权环）场景。在金融套利检测中，该算法可识别货币兑换的最优路径。

最小生成树：Prim与Kruskal

Prim算法从任意顶点出发，逐步扩展生成树，每次选择连接生成树与非生成树顶点的最小权边。使用优先队列优化后，时间复杂度为O(ElogV)，适用于稠密图。Kruskal算法则按边权排序，通过并查集（Union-Find）检测环路，时间复杂度为O(ElogE)，在稀疏图中表现更优。例如，LeetCode 1584题（连接所有点的最小费用）可通过Kruskal算法求解。

拓扑排序：检测有向无环图

拓扑排序通过DFS或Kahn算法（入度统计）实现，用于任务调度和课程安排。Kahn算法步骤包括：统计入度、初始化队列、处理入度为0的节点、更新邻接节点入度。若最终排序节点数不等于总节点数，则说明图中存在环。LeetCode 207题（课程表）要求判断课程安排是否可行，拓扑排序可高效检测依赖关系。

经典算法题解析：实战提升能力

LeetCode 210题：课程表II

本题要求返回课程安排的拓扑序列。解法步骤如下：

构建邻接表存储课程依赖关系
统计每门课程的入度
初始化队列，将入度为0的课程入队
依次处理队列中的课程，减少邻接课程的入度
若邻接课程入度为0，则入队
最终检查是否所有课程均被处理

from collections import deque
def findOrder(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for course, pre in prerequisites:
        adj[pre].append(course)
        in_degree[course] += 1
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return result if len(result) == numCourses else []

LeetCode 787题：K站中转内最便宜的航班

本题要求在限定中转次数内找到最便宜航班。解法结合BFS与动态规划：

构建邻接表存储航班信息
初始化距离数组，记录中转k次的最小成本
逐层扩展，更新距离数组
最终返回最小成本或-1

import heapq
def findCheapestPrice(n, flights, src, dst, k):
    adj = [[] for _ in range(n)]
    for u, v, price in flights:
        adj[u].append((v, price))
    heap = [(0, src, k + 1)]
    visited = {}
    while heap:
        cost, node, stops = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops > 0:
            for neighbor, price in adj[node]:
                if (neighbor, stops - 1) not in visited or cost + price < visited[(neighbor, stops - 1)]:
                    visited[(neighbor, stops - 1)] = cost + price
                    heapq.heappush(heap, (cost + price, neighbor, stops - 1))
    return -1

优化策略与注意事项

算法选择：根据问题特性选择算法。如单源最短路径优先Dijkstra，所有节点对最短路径选择Floyd-Warshall。
数据结构优化：优先队列可加速Dijkstra算法，并查集可高效实现Kruskal算法。
边界条件处理：注意负权边、负权环、图不连通等特殊情况。
空间复杂度控制：邻接表在稀疏图中更节省空间，邻接矩阵适合稠密图。

总结与展望

图论算法在路径规划、网络优化、任务调度等领域具有广泛应用。掌握DFS/BFS遍历、最短路径、最小生成树、拓扑排序等核心算法，结合LeetCode经典题目练习，可显著提升算法设计与实现能力。未来，随着图神经网络（GNN）的发展，图论算法将在社交网络分析、推荐系统等领域发挥更大作用。开发者应持续关注算法优化与工程实现，构建高效、可扩展的图处理系统。

直击图论核心：高频考点与经典算法题深度解析