手机网站开发介绍,室内设计效果图平面图,windows优化大师会员,WordPress转织梦样式调用目录 一、定义
深度优先遍历通常用于解决以下问题#xff1a;
深度优先遍历算法具有以下优点#xff1a;
深度优先遍历算法的一个缺点是#xff1a;
二、代码
空间复杂度#xff1a;
时间复杂度#xff1a;
邻接矩阵存储#xff1a;
邻接表存储#xff1a;
三、…目录 一、定义
深度优先遍历通常用于解决以下问题
深度优先遍历算法具有以下优点
深度优先遍历算法的一个缺点是
二、代码
空间复杂度
时间复杂度
邻接矩阵存储
邻接表存储
三、手动模拟深度优先遍历⭐⭐⭐⭐⭐
1、首先访问结点2
2、访问2的邻接点6
3、跳转到6访问6的邻接结点发现2已经被访问过了于是访问7
4、跳转到7访问7的邻接结点6被访问过了所以跳过访问8
5、跳转到8访问8的邻接结点访问4
6、继续访问跳转到4访问4的邻接结点访问3
7、跳转到3访问3的邻接结点访问66被访问过了跳过访问7跳过访问4跳过由于3的邻接结点都被访问完了所以返回上一级
8、遍历4访问8跳过访问7跳过返回上一级
9、上一级是8所以遍历8访问7跳过返回上一级
10、遍历7访问3跳过访问4跳过返回上一级
11、遍历6访问3跳过返回上一级
12、遍历2访问1
13、跳转至1访问2跳过访问5
14、跳转至5访问1跳过
至此邻接表所有结点全部访问完毕。
四、深度优先生成树
五、深度优先生成森林
六、图的遍历与图的连通性
无向图
有向图 一、定义
1、深度优先遍历(Depth-First Search, DFS)是一种遍历或搜索图的算法。
2、该算法从图的某一个起始节点开始递归地探索该节点的所有邻居节点直到找出整个图的连通部分。
3、DFS使用了栈的数据结构来保存待访问的节点。
4、当访问一个节点时我们将该节点入栈并将其标记为已访问。
然后如果该节点有未访问的邻居节点我们就将邻居节点入栈并标记为已访问。
这个过程一直持续到栈为空为止。当栈为空时我们就完成了整个图的深度优先遍历。
深度优先遍历通常用于解决以下问题
检测一个无向图是否为连通图。搜索一条路径例如在迷宫中从起点到终点的最短路径。找出一个无向图的所有连通分量。
深度优先遍历算法具有以下优点
实现简单。占用的空间相对较小因为它只需要一个栈来保存待访问的节点。适用于解决一些基于图的问题。
深度优先遍历算法的一个缺点是
它可能会陷入无限循环中因为它只是深度优先探索邻居节点而不是考虑整个图的结构。这种缺点可以通过引入剪枝策略来解决例如标记已访问的节点或者设置搜索的深度限制。
二、代码
#include iostream
#include vectorusing namespace std;void DFS(int start, vectorvectorint graph, vectorbool visited) {visited[start] true; // 标记当前节点为已访问cout start ; // 输出遍历到的节点for (int i 0; i graph[start].size(); i) {int next graph[start][i];if (!visited[next]) { // 如果下一个节点未被访问DFS(next, graph, visited); // 递归访问下一个节点}}
}int main() {// 构建一个图vectorvectorint graph {{1, 2}, {0, 3, 4}, {0, 5, 6}, {1}, {1}, {2}, {2, 7}, {6}};vectorbool visited(graph.size(), false); // 初始化所有节点为未访问状态DFS(0, graph, visited); // 从节点0开始深度优先遍历return 0;
}
空间复杂度
最好情况 最坏情况 时间复杂度 邻接矩阵存储 邻接表存储 三、手动模拟深度优先遍历⭐⭐⭐⭐⭐
假如我们由如下邻接表 我们要得到从2开始的深度优先遍历序列。
1、首先访问结点2 此时遍历序列为 2、访问2的邻接点6 此时遍历序列为 3、跳转到6访问6的邻接结点发现2已经被访问过了于是访问7 此时遍历序列为 4、跳转到7访问7的邻接结点6被访问过了所以跳过访问8 此时遍历序列为 5、跳转到8访问8的邻接结点访问4 此时遍历序列为 6、继续访问跳转到4访问4的邻接结点访问3 此时遍历序列为 7、跳转到3访问3的邻接结点访问66被访问过了跳过访问7跳过访问4跳过由于3的邻接结点都被访问完了所以返回上一级 8、遍历4访问8跳过访问7跳过返回上一级 9、上一级是8所以遍历8访问7跳过返回上一级 10、遍历7访问3跳过访问4跳过返回上一级 11、遍历6访问3跳过返回上一级 12、遍历2访问1 此时遍历序列为 13、跳转至1访问2跳过访问5 此时遍历序列为 14、跳转至5访问1跳过 至此邻接表所有结点全部访问完毕。
得到深度优先遍历序列为2、6、7、8、4、3、1、5
四、深度优先生成树
与广度优先生成树相似都是把每个结点第一次被访问的路径提取出来所生成的树就是生成树
以下图为例 我们从2开始访问把每个结点第一次被访问的路径标红这就是生成树。
注意 五、深度优先生成森林
我们多加一个图 然后表示出它的深度优先生成树写在一起就是深度优先生成森林 六、图的遍历与图的连通性
无向图 有向图
