软件设计师图算法怎么复习？Dijkstra、拓扑排序和邻接矩阵

软件设计师图算法怎么复习？

图算法题并不都要你手算完整过程，很多时候是在考“这个算法解决什么问题”。Dijkstra、拓扑排序、邻接矩阵这几个点，如果先把适用场景分清，选项会清爽很多。

软件设计师专题软考题库编辑部持续更新

内容整理：软考题库编辑部最近更新：2026-06-01

Dijkstra 抓三个词：单源、最短路径、非负权

Dijkstra 算法适合求非负权图中的单源最短路径。题干如果写“从某一个顶点出发，求到其他各顶点的最短路径”，而且边权没有负数，就很像 Dijkstra 的典型场景。

它不是排序算法，也不是最小生成树算法。很多同学会把 Dijkstra、Prim、Kruskal 混在一起，原因是它们都出现在图这一章。做题时先问：题目到底要最短路径，还是要连接所有顶点的最小代价。

拓扑排序处理的是依赖顺序，不是数字大小顺序。比如课程 A 必须在课程 B 前学，任务 1 必须在任务 2 前完成，这类先后约束就适合用拓扑排序描述。

拓扑排序有一个重要前提：图中不能有环。如果存在循环依赖，就没有合法的线性顺序。题目里出现“有向无环图”或 DAG，基本就是在提醒你这个点。

邻接矩阵用一个 n×n 的矩阵表示顶点之间是否相连或边权是多少，所以空间复杂度通常按顶点数写成 O(n²)。哪怕边很少，矩阵也要留出这些位置。

如果题干强调稀疏图，邻接表往往更省空间；如果题干强调查询两个顶点是否相邻，邻接矩阵通常更直接。这里考的是表示方式的取舍，不只是背一个公式。