A. DS图—图的邻接矩阵存储及度计算

邻接矩阵是图的一种常用表示方法，其基本思想是用一个矩阵来表示图中各个顶点之间的连接关系。具体来说，矩阵的行和列分别对应图中的顶点，矩阵中的元素表示相应顶点之间是否有边连接。对于无向图，邻接矩阵是一个对称矩阵，因为边的连接是双向的；对于有向图，邻接矩阵则不一定是对称的。

邻接矩阵的存储方式可以采用一维数组或二维数组，一维数组更节省空间，但访问元素时需要进行下标的计算，二维数组则更直观易懂，但占用空间较大。

邻接矩阵存储方式的优点是方便进行图的遍历、搜索和计算图的度等操作。其中，度是指与某个顶点相连的边的数量，对于无向图，每个顶点的度就是其相邻顶点的数量；对于有向图，每个顶点有出度和入度两个概念，分别表示以该顶点为起点和终点的边的数量。

计算图的度可以通过遍历邻接矩阵来实现。对于无向图，每个顶点的度可以通过遍历邻接矩阵中相应行的元素来计算；对于有向图，每个顶点的出度可以通过遍历邻接矩阵中相应行的元素来计算，入度则可以通过遍历邻接矩阵中相应列的元素来计算。

相关问题

6-1 邻接矩阵存储图的深度优先遍历 分数 20 全屏浏览题目 切换布局 作者 ds课程组

深度优先遍历（Depth First Search，DFS）是一种针对图的遍历方式，它从图的某一顶点出发，访问此顶点，然后从其中一个邻接点出发再次进行深度优先遍历，直到所有顶点都被访问过为止。

在邻接矩阵存储图的深度优先遍历中，我们首先需要创建一个大小为n*n的矩阵来表示图的邻接关系，其中n为图的顶点数。然后我们需要创建一个大小为n的数组来记录每个顶点是否被访问过。

接下来，我们可以使用递归或者栈来实现深度优先遍历。递归方式下，我们从图中的某个顶点v开始，首先将该顶点标记为已访问，然后依次访问其未被访问过的邻接点，并对这些邻接点递归调用深度优先遍历函数。栈方式下，我们首先将起始顶点v入栈，然后当栈非空时，弹出栈顶元素并访问其未被访问过的邻接点，将这些邻接点入栈，直到栈为空为止。

在实现深度优先遍历的过程中，我们需要注意避免重复访问已经访问过的顶点，以及要考虑图中可能存在多个连通分量的情况。

总的来说，邻接矩阵存储图的深度优先遍历是一种有效的图遍历方法，能够帮助我们了解图的结构和特性。

DS18B20温度计算

DS18B20是一种数字温度传感器，它可以通过单总线接口与微控制器进行通信。DS18B20温度传感器的输出是一个16位的数字信号，其中包含了当前温度的信息。以下是计算温度的方法：

1. 读取DS18B20传感器输出的16位数字信号，其中高8位表示整数部分，低8位表示小数部分。

2. 将高8位和低8位分别转换为十进制数。

3. 将小数部分转换为实际温度，公式为：小数部分除以2的8次方，即小数部分/256。

4. 将整数部分和小数部分的温度值相加，即可得到当前温度的实际值。

例如，若读取的数字信号为0x1F08，则高8位为0x1F，低8位为0x08。将高8位和低8位分别转换为十进制数，得到31和8。将小数部分的0x08转换为实际温度，得到0.03125度。将整数部分31和小数部分的0.03125度相加，得到31.03125度，即为当前温度的实际值。