← 数据结构主页数据结构 · 图的概念
近年来 408 数据结构真题中，与「图的概念」相关的题目共 12 道，累计 62 分。
邻接表求入度：需遍历所有边链表，复杂度 O(|E|)
邻接表图的概念
有向图路径与字符串集：无环图最长路径最多 n-1 条边，不存在长度为 n 的串
图的概念
图的性质：各顶点度≥2 的无向图必有回路（握手定理推导）
图的概念
邻接多重表：根据邻接多重表存储结构求无向图顶点 b 与 d 的度
十字链表图的概念
算法设计：判断有向图是否存在唯一的拓扑序列（每次入度为 0 的顶点唯一）
拓扑排序图的概念
算法设计：用邻接矩阵求有向图中出度大于入度的 K 顶点
邻接矩阵图的概念
图的连通性：无向图至少需要 |V|-1 条边才可能连通
图的概念
图论算法：判断无向连通图是否存在欧拉路径（奇度顶点个数≤2）
邻接矩阵图的概念
DAG 表示表达式：消除公共子表达式减少顶点数
图的概念
邻接矩阵与路径：A² 中元素表示长度为 2 的路径条数，B^m 的一般规律
邻接矩阵图的概念
最短路径问题：证明贪心策略"每次选最近顶点"不保证全局最优
Dijkstra图的概念