JAVA中深度优先搜索(DFS)与广度优先搜索(BFS)算法解析

1. 深度优先搜索算法（Depth-First Search, DFS）基础概念 深度优先搜索算法是一种用于遍历或搜索树或图的算法。在这种算法中，你从一个源节点开始，尽可能深地探索分支。当节点v的所有出边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。 2. 深度优先搜索与广度优先搜索(Breadth-First Search, BFS)的对比 DFS是一种深度优先遍历算法，而BFS是一种广度优先遍历算法。BFS在搜索时会先访问起始点邻近的节点，然后再对邻近节点的邻近节点进行访问，如此类推。而DFS则尽可能深地探索图的分支。 3. DFS算法在Java中的实现 在Java中实现DFS算法通常需要使用递归或栈。以下是DFS算法使用递归方式实现的基本步骤： - 创建一个Boolean类型的数组标记节点是否被访问过。 - 创建一个递归函数，该函数接受节点为参数。 - 在递归函数中，首先将当前节点标记为已访问。 - 遍历当前节点的所有邻接节点。 - 对每一个未访问的邻接节点调用递归函数。 4. DFS的应用场景 DFS算法有多种应用场景，如解决迷宫问题、解算数谜（如数独）、图的拓扑排序、检测图的循环、解决有向图的强连通分量问题以及计算机网络中的路由算法等。 5. BFS与DFS的时间复杂度 在无权图中，若使用邻接矩阵存储，BFS和DFS的时间复杂度都是O(V+E)，其中V是顶点数，E是边数。若使用邻接表存储，BFS的时间复杂度仍然是O(V+E)，但是DFS的时间复杂度为O(V)。 6. 递归与栈在DFS中的作用 在DFS的递归实现中，递归机制本身提供了栈的功能，用于跟踪路径。而在非递归实现中，则需要显式地使用栈数据结构来跟踪待访问的节点。 7. 实际代码实现（以Java为例） 在Java中，可以通过以下方式实现DFS： ```java public class Graph { private int V; // No. of vertices private LinkedList<Integer> adj[]; // Adjacency Lists // Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList(); } // Function to add an edge into the graph void addEdge(int v, int w) { adj[v].add(w); // Add w to v’s list. } // A function used by DFS void DFSUtil(int v, boolean visited[]) { // Mark the current node as visited and print it visited[v] = true; System.out.print(v + " "); // Recur for all the vertices adjacent to this vertex Iterator<Integer> i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil(n, visited); } } // The function to do DFS traversal. It uses recursive DFSUtil() void DFS(int v) { // Mark all the vertices as not visited(set as // false by default in java) boolean visited[] = new boolean[V]; // Call the recursive helper function to print DFS traversal DFSUtil(v, visited); } } // Main class to test above class Main { public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); } } ``` 以上代码中，我们定义了一个Graph类，并通过DFSUtil递归函数实现了DFS算法。我们还定义了一个DFS函数，该函数初始化一个访问标记数组，并开始递归遍历。这段代码打印出了从节点2开始的深度优先遍历的结果。