。

遍历图的两种主要方法是深度优先搜索#xff08;Depth-First

Search,

DFS#xff09;和广度优先搜索#xff08;Breadth-First

Search,

BFS#xff09;。

本文将详细介绍深度优先搜索的定义、算法及其实现。

深度优先搜…引言

图遍历是指按照一定的顺序访问图中的每个顶点。

遍历图的两种主要方法是深度优先搜索Depth-First

Search,

深度优先搜索DFS是一种遍历或搜索图的算法从图的某个起始顶点开始尽可能深入地访问每一个顶点直到无法继续为止然后回溯并继续搜索未访问的顶点。

算法步骤

从起始顶点开始标记该顶点为已访问。

递归地访问所有未被访问的邻接顶点。

回溯到上一个顶点继续访问其他未被访问的邻接顶点直到所有顶点都被访问。

假设我们有一个无向图顶点集合为

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

ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EBMKMW8R6TqnZgRL

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%,

#aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EBMKMW8R6TqnZgRL

:root{--mermaid-font-family:"trebuchet

DFS实现递归方式

LinkedList[numVertices];visited

new

{adjLists[i].add(j);adjLists[j].add(i);

无向图}//

);}System.out.println();}}public

static

5);System.out.println(图的邻接表表示);graph.printAdjLists();System.out.println(深度优先搜索遍历结果);graph.DFS(0);

输出0

LinkedList[numVertices];visited

new

{adjLists[i].add(j);adjLists[j].add(i);

无向图}//

Stack();stack.push(vertex);while

(!stack.isEmpty())

);}System.out.println();}}public

static

5);System.out.println(图的邻接表表示);graph.printAdjLists();System.out.println(深度优先搜索遍历结果);graph.DFS(0);

输出0

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

ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ZB1WPU2WFNBscRzp

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%,

#aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ZB1WPU2WFNBscRzp

:root{--mermaid-font-family:"trebuchet

访问顶点0

通过上述讲解和实例代码我们详细展示了深度优先搜索DFS的定义、算法及其实现。

DFS是一种重要的图遍历算法广泛应用于各种场景。

希望这篇博客对您有所帮助

如果您觉得这篇文章对您有帮助请关注我的CSDN博客点赞并收藏这篇文章您的支持是我持续创作的动力

关键内容总结

深度优先搜索DFS的定义DFS算法的步骤DFS的递归和非递归实现DFS算法的图解

推荐阅读深入探索设计模式专栏详细讲解各种设计模式的应用和优化。

点击查看深入探索设计模式。

特别推荐设计模式实战专栏深入解析设计模式的实际应用提升您的编程技巧。

点击查看设计模式实战。

邻接表表示