直击考点：图论核心算法与高频题精解

一、图论基础概念：高频考点的基石

图论是计算机科学中研究图（由顶点与边构成的数学结构）的理论，其核心概念是理解图的结构与性质。在编程考试中，图的表示方法（邻接矩阵、邻接表）、图的分类（有向图、无向图、带权图）以及路径与连通性（简单路径、环、强连通分量）是基础中的基础。例如，邻接矩阵通过二维数组存储顶点间关系，适合稠密图；邻接表通过链表或数组存储边的信息，更适合稀疏图。理解这些概念是后续学习算法的前提。

典型应用场景

社交网络分析：用户为顶点，好友关系为边，通过连通性判断用户是否间接关联。
交通网络优化：城市为顶点，道路为边，通过最短路径算法优化导航路线。
任务调度：任务为顶点，依赖关系为边，通过拓扑排序确定执行顺序。

二、经典图论算法：高频考点的核心

1. 深度优先搜索（DFS）与广度优先搜索（BFS）

DFS通过递归或栈实现，适用于遍历或搜索连通分量、检测环；BFS通过队列实现，适用于无权图的最短路径查找。例如，在迷宫问题中，BFS可找到从起点到终点的最短步数路径。

代码示例（BFS找最短路径）：

from collections import deque
def bfs_shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = set()
    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append((neighbor, path + [neighbor]))
    return None

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

Dijkstra算法用于单源最短路径（非负权图），通过优先队列（堆）优化，时间复杂度为O((V+E)logV)；Floyd-Warshall算法用于所有顶点对的最短路径，通过动态规划实现，时间复杂度为O(V³)。例如，在物流网络中，Dijkstra可计算从仓库到各配送点的最短时间。

代码示例（Dijkstra算法）：

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

3. 最小生成树：Prim与Kruskal算法

Prim算法从任意顶点开始，逐步扩展生成树，适合稠密图；Kruskal算法按边权排序后选择不形成环的边，适合稀疏图。例如，在电网设计中，最小生成树可最小化电缆总长度。

代码示例（Kruskal算法）：

def kruskal(graph):
    parent = {node: node for node in graph}
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1
    edges = []
    for node in graph:
        for neighbor, weight in graph[node].items():
            edges.append((weight, node, neighbor))
    edges.sort()
    mst = []
    for weight, u, v in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, weight))
    return mst

三、高频考点与经典算法题解析

1. 拓扑排序（LeetCode 207/210）

拓扑排序用于有向无环图（DAG），判断任务是否可完成或输出执行顺序。核心是通过BFS或DFS计算入度，逐步移除入度为0的顶点。

真题解析：

LeetCode 207（课程表）：判断课程依赖关系是否构成环，若可拓扑排序则返回True。
LeetCode 210（课程表II）：输出拓扑排序结果，若无解则返回空数组。

2. 二分图检测（LeetCode 785）

二分图指顶点可划分为两个集合，且每条边连接不同集合的顶点。通过BFS或DFS染色法检测，若相邻顶点颜色相同则非二分图。

代码示例：

def isBipartite(graph):
    color = {}
    for node in range(len(graph)):
        if node not in color:
            queue = deque([node])
            color[node] = 0
            while queue:
                current = queue.popleft()
                for neighbor in graph[current]:
                    if neighbor in color:
                        if color[neighbor] == color[current]:
                            return False
                    else:
                        color[neighbor] = 1 - color[current]
                        queue.append(neighbor)
    return True

3. 强连通分量（Kosaraju算法）

强连通分量指有向图中最大子图，其中任意两点互相可达。通过两次DFS（原图与转置图）划分，常用于网页排名或社交网络分析。

四、备考建议与实战技巧

理解算法本质：不要死记硬背代码，需掌握算法思想（如Dijkstra的贪心策略、Floyd的动态规划）。
多维度练习：从简单题（如BFS找路径）到复杂题（如强连通分量）逐步提升。
优化时间复杂度：例如，用优先队列优化Dijkstra，用并查集优化Kruskal。
结合实际场景：将算法与社交网络、交通优化等场景结合，加深理解。

五、总结

图论是编程考试中的高频考点，掌握其基础概念、经典算法及典型应用场景是关键。通过系统学习DFS/BFS、最短路径、最小生成树等算法，并结合真题练习，可显著提升解题能力。希望本文的总结与代码示例能为开发者提供实用参考，助力高效备考。