1. 图论基础从零理解数据结构第一次接触图论时我完全被各种术语搞晕了。直到在头歌实训平台反复练习后才发现图论其实就像我们日常生活中的社交网络。想象一下微信好友关系每个人是一个顶点好友关系就是边这样理解图就简单多了。图的阶指的是顶点数量就像班级里有30个同学。度则是某个顶点的连接数好比统计某人的微信好友数量。这里有个有趣公式所有顶点度数之和等于边数的两倍。比如5个顶点8条边的图度数和就是168×2。这个规律在解题时特别有用我经常用它快速验证答案。无向完全图是所有顶点都互相连接的图。计算边数有固定公式n(n-1)/2。5阶无向完全图就是5×4÷210条边。记得第一次做题时我总忘记除以2结果把完全图算成了20条边闹了不少笑话。2. 图的矩阵表示用代码说话在头歌实训做关联矩阵题目时我踩过一个大坑。题目要求用Python的sympy库输出矩阵但平台对格式要求极其严格——连空格和换行都要完全匹配。后来我发现用三重引号字符串可以完美保持格式print(⎡1 0 0 1 0⎤ ⎢ ⎥ ⎢1 1 0 0 1⎥ ⎢ ⎥ ⎢0 1 1 0 0⎥ ⎢ ⎥ ⎣0 0 1 1 1⎦)邻接矩阵和关联矩阵是两种核心表示方法。邻接矩阵记录顶点间的直接连接就像地铁站之间的直达关系表。关联矩阵则记录顶点与边的归属关系更适合处理复杂网络。在判断两个图是否相等时邻接矩阵比关联矩阵更方便因为可以直接用矩阵相等来判断。3. Dijkstra算法实战寻找最优路径第一次实现Dijkstra算法时我被那个∞的表示难住了。后来发现用足够大的数代替就行比如99999。算法核心就像快递员派件每次从仓库起点出发选择当前最短的路线送货并更新周边站点的最短距离。在头歌平台的题目中需要输出两个列表花费列表和前驱节点列表。这里有个易错点起点到自己的花费是0前驱节点要用-1表示。我的调试技巧是先用简单图手动计算预期结果比如下面这个4节点图graph [ [(1,2),(2,5)], # 节点0 [(2,1),(3,4)], # 节点1 [(3,3)], # 节点2 [] # 节点3 ]4. 调试技巧与性能优化在头歌平台提交代码时我总结出三个避坑法则输入输出严格匹配平台测试是字符串完全比对多一个空格都不行边界条件测试空图、单节点图、不连通图都要考虑变量命名清晰costs、parents比c、p更易维护对于大规模图可以用优先队列优化Dijkstra算法。Python的heapq模块就很适合import heapq def dijkstra_heap(graph, start): heap [(0, start)] costs [float(inf)] * len(graph) costs[start] 0 while heap: current_cost, u heapq.heappop(heap) if current_cost costs[u]: continue for v, weight in graph[u]: if costs[v] costs[u] weight: costs[v] costs[u] weight heapq.heappush(heap, (costs[v], v)) return costs实际项目中我更喜欢用networkx库处理复杂图论问题。但在学习阶段手动实现算法更能加深理解。记得某次调试时因为把visited列表放在更新costs之前导致结果错误花了两个小时才找到这个bug。