下载安卓APP箭头
箭头给我发消息

客服QQ:3315713922

2022年软件设计师考试知识点(六十三):图

作者:匿名     来源: 软考点击数:792发布时间: 2022-01-11 22:28:37

标签: 2022年软件设计师考试知识点2022年软件设计师考点

软考,您想通过吗?一次通过才是硬道理

  为帮助考生备考2022年软考中级软件设计师考试,课课家小编为大家整理了2022年软件设计师考试知识点(六十三):图,希望对大家备考会有帮助。

  很多考生在备考2022年软件设计师考试,课课家小编为大家整理了2022年软件设计师考试知识点(六十三):图,供考生备考复习。

  图(★★)

  【考法分析】

  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、了解最小生成树的构造。

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

 

  相关推荐:2022年软件设计师考试知识点汇总

赞(9)
踩(0)
分享到:
华为认证网络工程师 HCIE直播课视频教程