软件设计师图考点

　　软件设计师图考点有哪些?为了方便考生及时有效的备考，课课家小编为大家精心整理了软考中级软件设计师图考试知识点，供大家参考和学习。如想获取更多计算机软件水平考试的模拟题及备考资料，请关注课课家网站的更新。

　　【考法分析】

　　1、本知识点的主要考查形式有：判断给出的关于图的概念、特性的描述是否正确;或根据图的邻接矩阵、邻接表，指出相关图、图的特点、图的遍历;根据图示，指出遍历顺序、拓扑序列。

　　【要点分析】

　　1、完全图

　　在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图(complete graph)。

　　在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图。

　　2、图的邻接矩阵表示：用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素Rij定义为：

　　3、图的邻接表表示：首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。

　　4、图的遍历：

　　5、图的拓扑排序：拓扑排序是将AOV网中的所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网点中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在顶点Vj之前。

　　6、最小生成树，是该图的极小联通子图。普里姆算法构造最小生成树过程：

　　(1)去掉所有的连线，将所有顶点放到集合R1中，作为未处理结点集合，另新建集合R2存放已处理结点。

　　(2)选择入度为0的顶点作为起点，放到集合R2中;

　　(3)选择R2到R1最短(代价最小)的路径，同时将对应顶点从R1删除并放到集合R2中。

　　(4)重复步骤3直到R1为空。

　　【备考点拨】

　　1、掌握图的相关概念;

　　2、掌握图的存储;

　　3、掌握图的遍历;

　　4、掌握图的拓扑序列求取;

　　5、了解最小生成树的构造。

      课课家教育专注软考培训10年以上，一直坚持自主研发，将丰富的软考培训经验有效融入教程研发过程，自成体系的软考视频教程、软考培训教材和软考在线题库，使考生的学习更具系统性，辅导更具针对性。想要报考2020年软考的考生现在就可以开始备考了，报名课课家软考各科目考试赠送：辅导教材、历年真题、考前冲剌资料、在线模拟测试题库、老师专属答疑指导等，以保障学员顺利通过考试。

　　>>>>>>点击进入软考报名专题