java实现dfs(java实现dfa)

什么是dfs？

深度优先搜索（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。其主要思想是从起点开始遍历，选择一条未被访问的边前进，若该节点没有未被访问的边，则返回上一个节点并选择另外一条未被访问的边，并依此类推，直到所有节点都被访问。

在java中，实现dfs可以使用递归或栈来处理代码。下面我们将分别介绍这两种实现方式。

使用递归实现dfs

使用递归实现dfs比较直观和简单。主要思路是递归遍历每个节点，并在递归中处理未被访问的边。下面是一个简单的使用递归实现dfs的例子：

```
class Graph {
private int V; // 节点数
private LinkedList adj[]; // 邻接表

Graph(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);
}

// dfs搜索
void dfs(int v, boolean visited[]) {
visited[v] = true;
System.out.print(v + " ");

Iterator i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
dfs(n, visited);
}
}
}

// 使用dfs搜索节点
void dfsSearch(int v) {
boolean visited[] = new boolean[V];
dfs(v, visited);
}
}
```

上面的代码中，我们定义了一个Graph类，其中包含节点数V和邻接表adj[]。在dfs方法中，我们首先将当前节点v设为已访问，并输出该节点信息。然后通过邻接表获取与该节点相邻的节点列表，对于每一个节点n，如果该节点未被访问，递归调用dfs方法进行遍历。

使用栈实现dfs

使用栈实现dfs的思路与递归类似，需要一个辅助栈来存储节点信息。主要思路是从起点开始，将其压入栈中，然后在循环中取出栈顶节点v，并标记其为已访问。接着通过邻接表获取与该节点相邻的节点列表，对于每一个节点n，如果该节点未被访问，将其压入栈中。直到栈为空为止。

下面是一个使用栈实现dfs的例子：

```
class Graph {
private int V; // 节点数
private LinkedList adj[]; // 邻接表

Graph(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);
}

// dfs搜索
void dfsSearch(int s) {
boolean visited[] = new boolean[V];

Stack stack = new Stack();
stack.push(s);

while (!stack.isEmpty()) {
s = stack.pop();

if (!visited[s]) {
visited[s] = true;
System.out.print(s + " ");
}

Iterator i = adj[s].iterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
stack.push(n);
}
}
}
}
}
```

上面的代码中，我们定义了一个Graph类，其中包含节点数V和邻接表adj[]。在dfsSearch方法中，我们首先定义一个栈，并将起点s压入栈中，然后进入循环。在循环中，从栈中取出栈顶节点s，并标记其为已访问。接着通过邻接表获取与该节点相邻的节点列表，对于每一个节点n，如果该节点未被访问，将其压入栈中，直到栈为空为止。