深度优先搜索（DFS）是一种用于遍历或搜索树或图数据结构的算法。它从根节点开始沿着树的深度遍历子节点，直到到达叶子节点，然后回溯到前一个节点继续遍历。DFS通常使用递归或栈来实现。
DFS的原理是通过不断地探索一个节点的所有子节点，直到无法再继续深入为止。然后回溯到上一个节点，继续探索其他子节点。这种方法保证了每个节点都被访问且不会重复访问，同时也保证了整个数据结构被完整地遍历。
下面使用代码来实现DFS如下：
Java版本
栈版本：
import java.util.*;
public class DFSUsingStack {
private int V;
private LinkedList<Integer> adj[];
DFSUsingStack(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void DFS(int start) {
boolean visited[] = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int current = stack.pop();
if (!visited[current]) {
System.out.print(current + " ");
visited[current] = true;
Iterator<Integer> iterator = adj[current].listIterator();
while (iterator.hasNext()) {
int n = iterator.next();
if (!visited[n]) {
stack.push(n);
}
}
}
}
}
public static void main(String args[]) {
DFSUsingStack g = new DFSUsingStack(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);
g.DFS(2);
}
}
递归版本：
import java.util.*;
public class DFSUsingRecursion {
private int V; // Number of vertices
private LinkedList<Integer> adj[];
DFSUsingRecursion(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void DFSUtil(int v, boolean visited[]) {
visited[v] = true;
System.out.print(v + " ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}
void DFS(int start) {
boolean visited[] = new boolean[V];
DFSUtil(start, visited);
}
public static void main(String args[]) {
DFSUsingRecursion g = new DFSUsingRecursion(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);
g.DFS(2);
}
}
上面代码使用递归和栈实现了深度优先搜索，当从顶点2开始进行DFS遍历时，输出的结果应为"2 0 1 3"。
C++版本
使用栈：
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int start);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::DFS(int start) {
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
stack<int> stack;
stack.push(start);
while (!stack.empty()) {
int current = stack.top();
stack.pop();
if (!visited[current]) {
cout << current << " ";
visited[current] = true;
for (auto i = adj[current].begin(); i != adj[current].end(); ++i) {
if (!visited[*i])
stack.push(*i);
}
}
}
}
int main() {
Graph g(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);
cout << "DFS Traversal using Stack:" << endl;
g.DFS(2);
return 0;
}
使用递归：
#include <iostream>
#include <list>
using namespace std;
class Graph {
int V;
list<int> *adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int start);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::DFSUtil(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i])
DFSUtil(*i, visited);
}
}
void Graph::DFS(int start) {
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(start, visited);
}
int main() {
Graph g(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);
cout << "DFS Traversal using Recursion:" << endl;
g.DFS(2);
return 0;
}
JS版本
使用栈：
class Graph {
constructor() {
this.vertices = [];
this.adjList = new Map();
}
addVertex(v) {
this.vertices.push(v);
this.adjList.set(v, []);
}
addEdge(v, w) {
this.adjList.get(v).push(w);
}
DFS(start) {
let visited = new Set();
let stack = [start];
while (stack.length > 0) {
let current = stack.pop();
if (!visited.has(current)) {
console.log(current);
visited.add(current);
let neighbors = this.adjList.get(current);
for (let neighbor of neighbors) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
}
let g = new Graph();
g.addVertex(0);
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS(2);
使用递归：
class Graph {
constructor() {
this.vertices = [];
this.adjList = new Map();
}
addVertex(v) {
this.vertices.push(v);
this.adjList.set(v, []);
}
addEdge(v, w) {
this.adjList.get(v).push(w);
}
DFSUtil(v, visited) {
visited.add(v);
console.log(v);
let neighbors = this.adjList.get(v);
for (let neighbor of neighbors) {
if (!visited.has(neighbor)) {
this.DFSUtil(neighbor, visited);
}
}
}
DFS(start) {
let visited = new Set();
this.DFSUtil(start, visited);
}
}
let g = new Graph();
g.addVertex(0);
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS(2);
原文链接: https://blog.csdn.net/2401_82884096/article/details/138756386