做拍卖网站,网络公司 网站源码,网站设计的书,网站搭建素材引言
图遍历是指按照一定的顺序访问图中的每个顶点。遍历图的两种主要方法是深度优先搜索#xff08;Depth-First Search, DFS#xff09;和广度优先搜索#xff08;Breadth-First Search, BFS#xff09;。本文将详细介绍深度优先搜索的定义、算法及其实现。
深度优先搜…引言
图遍历是指按照一定的顺序访问图中的每个顶点。遍历图的两种主要方法是深度优先搜索Depth-First Search, DFS和广度优先搜索Breadth-First Search, BFS。本文将详细介绍深度优先搜索的定义、算法及其实现。
深度优先搜索DFS
定义
深度优先搜索DFS是一种遍历或搜索图的算法从图的某个起始顶点开始尽可能深入地访问每一个顶点直到无法继续为止然后回溯并继续搜索未访问的顶点。
算法步骤
从起始顶点开始标记该顶点为已访问。递归地访问所有未被访问的邻接顶点。回溯到上一个顶点继续访问其他未被访问的邻接顶点直到所有顶点都被访问。
示例
假设我们有一个无向图顶点集合为 ({A, B, C, D, E, F})边集合为 ({(A, B), (A, C), (B, D), (C, E), (D, F)})。 #mermaid-svg-EBMKMW8R6TqnZgRL {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-EBMKMW8R6TqnZgRL .error-icon{fill:#552222;}#mermaid-svg-EBMKMW8R6TqnZgRL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-EBMKMW8R6TqnZgRL .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-EBMKMW8R6TqnZgRL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-EBMKMW8R6TqnZgRL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-EBMKMW8R6TqnZgRL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-EBMKMW8R6TqnZgRL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-EBMKMW8R6TqnZgRL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-EBMKMW8R6TqnZgRL .marker.cross{stroke:#333333;}#mermaid-svg-EBMKMW8R6TqnZgRL svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EBMKMW8R6TqnZgRL .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-EBMKMW8R6TqnZgRL .cluster-label text{fill:#333;}#mermaid-svg-EBMKMW8R6TqnZgRL .cluster-label span{color:#333;}#mermaid-svg-EBMKMW8R6TqnZgRL .label text,#mermaid-svg-EBMKMW8R6TqnZgRL span{fill:#333;color:#333;}#mermaid-svg-EBMKMW8R6TqnZgRL .node rect,#mermaid-svg-EBMKMW8R6TqnZgRL .node circle,#mermaid-svg-EBMKMW8R6TqnZgRL .node ellipse,#mermaid-svg-EBMKMW8R6TqnZgRL .node polygon,#mermaid-svg-EBMKMW8R6TqnZgRL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-EBMKMW8R6TqnZgRL .node .label{text-align:center;}#mermaid-svg-EBMKMW8R6TqnZgRL .node.clickable{cursor:pointer;}#mermaid-svg-EBMKMW8R6TqnZgRL .arrowheadPath{fill:#333333;}#mermaid-svg-EBMKMW8R6TqnZgRL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-EBMKMW8R6TqnZgRL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-EBMKMW8R6TqnZgRL .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-EBMKMW8R6TqnZgRL .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-EBMKMW8R6TqnZgRL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-EBMKMW8R6TqnZgRL .cluster text{fill:#333;}#mermaid-svg-EBMKMW8R6TqnZgRL .cluster span{color:#333;}#mermaid-svg-EBMKMW8R6TqnZgRL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EBMKMW8R6TqnZgRL :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} A B C D E F DFS实现递归方式
下面是用Java实现DFS的代码示例
import java.util.LinkedList;
import java.util.List;public class Graph {private LinkedListInteger[] adjLists; // 邻接表数组private boolean[] visited; // 访问标记数组// 构造函数public Graph(int numVertices) {adjLists new LinkedList[numVertices];visited new boolean[numVertices];for (int i 0; i numVertices; i) {adjLists[i] new LinkedList();}}// 添加边public void addEdge(int i, int j) {adjLists[i].add(j);adjLists[j].add(i); // 无向图}// 深度优先搜索public void DFS(int vertex) {visited[vertex] true;System.out.print(vertex );for (int adj : adjLists[vertex]) {if (!visited[adj]) {DFS(adj);}}}// 打印邻接表public void printAdjLists() {for (int i 0; i adjLists.length; i) {System.out.print(i : );for (int j : adjLists[i]) {System.out.print(j );}System.out.println();}}public static void main(String[] args) {Graph graph new Graph(6);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);System.out.println(图的邻接表表示);graph.printAdjLists();System.out.println(深度优先搜索遍历结果);graph.DFS(0); // 输出0 1 3 5 2 4}
}DFS实现非递归方式
下面是用Java实现DFS的非递归方式的代码示例
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;public class Graph {private LinkedListInteger[] adjLists; // 邻接表数组private boolean[] visited; // 访问标记数组// 构造函数public Graph(int numVertices) {adjLists new LinkedList[numVertices];visited new boolean[numVertices];for (int i 0; i numVertices; i) {adjLists[i] new LinkedList();}}// 添加边public void addEdge(int i, int j) {adjLists[i].add(j);adjLists[j].add(i); // 无向图}// 深度优先搜索非递归public void DFS(int vertex) {StackInteger stack new Stack();stack.push(vertex);while (!stack.isEmpty()) {int v stack.pop();if (!visited[v]) {visited[v] true;System.out.print(v );}for (int adj : adjLists[v]) {if (!visited[adj]) {stack.push(adj);}}}}// 打印邻接表public void printAdjLists() {for (int i 0; i adjLists.length; i) {System.out.print(i : );for (int j : adjLists[i]) {System.out.print(j );}System.out.println();}}public static void main(String[] args) {Graph graph new Graph(6);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);System.out.println(图的邻接表表示);graph.printAdjLists();System.out.println(深度优先搜索遍历结果);graph.DFS(0); // 输出0 2 4 1 3 5}
}DFS算法步骤图解
以下是对上述示例中DFS算法步骤的图解 #mermaid-svg-ZB1WPU2WFNBscRzp {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ZB1WPU2WFNBscRzp .error-icon{fill:#552222;}#mermaid-svg-ZB1WPU2WFNBscRzp .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ZB1WPU2WFNBscRzp .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ZB1WPU2WFNBscRzp .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ZB1WPU2WFNBscRzp .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ZB1WPU2WFNBscRzp .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ZB1WPU2WFNBscRzp .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ZB1WPU2WFNBscRzp .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ZB1WPU2WFNBscRzp .marker.cross{stroke:#333333;}#mermaid-svg-ZB1WPU2WFNBscRzp svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ZB1WPU2WFNBscRzp .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ZB1WPU2WFNBscRzp .cluster-label text{fill:#333;}#mermaid-svg-ZB1WPU2WFNBscRzp .cluster-label span{color:#333;}#mermaid-svg-ZB1WPU2WFNBscRzp .label text,#mermaid-svg-ZB1WPU2WFNBscRzp span{fill:#333;color:#333;}#mermaid-svg-ZB1WPU2WFNBscRzp .node rect,#mermaid-svg-ZB1WPU2WFNBscRzp .node circle,#mermaid-svg-ZB1WPU2WFNBscRzp .node ellipse,#mermaid-svg-ZB1WPU2WFNBscRzp .node polygon,#mermaid-svg-ZB1WPU2WFNBscRzp .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ZB1WPU2WFNBscRzp .node .label{text-align:center;}#mermaid-svg-ZB1WPU2WFNBscRzp .node.clickable{cursor:pointer;}#mermaid-svg-ZB1WPU2WFNBscRzp .arrowheadPath{fill:#333333;}#mermaid-svg-ZB1WPU2WFNBscRzp .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ZB1WPU2WFNBscRzp .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ZB1WPU2WFNBscRzp .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ZB1WPU2WFNBscRzp .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ZB1WPU2WFNBscRzp .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ZB1WPU2WFNBscRzp .cluster text{fill:#333;}#mermaid-svg-ZB1WPU2WFNBscRzp .cluster span{color:#333;}#mermaid-svg-ZB1WPU2WFNBscRzp div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ZB1WPU2WFNBscRzp :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 0 1 2 3 4 5 访问顶点0 访问顶点1 访问顶点3 访问顶点5 回溯到顶点3 回溯到顶点1 回溯到顶点0 访问顶点2 访问顶点4 结论
通过上述讲解和实例代码我们详细展示了深度优先搜索DFS的定义、算法及其实现。DFS是一种重要的图遍历算法广泛应用于各种场景。希望这篇博客对您有所帮助 如果您觉得这篇文章对您有帮助请关注我的CSDN博客点赞并收藏这篇文章您的支持是我持续创作的动力 关键内容总结
深度优先搜索DFS的定义DFS算法的步骤DFS的递归和非递归实现DFS算法的图解 推荐阅读深入探索设计模式专栏详细讲解各种设计模式的应用和优化。点击查看深入探索设计模式。 特别推荐设计模式实战专栏深入解析设计模式的实际应用提升您的编程技巧。点击查看设计模式实战。
如有任何疑问或建议欢迎在评论区留言讨论。谢谢阅读 测试代码的运行结果
邻接表表示
0: 1 2
1: 0 3
2: 0 4
3: 1 5
4: 2
5: 3 深度优先搜索遍历结果
递归方式0 1 3 5 2 4
非递归方式0 2 4 1 3 5
