4.6 - 堆 4.7 - 图

发布于:2023-01-17 ⋅ 阅读:(346) ⋅ 点赞:(0)

目录

一、堆

1、概念

2、堆总是满足下列性质

3、考法1:大/小顶堆

二、图

1、概念

2、度

3、入度

4、出度

5、有向完全图和无向完全图

三、图的存储结构:领接矩阵表示法

1、有向图的领接矩阵表示法

2、无向图的领接矩阵表示法

3、考法1:领接矩阵表存储


一、堆

1、概念

  • 是计算机科学中一类特殊数据结构的统称;

  • 堆通常是一个可以被看做一棵树的数组对象。

2、堆总是满足下列性质

  • 堆中某个节点的值,总是不大于或不小于其父节点的值;

  • 堆总是一棵完全二叉树(完全二叉树压树时,每一层的左右节点都是有数的,不应该有空的。)。

3、考法1:大/小顶堆

  • 解题方式:按照“层次遍历”的方式,将选项压成一棵二叉树,进而得到结果。

  • 层级遍历:从上往下,同一层有多个节点则从左往右。

  • 注意:因为“堆”是一棵完全二叉树,所以压树时,每一层的左右节点都是有数的,不应该有空的。

二、图

1、概念

  • 由集合V和E构成的二元组,记作G=(V,E)。

  • V:代表点;为了与树形结构区别,在图结构中常将结点称为顶点;

  • E:代表边,分为有向边、无向边;

  • 所以图可以简单理解为由点和边构成的集合,有向图每条边都有方向,无向图每条边都没有方向。

2、度

  • 与顶点v相关的边的条数为顶点的度。

3、入度

  • 在有向图中,指向顶点v的边的条数称为顶点v的入度。

4、出度

  • 由顶点v发出的边的条数称为顶点v的出度。

5、有向完全图和无向完全图

  • 在有向图中有n个顶点,则最多有n(n-1)条边(图中任意两点都有两条边相连),将具有n(n-1)条边的有向图称为有向完全图。

  • 若无向图中有n个顶点,则最多有n(n-1)/2条边(任意两个顶点之间都有一条边),将这种无向图称为完全无向图。

三、图的存储结构:领接矩阵表示法

1、有向图的领接矩阵表示法

  • 用n*n的矩阵存放图中的信息;n就是图中点的个数。

  • 第一行存的是节点1与其他节点的关系情况;第一行第一个元素表示节点1与节点1的关系,第一行第二个元素表示节点1与节点2的关系......

  • 第一个元素是0,因为节点1没有有向边指向节点1;第二个元素是1,因为节点1有一条边指向节点2;以此类推。

  • 注意箭头是出度时,矩阵元素才是1;

2、无向图的领接矩阵表示法

  • 用n*n的矩阵存放图中的信息;n就是图中点的个数。

  • 第一行存的是节点1与其他节点的关系情况;第一行第一个元素表示节点1与节点1的关系,第一行第二个元素表示节点1与节点2的关系............

  • 第一个元素是0,因为节点1与节点1之间没有边;第二个元素是1,因为节点1与节点2之间有一条边;以此类推。

  • 不需要考虑箭头的方向,只要右边相连接就是1。

3、考法1:领接矩阵表存储


网站公告

今日签到

点亮在社区的每一天
去签到