java实现dfs(java实现dfa)-捕鱼10元起上10元下

什么是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，如果该节点未被访问，将其压入栈中，直到栈为空为止。