|
第四部分 图 复习策略图的概念比较多值得同学们认真研究下没有基本概念的基础就相当于没有单词的英语是很难把知识掌握清楚的对于图是承接着树而衍生出来的在实际应用中图更为广泛所有问题都是化未知为已知解决图的问题很多时候是借助树和二叉树来实现的同学们应注意树二叉树和图之间的对应关系考研复习中图无疑是另一个重点此部分出大题的可能性很高年真题的第一道既是如此此部分同学们要重视由人名来命名的算法这类算法是为了纪念作者而命名的可见其经典性这类算法也相当有难度考试时仅仅只会就此算法稍加改动或应用算法的思想来命题 年真题分值比例选择题道（分）综合题道（分）% （一）图的基本概念 图是由顶点的有穷非空集合和顶点之间边的集合组成通常表示为G=（VE）其中G表示一个图V是图G中顶点的集合E是图G中顶点之间边的集合 若顶点vi和vj之间的边没有方向则称这条边为无向边表示为（vivj） 如果图的任意两个顶点之间的边都是无向边则称该图为无向图 若从顶点vi到vj的边有方向则称这条边为有向边表示为<vivj> 如果图的任意两个顶点之间的边都是有向边则称该图为有向图 简单图【释无环无回弧】在图中若不存在顶点到其自身的边且同一条边不重复出现 邻接依附【释挨着】 无向图中对于任意两个顶点vi和顶点vj若存在边（vivj）则称顶点vi和顶点vj互为邻接点同时称边（vivj）依附于顶点vi和顶点vj 有向图中对于任意两个顶点vi和顶点vj若存在弧<vivj>则称顶点vi邻接到顶点vj顶点vj邻接自顶点vi同时称弧<vivj>依附于顶点vi和顶点vj 返回《数据结构》考研复习精编 [] [] [] [] [] [] [] [] [] [] |
