深度优先搜索可以判断图中是否有环(用深度优先搜索遍历一个有向无环图)
导语：深度优先搜索算法检测有向环的理解和实用方法
在调度系统中牵扯到对调度数据结构的有向环进行检测，所以使用DFS算法来检测组装形成的调度数据结构不存在无限循环结构，记录分享DFS如何检测环的。
举个栗子
栗子
转换 为临接矩阵可以转化为数据问题：
矩阵表示
根据深度优先搜索，我们这里默认按行进行遍历，对于第一行，起始节点就是第一行对应到那个元素0，遍历到第二个元素时发现不为0，则节点0可以到达节点1；接着以节点1作为中转点，遍历节点1对应的那一行，也就是矩阵中的第二行，发现节点1可以到达节点2；同理，继续遍历节点2所在的行，发现节点2可以到达节点0，而节点0正是起始节点，也就是发现了有向图中存在着环路。
检测图解
代码实现
import java.util.Arrays;public class graph { private static boolean result = false; public static void main(String[] args) { int[][] matrix = new int[][]{{0,1,0,1,1}, {0,0,1,0,0}, {1,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0}}; boolean[] visited = new boolean[matrix.length]; for(int i = 0; i < matrix.length; i++) for(int j = 0; j < matrix[0].length; j++){ //节点i到j可达则进行深度优先搜索 if(matrix[i][j] != 0){ Arrays.fill(visited, false); visited[j] = true; dfs(matrix, i, j, visited); } if(result){ System.out.println(); return; } } System.out.println(); } private static void dfs(int[][] matrix, int start, int cur_node, boolean[] visited){ for(int col = 0; col < matrix.length; col++){ //当前节点可达且未访问过 if(matrix[cur_node][col] != 0 && !visited[col]){ if(col == start){ result = true; return; } //记录访问过的节点 visited[col] = true; dfs(matrix, start, col, visited); visited[col] = false; } } }}深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分 支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发 现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
深度优先遍历图算法步骤：
1. 访问顶点v；
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
如下图
转换图解
借用一个邻接表和布尔类型数组（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将所有点按一定次序存入邻接表，再通过迭代器，对邻接表的linklist和布尔数组做出操作，从而达到不重复递归遍历的效果。
免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请与我联系，一经查实立刻删除内容。本文内容由快快网络小德创作整理编辑！