编程实现图的深度优先和广度优先搜索遍历两种算法(邻接矩阵和邻接表两种存储方式任选其一)
时间: 2023-04-24 16:02:10 浏览: 115
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
深度优先搜索遍历算法:
邻接矩阵存储方式:
1. 从起点开始,将其标记为已访问。
2. 遍历起点的所有邻居节点,如果邻居节点未被访问,则递归访问该邻居节点。
3. 重复步骤2,直到所有节点都被访问。
邻接表存储方式:
1. 从起点开始,将其标记为已访问,并将其加入栈中。
2. 从栈中取出一个节点,遍历该节点的所有邻居节点,如果邻居节点未被访问,则将其标记为已访问,并将其加入栈中。
3. 重复步骤2,直到栈为空。
广度优先搜索遍历算法:
邻接矩阵存储方式:
1. 从起点开始,将其标记为已访问,并将其加入队列中。
2. 从队列中取出一个节点,遍历该节点的所有邻居节点,如果邻居节点未被访问,则将其标记为已访问,并将其加入队列中。
3. 重复步骤2,直到队列为空。
邻接表存储方式:
1. 从起点开始,将其标记为已访问,并将其加入队列中。
2. 从队列中取出一个节点,遍历该节点的所有邻居节点,如果邻居节点未被访问,则将其标记为已访问,并将其加入队列中。
3. 重复步骤2,直到队列为空。
阅读全文