深圳网页网站设计,做网站的升级人,wordpress高端博客主题,新品发布会ppt参考树
并查集#xff1a; 并查集的应用#xff1a; 判断连通性、判环Kruskal算法排序并查集 并查集的存储方式 逻辑#xff1a;双亲表示法的树存储#xff1a;数组 并查集的时间复杂度#xff08;m为并查集长度#xff09; find#xff1a;优化前为 O ( m ) O(m) O(m) 并查集的应用 判断连通性、判环Kruskal算法排序并查集 并查集的存储方式 逻辑双亲表示法的树存储数组 并查集的时间复杂度m为并查集长度 find优化前为 O ( m ) O(m) O(m)优化后为 O ( l o g 2 n ) O(log_{2}n) O(log2n)union O ( 1 ) O(1) O(1)总复杂度优化前 O ( m 2 ) O(m^2) O(m2)优化后 O ( m ) O(m) O(m) 树、森林、二叉树遍历序列的关系 树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历 关于森林的中序遍历/后序遍历叫法问题二者指森林的同一种遍历方法都是先遍历第一棵树的子节点然后是第一棵树的根节点然后是第二棵树… 之所以称为中序遍历是因为要先处理完一棵树再处理另一棵树。
图
DFS与BFS算法的应用 DFS 判断图的强连通性 无向图的连通性若从任意一个节点出发仅需一次DFS就可以访问图中所有节点则该无向图就是连通的有向图的强连通性从任意一个节点v出发DFS若可以遍历该有向图的所有节点则此时将该有向图的所有边反向再次从节点v出发进行DFS若能够再次遍历该有向图的所有节点则表示该有向图是强连通图 判断图中是否有环回路欧拉回路求解若一条路径能不重复的包含图中所有边则称该路径为欧拉路径。若一条回路从一个节点出发又能回到该节点的路径是欧拉路径则称为欧拉回路。DFS可以判断图中是否存在欧拉回路迷宫判断二分图 BFS 求解单源最短路径问题只适用于无权图迷宫判断二分图 最短路径 有无环回路对Dijkstra算法并无影响但Dijkstra算法不能求解存在负权值边的图Floyd算法可以求带有负权值边的图但图中不能存在负权回路因为带有负权回路的图没有最短路径Dijkstra算法是解决单源最短路径类问题floyd算法是解决多源最短路径指图中任意两个顶点之间的最短路径类问题Dijkstra算法属于贪心算法floyd算法属于动态规划算法 判断有向图是否有环回路的几种方法 深度优先遍历若在遍历过程中遇到要访问的节点已在栈中就是有环拓扑排序找不到拓扑序列必定有环 拓扑排序 在拓扑排序算法中为暂存入度为零的顶点可以使用栈也可以使用队列。因为只要入了栈/队列就都是入度为零的从哪个入度为零的先开始都无所谓采用深度优先遍历也可实现拓扑排序
