← 数据结构主页数据结构 · 图基本概念
近年来 408 数据结构真题中，与「图基本概念」相关的题目共 17 道，累计 80 分。
邻接表求入度：需遍历所有边链表，复杂度 O(|E|)
图基本概念邻接表
有向图路径与字符串集：无环图最长路径最多 n-1 条边，不存在长度为 n 的串
图基本概念
图的性质：各顶点度≥2 的无向图必有回路（握手定理推导）
图基本概念广度优先搜索拓扑排序
算法设计：判断有向图是否存在唯一的拓扑序列（每次入度为 0 的顶点唯一）
拓扑排序图基本概念
算法设计：用邻接矩阵求有向图中出度大于入度的 K 顶点
邻接矩阵图基本概念
图的连通性：无向图至少需要 |V|-1 条边才可能连通
图基本概念
拓扑排序：有向无环图中不同拓扑排序序列的数量
图基本概念拓扑排序
图论算法：判断无向连通图是否存在欧拉路径（奇度顶点个数≤2）
邻接矩阵图基本概念
Dijkstra 最短路径：逐步求解过程中顶点的选取顺序
图基本概念Dijkstra 最短路径
邻接矩阵与路径：A² 中元素表示长度为 2 的路径条数，B^m 的一般规律
邻接矩阵图基本概念
拓扑排序：删除入度为 0 的结点得到合法的拓扑序列
图基本概念
> **总思路**：题面看似考网络，其实考的是**图的抽象 + 邻接表设计 + Dijkstra**——把 4 个路由器和 4 个直连子网当作图的顶点，链路当作
图基本概念邻接表Dijkstra 最短路径
有向图邻接矩阵：根据邻接矩阵计算顶点的入度和出度
图基本概念
图的 BFS 遍历：判断哪个序列是合法的广度优先序列
图基本概念广度优先搜索
无向图连通性：n 个顶点的无向图保证连通所需最少边数
图基本概念
最短路径问题：证明贪心策略"每次选最近顶点"不保证全局最优
Dijkstra 最短路径图基本概念