分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历
时间: 2023-04-29 13:05:04 浏览: 160
邻接矩阵实现图的深度优先遍历:
1. 从起点开始,将起点标记为已访问
2. 从起点开始,遍历起点的所有未访问的邻结点
3. 对于遍历到的邻结点,重复步骤1和2,直到遍历完整张图
邻接矩阵实现图的广度优先遍历:
1. 从起点开始,将起点入队
2. 当队列不为空时,取出队头元素
3. 将队头元素标记为已访问
4. 将队头元素的所有未访问的邻结点入队
5. 重复步骤2-4直到遍历完整张图
邻接表实现图的深度优先遍历:
1. 从起点开始,将起点标记为已访问
2. 从起点开始,遍历起点的所有未访问的邻结点
3. 对于遍历到的邻结点,重复步骤1和2,直到遍历完整张图
邻接表实现图的广度优先遍历:
1. 从起点开始,将起点入队
2. 当队列不为空时,取出队头元素
3. 将队头元素标记为已访问
4. 将队头元素的所有未访问的邻结点入队
5. 重复步邻接矩阵实现图的深度优先遍历:
1. 从第一个顶点开始,标记该顶点已遍历
2. 遍历该顶点的所有邻接顶点,如果该邻接顶点未被遍历,则递归遍历
3. 遍历完所有邻接顶点后,返回上一层递归
邻接矩阵实现图的广度优先遍历:
1. 从第一个顶点开始,标记该顶点已遍历
2. 将该顶点的所有邻接顶点加入队列
3. 从队列中取出一个顶点,如果该顶点未被遍历,则标记该顶点已遍历,并将该顶点的所有邻接顶点加入队列
4. 重复步骤3直到队列为空
邻接表实现图的深度优先遍历:
1. 从第一个顶点开始,标记该顶点已遍历
2. 遍历该顶点的所有邻接顶点,如果该邻接顶点未被遍历,则递归遍历
3. 遍历完所有邻接顶点后,返回上一层递归
邻接表实现图的广度优先遍历:
1. 从第一个顶点开始,标记该顶点已遍历
2. 将该顶点的所有邻接对于邻接矩阵和邻接表实现图的深度优先遍历,都是首先从起点开始遍历,标记起点为已访问,然后遍历起点的所有未访问的邻结点,对于遍历到的邻结点,重复步骤1和2,直到遍历完整张图。对于邻接矩阵和邻接表实现图的广度优先遍历,都是首先从起点开始遍历,将起点入队,当队列不为空时,取出队头元素,标记为已访问,将队头元素的所有未访问的邻结点入队,重复步骤2-4直到遍历完整张图.
阅读全文