本章内容是使用java实现的，Github代码库： https://github.com/zhe Kaili/code/tree/main/graph/src
33558www.Sina.com/github如果您使用的是管理图像，无法加载，请翻墙
【参考资料】im OOC Popo老师：算法系列图论精讲面试必须晋升(Java版) )
【过去的博客链接】
图论算法(1，2 )图的分类、图的基本概念(无向图和有向图、无权图、无环图、完全图、二分图； 简单图、连通分量、图的生成树、子图和母图)
图论算法(3)图的基本表示(邻接矩阵、邻接表、邻接矩阵和邻接表的对比) ) ) ) ) ) ) ) ) ) ) ) ) ) )。
图论算法(4)图的深度优先遍历DFS
图论算法(5)图的广度优先穿越BFS
图论算法(6):LeetCode图论算法练习(785 .判决二分图，695 .岛的最大面积，Floodfill算法，并查集) )。
4图深度优先遍历DFS (关于树的前、中、后、层序遍历，总结为https://blog.csdn.net/ZL 6481033/article/details/81009388 )
先看看查看文章内的图片可能需要科学上网！。 (以上一个导线测量为例) )。
reorder (根)； //从根节点到preorder(treenodenode ) if ) node！=null ) list.add(node.val )； preorder(node.left )； preorder(node.right )；树的深度优先遍历:与树略有不同，图形化算法需要在递归前确定是否有节点被访问，其时间复杂度为o(ve ) o ) ve ) o ) ve )
visited[0.V-1]=false； 保证使用//for循环遍历各点，算法得到无序图for(intv=0； v； v ) if (！ visited[v](DFS ) v； DFS(intv ) visited[v]=true； //list.add(v )标记为已访问的for(intw:adj ) v ) ) if (！ visited[w](DFS ) w； java实现： GraphDFS.java
4.1求ex :连通分量就是求包含几个连通图
visited[0.V-1]=-1； ccount=0； //连通分量for(v=0； v； v ) if(visited[v]==-1 ) DFS ) v，ccount )； ccount； DFS(v，ccid ) visited ) ccid； list.add(v )； for(intw:adj ) v ) ) if ) visited[w]==-1 ) DFS ) w，ccid )； java实现： CC.java
图的深度优先先序遍历:可以如下判断
visited[v]==visited[w]； 4.2求ex :两点之间的路径(不一定是最短的) ) ) ) ) ) ) ) )。
//pre[i]=j表示存在路径j-i//pre[i]=-1来代替visited [ I ]=false pre [0. v-1 ]=-1。 s=0； //自定义起点t=5； //自定义端点pre[s]=s； //将源的源转换为自己的DFS(s )； ///返回值是目标点tbooleanDFS(intv ) for ) intw:adj ) ) if ) visited ) w )=-1 ) pre ) w )=v； if(w==t )返回真； if(DFS ) w ) )返回真； 返回假；==java实现： Path.java==
4.3 Ex:环检java的实现： CycleDetection.java
4.4 Ex:二分图检验
左右两个看起来完全不同的图其实是一样的，但左侧的形状明显是二分图，而右侧更普通、更随机的形状无法直观判断。
基于DFS的二分图检验：
//-1:未访问//0:二分图的一侧//1:二分图的另一侧color[0.V-1]=-1； color[0]=0； DFS(0； ///返回值是目标图不是二分图的证据BooleanDFS(intv ) for ) intw:adj ) v ) ) if ) color ) w )=-1 ) color ) w )=1-color ) v ) IIF ) java实现： BipartitionDetection.java